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

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.

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.