Let $L_0 = { <M, w, 0> | M text{ halts on } w}$ and $L_1 = {<M, w, 1> | M text{ does not halt on } w}$.

In $<M,w,i>$ 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 $<M, w, 0> in L_0$ on $M_0$
- and $<M, w, 1> 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?