Problem Detail: Is the language $qquad L={ langle text{M} rangle ; | ; text{M is a Turing machine that decides some language} }$ a Turing-recognizable language? I think it’s not, as, even if I am able to tell somehow that a Turing machine halts for some input there are still infinite strings to check for. Similarly I think that this problem is not even co-recognizable. Am I right? If yes is there a more precise proof ?
Asked By : sashas
Answered By : Yuval Filmus
This language is usually known as TOT, the language of machines computing total functions. It is $Pi_2$-complete, and in particular is neither recognizable nor co-recognizable.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/48777
