[Math] Is the union of undecidable languages not Turing-recognizable

formal-languagesturing-machines

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

  1. if first symbol is something else than 1, $reject$
  2. (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

  1. if first symbol is something else than 0, $reject$
  2. (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?

Best Answer

Your construction for $L_2$ assumes that you can decide in finite time whether or not $U$ accepts $t$, such that you can accept if $U$ does not accept $t$.

But you can't do that. That would require you to solve the halting problem for an arbitrary $U$, which is well known to be impossible. You even said yourself that $N$ will not halt (and thus will reject) if $U$ does not halt.

Related Question