Let languages $A, B$ be defined as $$\begin{align} A &= \{\langle M\rangle\mid M(\langle M\rangle)=reject\}\\ B &= \{\langle M\rangle\mid M(\langle M\rangle)=accept\} \end{align}$$ In other words, $A$ is the set of descriptions of TMs which reject their own descriptions and $B$ is defined similarly. The languages $A$ and $B$ are disjoint, and are both Turing-recognizable. Prove that there does not exist a decidable language $C \subseteq \Sigma^*$ such that $A \subseteq C$ and $B \subseteq \overline{C}$, the complement.


Suppose there was a decidable language, $C$, of TM descriptions such that $A\subseteq C$ and $B\subseteq \overline{C}$. Since $C$ was assumed to be decidable, there is a decider TM, $D_C$, for it. Then either $\langle\,D_C\,\rangle\in C$ or $\langle\,D_C\,\rangle\in \overline{C}$. Let's run $D_C$ on its own description:

  • If $\langle\,D_C\,\rangle\in C$, then $D_C$ will accept $\langle\,D_C\,\rangle$ and hence $\langle\,D_C\,\rangle\in B\subseteq \overline{C}$, a contradiction.
  • In a similar way, if $\langle\,D_C\,\rangle\in \overline{C}$, we again reach a contradiction, that $\langle\,D_C\,\rangle\in A\subseteq C$.

Since we reach a contradiction in either case, we can conclude that there is no such $C$, as desired. This non-existence, by the way, has a name: we say that $A$ and $B$ are recursively inseparable.


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.