# Is it possible that the union of two undecidable languages is decidable?

I'm trying to find two languages, $L_1, L_2 \in RE \setminus R$, such that $L_1 \cup L_2 \in R$.

I have already proved that if $L_1\cap L_2 \in R$ and $L_1 \cup L_2 \in R$, such $L_1, L_2$ don't exist (because otherwise we'll be able to construct a Turing Machine $M_1$ which will decide $L_1$, for instance).

However, I cannot prove that it's impossible in the case $L_1\cap L_2 \in RE \setminus R$, and I can't find such languages.

• Your observation about the intersection is incorrect. Take $L_1,L_2\in RE\setminus R$ such that $L_1\cap L_2=\emptyset$, then $L_1\cap L_2\in R$. – Shaull May 24 '13 at 19:11
• @Shaull - just to be clear, I proved that there aren't any $L_1, L_2 \in RE \backslash R$ s.t. $L_1 \cap L_2 \in R$ and $L_1 \cup L_2 \in R$. – Tomer May 25 '13 at 9:51
• Ah, I see. That's indeed correct. Perhaps consider editing the post to clarify that. – Shaull May 25 '13 at 9:58
• Your observation shows that the same problem, but with disjoint union has no solution. – Hendrik Jan May 25 '13 at 20:29

Take $L_1=\{0\cdot x:x\in \Sigma^*\}\cup \{1\cdot x: x\in A_{TM}\}$ and $L_2=\{1\cdot x:x\in \Sigma^*\}\cup \{0\cdot x: x\in A_{TM}\}$. Clearly both languages are in $RE\setminus R$.
However, their union contains $\{0\cdot x\}\cup \{1\cdot x\}=\Sigma^*\setminus\{\epsilon\}$, so their union is $\Sigma^*$, and is therefore decidable.
• Strictly speaking it's $\Sigma^{\ast}$ without the empty word. – sdcvvc May 25 '13 at 10:56