# Examples for incomparable semi-decidable but undecidable languages

In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made:

'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, computably enumerable sets that are not Turing equivalent to the halting problem. In particular the answer is yes if there are two computably enumerable languages $A$ and $B$ that are incomparable with respect to $\leq_T$, i.e. such that $A\nleq_T B$ and $B\nleq_T A$.

The text goes on proving that there exists such languages $A$ and $B$.

Does this imply undecidable recursively enumerable sets are not isomorphic to the halting problem? Are there examples of such languages?

• yes there is an entire "undecidability hierarchy" where there are more complex problems given (roughly) the halting problem as an oracle. – vzn Jul 15 '14 at 17:26