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

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.

• Your language is known as TOT or TOTAL, and it is completely for the second level of the arithmetical hierarchy. In particular, it is neither r.e. nor co-r.e. If you just want to show the latter, reduce the halting problem to your language or its complement. – Yuval Filmus Dec 8 '19 at 22:14
• Isn't the halting problem recursively enumerable but not recursive, since if a Turing machine halts on some input one can find out in finite time (by simulating until it halts). How exactly would a reduction from the halting problem help if it's in a "stronger" category than the TOTAL language. (Sorry for asking ,I am a second undergrad and just getting started with complexity) – David Dec 8 '19 at 22:25
• TOTAL is stronger than HALT. HALT is complete for the first level of the arithmetical hierarchy, while TOTAL is complete for the second level. – Yuval Filmus Dec 8 '19 at 22:27

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.
• I understand how this shows that $L_{halt} \leq L_{all}$ as well as $L_{halt} \leq (L_{all})^C$. In our textbook we have shown that $L_{halt}$ is recursively enumerable. So the two reduction are necessarily true if $L_{all}$ is not in r.e. but not sufficient, since by reducing the halting problem they could also be in r.e.. I don't quite understand how the not in r.e. part follows from this. – David Dec 9 '19 at 16:30
• If $L_{halt}$ were co-r.e. then it would be recursive, but Turing proved that it isn't. – Yuval Filmus Dec 9 '19 at 16:32
• Yes but $L_{halt}$ is still r.e. and we are reducing $L_{halt}$ to $L_{all}$ which essentially just tells me that $L_{all}$ is not recursive. Similarly we can also only show that $(L{all})^C$ is not recursive by reducing $L_{halt}$ to $L_{all}^C$. Since we already know that $L_{all}$ is not recursively enumerable we cannot make any statement about $(L{all})^C$ (if it were recursively enumerable $(L{all})^C$ couldn't be recursively enumerable since otherwise both languages would be recursive). There is probably something in your reasoning that I don't understand yet. – David Dec 9 '19 at 16:56