$L=\{ \langle M \rangle \mid M \text{ is a Turing Machine which halts on all inputs}\}$.

Is this a Turing-recognizable language? I guess that it is neither Turing-recognizable, nor co-Turing-recognizable, but I can't prove it.

  • $\begingroup$ You can apply Rice's theorem. But more is true: in fact, $L$ is $\Pi_2$-complete. $\endgroup$ – Yuval Filmus May 15 '14 at 14:39
  • $\begingroup$ @Yuval Rice's theorem is about decidability, while this question is about semi-decidability. $\endgroup$ – FrankW May 15 '14 at 15:46
  • $\begingroup$ FrankW is right. Your language is also known as TOT, the language of total functions. If you spend some quality time with your favorite search engine you will find many hits, for example cs.uml.edu/~wang/cs502/NonRE.pdf. $\endgroup$ – Yuval Filmus May 15 '14 at 18:17
  • $\begingroup$ answers can be found here. Although chronologically first, I vote to close as dupe. $\endgroup$ – Ran G. Jun 3 '15 at 22:08
  • $\begingroup$ @FrankW, there is a stronger form of Rice's theorem which is about a set being c.e. $\endgroup$ – Kaveh Jun 5 '15 at 1:59