Automata Turing

Question

Could someone explain the question below step by step?

Suppose that Σ is a finite set and that L1, L2 and L3 are Turing acceptable subsets of Σ^* that satisfy the following properties: L1 ∪ L2 ∪ L3 = Σ^∗ ; L1 ∩ L2 = L2 ∩ L3 = L3 ∩ L1 = ∅. Show that L1, L2 and L3 must all be recursive.

Answer 1

We are given that:

L1 union L2 union L3 = E*
L1 intersect L2 = {}
L1 intersect L3 = {}
L2 intersect L3 = {}
L1 is acceptable/semidecidable/recursively enumerable/recognizable
L2 is acceptable/semidecidable/recursively enumerable/recognizable
L3 is acceptable/semidecidable/recursively enumerable/recognizable

We need to show that L1, L2 and L3 are rejectable/decidable/recursive/co-recognizable.

Can we show that a string is not in L1? Yes. Because the union of these three languages contains all strings, and because no two languages overlap, we know that any string not in L1 is in either L2 or L3. Because these languages are acceptable/semidecidable/recursively enumerable/recognizable, we have TMs TM2 and TM3 which will eventually accept/decide/enumerate/recognize strings in L2 and L3, respectively. In order to recognize a string is not in L1, we can set T2 and T3 running and see whether either one ever accepts/decides/enumerates/recognizes the string, in which case we know that L1 must not.

We now know that L1 is both acceptable/recursively enumerable/recognizable and, simultaneously, rejectable//co-recursively enumerable/co-recognizable. Languages such as this are decidable/recursive.

Because L1, L2 and L3 were numbered arbitrarily, any result that applies to L1 must apply to L2 and L3 as well, since we might as well have considered these other languages to be L1. In other words, the exact same argument given above applies if you swap L1 with either L2 or L3.

Therefore, each of the three languages is decidable/recursive.