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

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, ... ?

• I've no idea if this observation is any use but the setup is completely symmetrical so, if $A$ is decidable, they all are. – David Richerby Nov 16 '16 at 0:41
• $B\cup C$ is the complement of $A$. That should help. – Hendrik Jan Nov 16 '16 at 1:37

## 2 Answers

$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}$).

Let's call MA, MB and MC 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 2nd and 3rd tapes.
2. T executes one step of MA on tape 1. If MA accepts x, T accepts x.
3. T executes one step of MB on tape 2. If MB accepts x, T rejects x.
4. T executes one step of MC on tape 3. If MC 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.