prove that there does not exist a Turing machine with a particular property

Question

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.

Answer 1

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.