# Is the language of TMs that decide some language Turing-recognizable?

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 ?

• – Raphael
Oct 27 '15 at 21:43
• What, specifically have you tried towards proving your claims? Where did you get stuck?
– Raphael
Oct 27 '15 at 21:45
• @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. 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.

• Don't deciders have to fulfill more requirements than just to always halt? (Anyway, proof missing.)
– Raphael
Nov 10 '15 at 7:07
• @Raphael No, I don't think so. A machine that always halts always decides some language. Nov 10 '15 at 7:43
• Depends on your definition of "decider", I guess. What is the decision if the machine has "17" on the tape, or "123#456#321"?
– Raphael
Nov 10 '15 at 9:16
• 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. 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.

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