1
$\begingroup$

Prove that there does not exist a Turing machine M such that for every Turing machine K that halts on all inputs, $M$ accepts $\langle K\rangle$ if and only if $L(K)$ is infinite.

The above question came from a set of final practice problems for a computability course.

Suppose such a Turing machine M exists. Maybe one can contradict known theorems about decidability (e.g. the halting problem isn't decidable). Or perhaps Rice's theorem might be useful? Clearly the class of languages $L(K)$ so that $L(K)$ is infinite is nontrivial, so by Rice's theorem, the language $A := \{\langle M\rangle : L(M)\text{ is infinite}\}$ is undecidable. It might be possible to use the Turing machine M to decide A. M can be used to decide the language $B := \{\langle M\rangle : L(M)\text{ is infinite and M halts on all inputs}\}$. But the problem is that $M$ may not halt even if the input is of the form $\langle K\rangle$ for some Turing machine K.

$\endgroup$

1 Answer 1

1
$\begingroup$

The language of all Turing machines $T$ that do not halt on empty input is well-known to not be recognizable.

If the Turing machine $M$ of your question existed then you could decide the above language as follows:

  • Generate (the description of) a Turing Machine $K$ that, on input $x$, simulates $T$ on empty input for (up to) $|x|$ steps. If the simulation of $T$ does not halt within the $|x|$-th step, then $K$ accepts. Otherwise $K$ rejects.
  • Invoke $M$ with input $K$. $M$ accepts if and only if $L(K)$ is infinite, i.e., if and only if $T$ does not halt on empty input.
$\endgroup$

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.