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 ?

  • 1
    $\begingroup$ Duplicate? $\endgroup$ – Raphael Oct 27 '15 at 21:43
  • 1
    $\begingroup$ What, specifically have you tried towards proving your claims? Where did you get stuck? $\endgroup$ – Raphael Oct 27 '15 at 21:45
  • $\begingroup$ @Raphael I was only able to see that this problem was more difficult than halting problem as even if I am able to somehow determine that a Turing machine $T$ halts for some string $w$, there are infinite strings $w$ to check for. It's not a a correct way of proving, but by this I can see this problem is not decidable as halting problem is undecidable. Where I got stuck was I wanted to clarify if the same reason can be extended to language being not even Turing - recognizable. $\endgroup$ – sashas Oct 27 '15 at 21:51

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.

  • $\begingroup$ Don't deciders have to fulfill more requirements than just to always halt? (Anyway, proof missing.) $\endgroup$ – Raphael Nov 10 '15 at 7:07
  • $\begingroup$ @Raphael No, I don't think so. A machine that always halts always decides some language. $\endgroup$ – Yuval Filmus Nov 10 '15 at 7:43
  • $\begingroup$ Depends on your definition of "decider", I guess. What is the decision if the machine has "17" on the tape, or "123#456#321"? $\endgroup$ – Raphael Nov 10 '15 at 9:16
  • $\begingroup$ One possible definition is a special ACCEPT state and a special REJECT state. But taking your definition, we can adjust the machine by running an infinite loop if it doesn't output YES or NO, and then the argument goes through. $\endgroup$ – Yuval Filmus Nov 10 '15 at 9:20

Of course, this depends on what you exactly mean.

Do you mean, all the machines that decides a specific language? e.g., $$ L = \{ \langle M \rangle \mid M \text{ decides the language } A\}$$

then, it depends on the language $A$. For instance, if $A=HP$, the halting problem, then $L$ is clearly decidable (i.e., it is empty).

But if you mean, any language, i.e., that $M$ is a decider, $$ L = \{ \langle M \rangle \mid M \text{ halts on all inputs } \}$$ then $L$ is not recognizable, see Yuval's answer.

  • $\begingroup$ Also here, I don't think that the second $L$ you propose is the one from the question. $\endgroup$ – Raphael Nov 10 '15 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.