Given 3 disjoint Turing-recognizable languages prove that one of them is decidable

Question

Let $A$, $B$, $C$ be Turing-recognizable languages over an alphabet $\Sigma$. Assume that

• $A\cup B\cup C = \Sigma^*$, and
• $A\cap B = A\cap C = B\cap C = \emptyset$.

Prove that $A$ is Turing-decidable.

So far I've tried the following but it really hasn't gotten me anywhere.

Suppose $A$ is recognizable but not decidable then, $\overline{A} = B \cup C$ so $B$ or $C$ is undecidable, since decidable languages are closed under union.

In the case that only one is decidable you can show at least that its in $A$ or $B$ (or $A$ or $C$ in the other case). Then, ... ?

In the case that both are recognizable, ... ?

Answer 1

Let's call M_A, M_B and M_C the Turing machines that recognize A, B and C, respectively. The 3-TM T (a Turing machine with 3 tapes) that decides A can be described as follows:

T: input x.

1. Copy x on 2^nd and 3^rd tapes.
2. T executes one step of M_A on tape 1. If M_A accepts x, T accepts x.
3. T executes one step of M_B on tape 2. If M_B accepts x, T rejects x.
4. T executes one step of M_C on tape 3. If M_C accepts x, T rejects x.

T halts for every string x in A U B U C, so T halts for every input in Σ*. Moreover, L(T) = A. So T is a TM that decides A, and A is Turing-decidable.

Answer 2

$A$ is recognizable by assumption. Since $\overline{A}=B\cup C$ is recognizable (recognizable languages are closed under union) we have that $A$ and $\overline{A}$ are recognizable, and hence $A$ must be decidable (it's a simple exercise to construct a decider for $A$ from the recognizers of $A$ and $\overline{A}$).