Sorry for long title - the question is a bit unwieldy. To state the question precisely, I'm wondering about the following proposition:

Let $\Sigma = \{0,1\}$. If $A$ and $B$ are Turing-recognizable and $A \cup B = \Sigma^*$, then there exists a Turing-decidable language $C$ such that $A \cap \overline{B} \subseteq C$ and $\overline{A} \cap B \subseteq \overline{C}$ (equivalently, $A - B \subseteq C$ and $B - A \subseteq \overline{C}$

So, my current train of thought is as follows. Because $A \cup B$ is $\Sigma^*$, we have that $\Sigma^*$ is partitioned into exactly three disjoint sets: $A - B$, $A \cap B$, and $B - A$. That is, given $x \in \Sigma^*$, $x$ is in exactly one of these sets.

The basic way I can think of to obtain a decidable language is to enumerate one in lexicographic order (which always yields a decidable language). So one idea would be to enumerate $\Sigma^*$ in lexicographic order, and print a string if and only if it is not in $B - A$, but that poses a problem because we would have to decide membership in $B - A$, but they are merely recognizable.

I've thought about enumerating $A$ and $B$ but since they're only recognizable, the enumerations could be in any arbitrary order, making it impossible to compare them to test for membership in $A-B$ or $B-A$.

Finally, I know that $A$ and $B$ (if they are infinite) have infinite decidable subsets, but I don't think that will help.

I'd appreciate some hints if anyone has any.

Edit: Missed a hypothesis that $\Sigma = \{0,1\}$, which I'm not sure is relevant (I wouldn't think so), but it might be.


2 Answers 2


Got it. The question makes it seem more complicated than it really is.

Let $M$ and $N$ be TMs that recognize $A$ and $B$, respectively. Construct an enumerator $E$ that behaves as follows:

  1. For each $s_i \in \Sigma^*$ (in lexicographic order):
  2. Run $M$ and $N$ on $s_i$ simultaneously. It must be the case that $s_i$ is in at least one of $A$ or $B$. So, at least one machine is guaranteed to halt.
  3. If $M$ halts, $s_i \in A$, which means certainly $s_i \not\in \overline{A} \cap B$, so print $s_i$.
  4. If $N$ halts, $s_i \in B$, which means certainly $s_i \not\in A \cap \overline{B}$, so do not print $s_i$.

So $E$ prints at least all the strings in $A \cap \overline{B}$, and definitely does not print strings in $\overline{A} \cap B$. $E$ enumerates a language in lexicographic order, so its language is decidable and satisfies the conditions.


I believe 'C' is not also turing decideable. Consider the following 3 cases:

Case 1 : Intersection of A and B is empty set and neither of them is empty. Then A and B become Turing Decidable, therefore C also becomes turing decidable. Closure properties for TM.

Case 2: Intersection of A and B is either of them (Lets say A-B = A). Then, language (B-A) transforms to an undecidable, as its equivalent to the language which is empty. C = A-B = A, is Turing recognizable.

Case 3: Intersection of A and B is non-empty. Now, for C - TM for A should accept which would as its acceptor and TM for B should reject as it shouldnt belong to it. BUT since, B is an Turing recognizable(not decider) only (assuming from your query), it means it might never halt for the input which doesnt belongs to it. Thereby, the TM accepting C might never halts for strings belonging to C.Thereby, C doesnt have any acceptor.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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