2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 8 '19 at 22:14
  • $\begingroup$ 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) $\endgroup$ – David Dec 8 '19 at 22:25
  • $\begingroup$ TOTAL is stronger than HALT. HALT is complete for the first level of the arithmetical hierarchy, while TOTAL is complete for the second level. $\endgroup$ – Yuval Filmus Dec 8 '19 at 22:27
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Dec 9 '19 at 16:30
  • $\begingroup$ If $L_{halt}$ were co-r.e. then it would be recursive, but Turing proved that it isn't. $\endgroup$ – Yuval Filmus Dec 9 '19 at 16:32
  • $\begingroup$ 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. $\endgroup$ – David Dec 9 '19 at 16:56
  • $\begingroup$ I wrote out the argument in full. $\endgroup$ – Yuval Filmus Dec 9 '19 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.