The question is as follows:
Let us define $$L := \{w \mbox{ | either }w = 1x \mbox{ for some } x \mbox{ ∈ $A_{TM}$ or } \mbox{$w$ = 0$y$ for some $y$ ∈ $\overline {A_{TM}}$}\}.$$Prove that neither $L$ nor $\overline{L}$ are Turing-recognizable.
Here $A_{TM}$ is a language such that $A_{TM} = \{\langle M,v \rangle\ |\ \mbox{$M$ is a Turing machine and $M$ accepts $v$}\}$, $\overline{L}$ is the complement of $L$ and $\overline{A_{TM}}$ is the complement of $A_{TM}$.
Attempt to solution:
Let's first define $$L_1 := \{w\ |\ w = 1x \mbox{ for some } x \in A_{TM}\}$$ and $$L_2 := \{w\ |\ w = 0y \mbox{ for some } y \in \overline{A_{TM}}\}$$ where $L_1 \cup L_2 = L$
Now let's try to construct a TM $M$ that recognizes $L_1$:
$M =$ "On input $\langle w \rangle$, where $w$ is a word
- if first symbol is something else than 1, $reject$
- (else) if the rest of the word $w$ is in $A_{TM}$, $accept$, otherwise, $reject$. In more details, since the rest of the word is assumed to be an encoding of a TM $V$ and another word $s$ ($\langle V,s \rangle$), we call $V$ on input $s$. If $V$ accepts, $accept$, if $V$ rejects, $reject$."
Thus, this language is Turing-recognizable. However it is not decidable since $M$ will not halt if $V$ does not halt.
Now let's try to construct a TM $N$ that recognizes $L_2$:
$N =$ "On input $\langle w \rangle$, where $w$ is a word
- if first symbol is something else than 0, $reject$
- (else) if the rest of the word $w$ is in $\overline{A_{TM}}$, $accept$, otherwise, $reject$. In more details, since the rest of the word is assumed to be an encoding of a TM $U$ and another word $t$ ($\langle U,t \rangle$), we call $U$ on input $t$. If $U$ accepts $t$, $reject$, if $U$ rejects $t$, $accept$."
Thus, this language is Turing-recognizable. However it is not decidable since $N$ will not halt if $U$ does not halt.
And now I am stuck: how can I show that the union of these two undecidable languages is not Turing-recognizable? To me, it seems as if $L$ would be recognizable as well. Did I make a mistake above?
