Proof that $(L_{all})^C$ is not recursively enumerable

Question

The problem:

We have the language $L_{all} = \{\operatorname{Kod}(M) | M \text{ is a turing machine and } L(M) = \Sigma ^*\}$

Hence, $L_{all}$ is the set of all encoded Turing machines (the $\operatorname{Kod}()$ is the encoding function) which accept all words as input.

One needs to show that $(L_{all})^C$, the complement of $L_{all}$ is not in $\mathcal{L}_{RE}$, that means it is not recursively enumerable.

By definition, in $(L_{all})^C$ we have all strings which do not represent correctly encoded Turing machines as well as encoded Turing machines which reject at least one word from the alphabet.

What have I tried so far:

• One idea was to use the diagonalization argument that can be used to prove that $L_{diag}$, the diagonal language is not recursively enumerable. This however doesn't seem to work.
• I tried to prove that the statement is wrong (i.e. $(L_{all})^C)$ is recursively enumerable: The proof would more or less go like this (not very formal): Let $A$ be a Turing machine deciding if $x \in (L_{all})^C$. We first check if $A$'s input is a correctly encoded Turing machine ($x = \operatorname{Kod}(M)$), if not we reject. If it is, we associate every word from $\Sigma^*$ with a prime $p$ and then use this to simulate all words on $M$ at once, (in the $p^i$th step of $A$ we simulate the $i$th step of $M$ on the $p$th word). This is where my counter proof fails. Since there are uncountably infinitely many words in $\Sigma^*$ and only countably infinitely many primes. However I do not see a way how I can use this fact to prove the original statement.

Any suggestion or hints would be greatly appreciated since I am genuinely interested how one approaches such a proof.

Full disclosure This was a bonus question on an old exam (not connected to homework) and I am curious how one can prove this, especially since it seems to be somewhat counter intuitive.

Answer 1

Let HALT be the following version of the halting problem: Given a Turing machine $T$, determine whether it halts on the empty input.

Here is a computable reduction from HALT to $L_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which erases its input and then transfers control to $T$. You can check that $T \in \mathrm{HALT}$ iff $T' \in L_{all}$. This shows that $L_{all}$ cannot be co-r.e. Indeed, if $L_{all}$ were co-r.e. then HALT would be co-r.e. Since HALT is also known to be r.e., it would be recursive; but we know that HALT is not recursive.

Here is a computable reduction from HALT to the complement of $L_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which on input $n$ runs $T$ on the empty input for $n$ steps; if $T$ halted, $T'$ enters an infinite loop, and otherwise $T'$ halts. You can check that $T \in \mathrm{HALT}$ iff $T' \notin L_{all}$. This shows that $L_{all}$ cannot be r.e. Indeed, if $L_{all}$ were r.e. then HALT would be co-r.e., and we get a contradiction like in the preceding paragraph.

In fact, $L_{all}$ is $\Pi_2$-complete; it is sometimes known as TOT or TOTAL. Thus $L_{all}$ is stronger than HALT, which is only $\Sigma_1$-complete.