This question already has an answer here:


$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.


marked as duplicate by Ran G., Luke Mathieson, David Richerby, Kaveh, Juho Jun 6 '15 at 20:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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