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

1 Answer 1

10
$\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\}$, and therefore equals $\Sigma^*\setminus \{\epsilon\}$, and is therefore decidable.

$\endgroup$
5
  • 2
    $\begingroup$ Strictly speaking it's $\Sigma^{\ast}$ without the empty word. $\endgroup$
    – sdcvvc
    May 25, 2013 at 10:56
  • $\begingroup$ why it is cleary in $ RE \setminus R $ why its not in $ R $ ? $\endgroup$
    – maya cohen
    Jan 26 at 9:22
  • 1
    $\begingroup$ @mayacohen - because $A_{TM}$ easily reduces to each of them. E.g., for $L_1$ the reduction is $f(x)=1\cdot x$. $\endgroup$
    – Shaull
    Jan 26 at 16:33
  • $\begingroup$ what is the notation of Atm means? @Shaull and can I also what to know if the intersection is in R ? is it the empty lang? $\endgroup$
    – maya cohen
    Jan 26 at 17:51
  • 1
    $\begingroup$ @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!) $\endgroup$
    – Shaull
    Jan 27 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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