Examples for incomparable semi-decidable but undecidable languages

Question

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?

Answer 1

Some undecidable r.e. sets are isomorphic to the halting problem, for example the halting problem itself. Others are not, for example the one constructed by Friedberg and Muchnik using the priority method, a complicated kind of diagonalization. This set is not easy to describe, though one could argue that its description is "explicit". For some references, check out the Wikipedia article on simple sets, or any lecture notes on recursion theory.