Turing Machines

98 Views Asked by At

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.