The Halting problem is a natural undecidable language which is complete for the set of recursivly enumrable sets. I am interested in undecidable but not Turing-complete language such that we can not reduce the Halting problem to it.

What is the most natural undecidable RE problem which is not Turing-complete?


1 Answer 1


There indeed are sets that are undecidable but not Turing complete. However, I'm not sure there is such a thing as a natural undecidable not Turing complete language.

Emil Post set out on a search for exactly this (See Post's problem) and his research resulted in the Simple sets. To quote from the Wikipedia article:

[Its existence] was affirmed by Friedberg and Muchnik in the 1950s using a novel technique called the priority method. They give a construction for a set that is simple (and thus non-recursive), but fails to compute the halting problem.

  • $\begingroup$ I will wait for a natural problem. $\endgroup$ Mar 23, 2013 at 13:33
  • $\begingroup$ Some have argued that there are none. $\endgroup$ Mar 23, 2013 at 14:04
  • $\begingroup$ Could you provide a pointer? $\endgroup$ Mar 23, 2013 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.