Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...


1 Answer 1


The question shows several misconceptions. I'll try to clarify the key aspects.

If $L$ is recognizable but not decidable, then $L$ has to be infinite (otherwise, it is decidable). If a TM recognizes such $L$, it has to accept all the words in $L$ (by definition of "recognizes"), hence it must halt in infinitely many cases.

A TM halting on infinitely many cases does not imply that the recognized language is decidable. (I'm unsure about why you think this would be the case, it would make the halting problem decidable, for instance.)

There is no such a thing as an uncountable language, at least in a conventional setting where the alphabet is countable, and words have finite length. Hence, a TM can never halt on "uncountably many" words.

  • $\begingroup$ Okay, thank you for your clarification, let me rephrase it, I want to show that such a Turing Machine will fail to halt, if there are infinitely many inputs $\endgroup$
    – Joe
    Commented Nov 12, 2019 at 2:14
  • $\begingroup$ @Joe That machine will fail to halt on infinitely many inputs, otherwise (if it diverges only on finitely many cases), one could modify the TM on those finitely many cases so that it halts and rejects them and craft a TM that decides $L$, which is impossible. $\endgroup$
    – chi
    Commented Nov 12, 2019 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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