# 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$. May 24, 2013 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$. May 25, 2013 at 9:51
• Ah, I see. That's indeed correct. Perhaps consider editing the post to clarify that. May 25, 2013 at 9:58
• Your observation shows that the same problem, but with disjoint union has no solution. May 25, 2013 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\}$$, and therefore equals $$\Sigma^*\setminus \{\epsilon\}$$, and is therefore decidable.
• Strictly speaking it's $\Sigma^{\ast}$ without the empty word. May 25, 2013 at 10:56
• why it is cleary in $RE \setminus R$ why its not in $R$ ? Jan 26 at 9:22
• @mayacohen - because $A_{TM}$ easily reduces to each of them. E.g., for $L_1$ the reduction is $f(x)=1\cdot x$. Jan 26 at 16:33
• @mayacohen - $A_{TM}=\{\langle M,w \rangle:\ M\text{ accepts }w\}$. Just a canonical $RE\setminus R$ language. The intersection $L_1\cap L_2$ is not in $R$ (think why!) Jan 27 at 13:33