I came across this problem which asks to show the existence of two disjoint Turing-recognizable sets $A$ and $B$ such that no decidable set $C$ can separate them...

In this case, a set $C$ is said to separate $A$ and $B$ if $A \subseteq C$ and $B \subseteq \overline{C}$ ... If only $A$ is Turing-recognizable, then we could easily set $A$ to be $A_{TM}$ and $B$ as $\overline{A_{TM}}$. However, in this case both $A$ and $B$ are Turing-recognizable .... I think that $A$ and $B$ should be constructed using diagonalization, but could not think of a way to do it ... Any help ?

  • 1
    $\begingroup$ You can find some example on Wikipedia. $\endgroup$ Commented Jul 1, 2020 at 9:57


Your Answer

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