Unrecognizability of functional variant of halting problem

Question

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?

Answer 1

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.