# 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. – 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.

• 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. – Yuval Filmus 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. – 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.

• 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