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

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.