1
$\begingroup$

Let $L_0 = \{ \langle M, w, 0 \rangle \mid M \text{ halts on } w\}$ and $L_1 = \{\langle M, w, 1\rangle \mid M \text{ does not halt on } w\}$. In $\langle M,w,i \rangle$, the $i$ indicates a specific bit such as $0$ for language $L_0$ and $1$ for language $L_1$.

I want to prove that $L = L_0 \cup L_1$ is unrecognizable and so is $\overline{L}$.

I think: the halting problem $\{\langle M,x \rangle \mid M \text{ halts on input } x \}$ is recognizable, that is, given a machine $M$ and a string $w$, I can always get acceptance if $M$ stops on $w$ by simply running it.

Assume that $L_0$ and $L_1$ are recognizable, that is, there are machines $M_0$ and $M_1$ such that $M_0$ accepts $x \in L_0$ and halts, $M_1$ accepts $x \in L_1$ and halts. Then to recognize $x \in L_0 \cup L_1$, we can have a hypothetical $M_\cup$ that can recognize (not decide) $L_0 \cup L_1$:

  • we can run $\langle M, w, 0 \rangle \in L_0$ on $M_0$
  • and $ \langle M, w, 1 \rangle \in L_1$ on $M_1$

So:

  • If $M_0$ stops we know $M$ halts on $w$ and
  • if $M_1$ stops we know $M$ does not halt on $w$

(Note that any $x \not \in L_0 \cup L_1$ will lead to divergence on these two machines. That’s why $M_\cup$ can only recognize $L_0 \cup L_1$ and cannot decide.)

Thus we have solved the halting problem: for any $M$ and $w$, $M_\cup$ will accept and halt for both

  • $M$ halts on $w$
  • $M$ does not halt on $w$

This is a contradiction (halting problem is undecidable) and so both $M_0$ and $M_1$ cannot exist simultaneously. This proves that $L = L_0 \cup L_1$ is not recognizable.

For the $\overline{L}$ case: $\overline{L} = \overline{L_0} \cap \overline{L_1}$. As stated previously, $L_0$ is recognizable and $L_1$ is not recognizable (“no Turing machine can recognize all Turing machines that never halt”: Corollary 2 here).

  • $\overline{L_0}$ is not recognizable
  • $\overline{L_1}$ is recognizable
  • $\implies \overline{L}$ is not recognizable

Is this a valid chain of arguments for this proof?

$\endgroup$
1
$\begingroup$

A Turing machine $T$ decides the halting problem if on input $\langle M,w \rangle$:

  • If $M$ halts on $w$, then $T$ halts and outputs "Yes".
  • If $M$ does not halt on $w$, then $T$ halts and outputs "No".

In order to show that $L$ is not recognizable, you assume that $L$ is recognizable, and use that to construct a Turing machine $T$ which decides the halting problem. This is not quite what you are doing:

  • You are assuming that $L_0,L_1$ are recognizable, but you don't explain how this follows from $L$ being recognizable.
  • You don't explain why $M_{\cup}$ always halts. This is only the case if you run $M_0$ and $M_1$ in parallel, and halt whenever one of them halts.
  • You state that $M_{\cup}$ always accepts and halts whether $M$ halts on $w$ or not. However, such a machine is easy to construct: all you need to do is to immediately halt, without even reading the input. What we need is that $M_{\cup}$ halts with a different answer depending on whether $M$ halts on $w$ or not.

Moving forward, for $\overline{L}$, you express $\overline{L}$ as the intersection of a non-recognizable language and a recognizable language, and conclude that $\overline{L}$ is not recognizable. Unfortunately, this step is invalid. For example, the empty language is the intersection of a non-recognizable language of your choice and the empty language, which is recognizable; yet the empty language is recognizable.

Instead, you need an argument very similar to the one you use for $L$ itself.

$\endgroup$
6
  • $\begingroup$ I think the $\bar{L}$ part is completely wrong then. I'll redo that. Regarding the proof for $L$: yes, the parallel construction part should have been explicit. I don't understand the third point. In this parallel construction, either machine $M_0$ or $M_1$ must halt because either $M$ halts on $w$ or does not halt on $w$. If $M_0$ halts, we print "yes" and if $M_1$ halts, we print "no". Is that valid? $\endgroup$ – sprajagopal Jan 13 at 11:36
  • 1
    $\begingroup$ You have to state that explicitly. $\endgroup$ – Yuval Filmus Jan 13 at 11:36
  • $\begingroup$ As you stated in point 1, the bigger issue is $L_1$. Corollary 2 from here says (I think) $L_1$ is unrecognizable. If so, then my assumption that $L_1$ has a machine $M_1$ is itself wrong which breaks apart the whole proof. Is that correct? $\endgroup$ – sprajagopal Jan 13 at 11:45
  • $\begingroup$ Your starting assumption is that $L$ is recognizable. Take that as your starting point. $\endgroup$ – Yuval Filmus Jan 13 at 11:47
  • 1
    $\begingroup$ Yes, that’s the idea of the proof. $\endgroup$ – Yuval Filmus Jan 13 at 12:00

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.