[Solved]: Is it possible that the union of two undecidable languages is decidable?

Problem Detail: 

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.

Asked By : Tomer

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12252