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$ – Yuval Filmus Jul 1 '20 at 9:57

Your Answer

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

Browse other questions tagged or ask your own question.