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

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$


  • 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?