1

Earlier I asked similar questions, but I deleted it because I don't think it was clear. I was reading Computation Complexity by Papadimitriou, and as the book defines recursively inseparable languages, it says $H$ and $\overline{H}$ are examples of recursively inseparable languages because they are the only possible separating languages and are both not recursive.

I understand $H$ and $\overline{H}$ are not recursive, but why are they the only possible separating languages? I don't understand what this means.

Ralff
  • 1,487

1 Answers1

1

A separating language $L$ would have to contain one and be disjoint from the other; so, for example, we would have to have $H \subseteq L$ and $\overline{H} \cap L = \emptyset$. With a random pair of languages $A$ and $B$, it's usually possible for a third language $C$ to contain $A$ and a little bit more, but not touch $B$; but if $L$ contains anything that isn't in $H$, then $L$ has to contain something in $\overline{H}$ (that's just what $\overline{H}$ means). So, in this case, $L$ would have to be $H$. Or we could have $\overline{H} \subseteq L$ and $H \cap L = \emptyset$, in which case $L = \overline{H}$. In other words, if $L$ is a set separating $H$ and $\overline{H}$, then $L$ must be either $H$ or $\overline{H}$.

To summarize: it's not that $H$ and $\overline{H}$ are the only possible separating languages in general. It's that they're the only languages that could possibly be the separating languages in this case.

Reese Johnston
  • 17,988