2

Suppose that $\Sigma$ is a finite set and that $L_1$, $L_2$ and $L_3$ are Turing acceptable subsets of $\Sigma^*$ that satisfy the following properties:

  1. $L_1 \cup L_2 \cup L_3 = \Sigma^*$;

  2. $L_1 \cap L_2 = L_2 \cap L_3 = L_3 \cap L_1 = \varnothing$.

Show that $L_1$, $L_2$ and $L_3$ must all be recursive.

Brian M. Scott
  • 616,228
user43573
  • 39
  • Can you prove the corresponding result for the case of two languages, $L_1$ and $L_2$, such that $L_1\cap L_2=\varnothing$ and $L_1\cup L_2=\Sigma^*$? That’s a very standard result, and at least one proof of it generalizes very easily to your problem. – Brian M. Scott Dec 03 '13 at 01:39
  • I know that if L1 and L2 are recursive then L U P is also recursive and so is L1 ∩ L2 but I don't know how to go the other way around! – user43573 Dec 03 '13 at 01:46
  • 1
    Suppose that $M_1,M_2$, and $M_3$ are Turing machines that accept $L_1,L_2$, and $L_3$, respectively. Do you know that there must be a Turing machine $M$ that simulates running $M_1,M_2$, and $M_3$ simultaneously on the input to $M$? – Brian M. Scott Dec 03 '13 at 01:55

0 Answers0