patternModerate
Is it possible that the union of two undecidable languages is decidable?
Viewed 0 times
theundecidablelanguagesunionpossibletwothatdecidable
Problem
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.
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.
Solution
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.
However, their union contains $\{0\cdot x\}\cup \{1\cdot x\}=\Sigma^\setminus\{\epsilon\}$, and therefore equals $\Sigma^\setminus \{\epsilon\}$, and is therefore decidable.
Context
StackExchange Computer Science Q#12252, answer score: 10
Revisions (0)
No revisions yet.