Say that a language $C$ is a separator for disjoint languages $A$ and $B$ if $A \subseteq C$ and $B \subseteq \bar{C}$.

I need to find two languages $A,B\in \mathrm{RE}$ that have no recursive separator $C$.

  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help with conceptual problems but we're not here to solve exercises for you. $\endgroup$ – David Richerby Dec 24 '14 at 17:09
  • $\begingroup$ Note: this is very similar to Sipser problem 4.20. $\endgroup$ – Ryan Dec 24 '14 at 18:04
  • 1
    $\begingroup$ Hint: what if $A=C$ and $B=\overline{C}$? $\endgroup$ – Ran G. Dec 24 '14 at 18:15
  • $\begingroup$ We'll I have tried a few approaches, first you can notice that since $C \in R$ so is $\bar{C} \in R$. I've tried to build a reduction using the fact that $A \cup B \in RE$ and build a TM that will be equivalent to H_{tm}, but that didn't work. I'm not looking for a solution to copy, more of a hint towards a possible solution $\endgroup$ – Edo Cohen Dec 24 '14 at 19:44
  • $\begingroup$ Ran.G, in the case $A=C$ and $B=\bar{C}$, C is a recursive separator. $\endgroup$ – Edo Cohen Dec 24 '14 at 19:50

Hint: Such sets $A,B$ (sans the requirement of recursive enumerability) are called recursively inseparable. According to Wikipedia "it is possible for $A$ and $B$ to be recursively inseparable, disjoint, and recursively enumerable", and Wikipedia might have relevant examples. (Even if not, now you know what term to look for in the vast sea of internet.)

Extra hint: Wikipedia does indeed provide two such examples:

  1. $A$ is the set of encodings of TMs whose output is $0$, $B$ is the set of encodings of TMs whose output is $1$.
  2. $A$ is the set of provable tautologies, $B$ is the set of refutable contradictions.
  • 1
    $\begingroup$ that's a comment, not an answer. $\endgroup$ – Ran G. Dec 27 '14 at 18:23
  • $\begingroup$ A complete answer is a faux pas, since it's probably a homework exercise. $\endgroup$ – Yuval Filmus Dec 27 '14 at 20:26

So, this is what I came up with:

$A=\left\{ \left \langle M \right \rangle \ | \ \left \langle M \right \rangle \in\ L(M)\right\}$

$B=\left\{ \left \langle M \right \rangle \ | \ \left \langle M \right \rangle \notin\ L(M)\right\}$

Now, let's assume there exists such a $C \in R$ s.t. $B \subseteq C$ and $A \subseteq \overline{C}$

Let $M_C$ be a TM such that $L(M_C)=C$.

Now, consider $M_C(\left \langle M_C \right \rangle)$

If $M_C$ accepts, then $\left \langle M_C \right \rangle \in A$ by A's definition. Because $A \subseteq \overline{C}$, we get that $\left \langle M_C \right \rangle \notin C$ so $M_C$ rejects.

On the other hand, if $M_C$ rejects, then $\left \langle M_C \right \rangle \in B$ so we get $\left \langle M_C \right \rangle \in B \subseteq C$ so we get that $\left \langle M_C \right \rangle \in C$, so $M_C$ accepts.


  • 2
    $\begingroup$ Is $B$ recursively enumerable? $\endgroup$ – sdcvvc Dec 26 '14 at 10:31
  • $\begingroup$ Nope, you're right, $B \in Co-RE$, I guess this isn't a valid proof. $\endgroup$ – Edo Cohen Dec 27 '14 at 18:06

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.