How is Turing Machine which accepts nothing is not Recursively Enumerable?

Question

How is Turing Machine which accepts nothing is not Recursively Enumerable.

Answer 1

We will use an indirect argument to show that the language of encodings of Turing Machines that accept nothing cannot be recursively enumerable.

Lemma 1: if L and its complement are recursively enumerable, then L is recursive.

Proof: let M be a TM that enumerates L and M' be a TM that enumerates the complement of L. Given any string s, we can decide whether s is in L as follows. Begin running M and M', interleaving their executions so that each one eventually gets an arbitrary amount of runtime. If s is in L, M will eventually list it, at which point we know s is in L and we halt-accept. If s is not in L, M' will eventually list it, at which point we know s is not in L and we halt-reject. Thus, for any s, we can halt-accept if s is in L or halt-reject otherwise. Therefore, L and its complement are recursive.

Lemma 2: The language of encodings of Turing Machines that accept something is recursively enumerable.

Proof: The set of all Turing Machine encodings is countable, and so is the set of all possible tape inputs. Thus, the set (M, s) of pairs of machines and inputs is countable. We may therefore assume some ordering of these pairs p1, p2, ..., pk, ... For each pair p = (M, s), begin executing machine M on input s, interleaving the executions of pairs p1, p2, ..., pk, ... so each eventually gets an arbitrary amount of runtime. If pk enters the halt-accept state, we may immediately list M as a TM that accepts something (namely, the corresponding s), and we can even terminate all other running instances checking the same M (and forego starting any new ones). Any machine M that accepts some input will eventually be started and will eventually halt-accept on an input, so all machines are eventually enumerated.

Lemma 3: The language of encodings of Turing Machines that accept nothing is not recursive.

Proof: This is a direct result of Rice's Theorem. The property "accepts nothing" is a semantic property of the language itself and is true for some, but not all, languages; therefore, no TM can decide whether another TM accepts a language with the property or not.

Theorem: The language of encodings of Turing Machines that accept nothing is not recursively enumerable.

Proof: Assume this language is recursively enumerable. We have already proven in Lemma 2 that its complement is recursively enumerable. By Lemma 1, then, both languages are recursive. However, Lemma 3 proves that the language is not recursive. This is a contradiction. The only assumption was that the language is recursively enumerable, so that assumption must have been false: so the language is not recursively enumerable.