# Unrecognizability of functional variant of halting problem

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?

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.

• 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? Jan 13, 2021 at 11:36
• You have to state that explicitly. Jan 13, 2021 at 11:36
• 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? Jan 13, 2021 at 11:45
• Your starting assumption is that $L$ is recognizable. Take that as your starting point. Jan 13, 2021 at 11:47
• Yes, that’s the idea of the proof. Jan 13, 2021 at 12:00