0
$\begingroup$

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

My first intuition is "Yes", since we may look at $M_1, M_2$ which accepts $L_1, L_2$, respectively. Then, WLOG there's $w$ such that $M_1$ doesn't halt for, and so the machine $M$ which runs $M_1, M_2$ in parallel, may not halt.

$\endgroup$
  • $\begingroup$ If $w \in L_1$, then $M_1$ must always halt for $w$ $\endgroup$ – Erbureth says Reinstate Monica May 23 '15 at 13:34
  • $\begingroup$ I've corrected it. was sort of a typo.. $\endgroup$ – Elimination May 23 '15 at 13:53
5
$\begingroup$

Hint: Let $L$ be any language in $\mathsf{RE} - \mathsf{R}$, and consider $$ L_1 = 0\Sigma^* \cup 1L, \quad L_2 = 1\Sigma^* \cup 0L. $$

$\endgroup$
  • $\begingroup$ But $L_1$ mustn't be decidable since it's in $RE-R$. Maybe I'm missing your intention. $\endgroup$ – Elimination May 23 '15 at 14:12
  • $\begingroup$ No, I think I misinterpreted your $R$ to mean regular rather than recursive. $\endgroup$ – Yuval Filmus May 23 '15 at 14:18
  • $\begingroup$ I'm looking at the intersection of $L_1, L_2$ but don't see why $L_1 \cap L_2 \in R$ $\endgroup$ – Elimination May 23 '15 at 14:50
  • $\begingroup$ What has intersection got to do anything with this? You asked about the union $L_1 \cup L_2$. $\endgroup$ – Andrej Bauer May 23 '15 at 16:16
  • 1
    $\begingroup$ You can also give a similar example for intersection: $0L$ and $1L$. $\endgroup$ – Yuval Filmus May 23 '15 at 20: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.