# turing machines – Showing this union: \${ | M text{ halts on } w} cup { | M text{ does not halt on } w}\$ is unrecognizable

Let $$L_0 = { | M text{ halts on } w}$$ and $$L_1 = { | M text{ does not halt on } w}$$.
In $$$$ 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 it $$bar{L}$$.

I think: the halting problem $${< M,x >:M$$ halts on input $$x }$$ is recognizable i.e. given a machine $$M$$ and a string $$w$$, I can always get acceptance if $$M$$ stops on $$w$$ by simply running it.

Assumption: if $$L_0$$ and $$L_1$$ were recognizable i.e. if there are machines $$M_0$$ and $$M_1$$ that accept and halt i.e. $$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 $$ in L_0$$ on $$M_0$$
• and $$ 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 $$bar{L}$$ case: $$bar{L} = bar{L}_0 cap bar{L}_1$$. As stated previously $$L_0$$ is recognizable. $$L_1$$ is not recognizable (“no Turing machine can recognize all Turing machines that never halt”: corollary 2 from here).

• $$bar{L}_0$$ is not recognizable
• $$bar{L}_1$$ is recognizable
• $$implies bar{L}$$ is not recognizable

Is this a valid chain of arguments for this proof?

Posted on