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?

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

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.


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.