2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Shaull May 24 '13 at 19:11
  • 1
    $\begingroup$ @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$. $\endgroup$ – Tomer May 25 '13 at 9:51
  • $\begingroup$ Ah, I see. That's indeed correct. Perhaps consider editing the post to clarify that. $\endgroup$ – Shaull May 25 '13 at 9:58
  • $\begingroup$ Your observation shows that the same problem, but with disjoint union has no solution. $\endgroup$ – Hendrik Jan May 25 '13 at 20:29
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Strictly speaking it's $\Sigma^{\ast}$ without the empty word. $\endgroup$ – sdcvvc May 25 '13 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.