4
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I will wait for a natural problem. $\endgroup$ – Mohammad Al-Turkistany Mar 23 '13 at 13:33
  • $\begingroup$ Some have argued that there are none. $\endgroup$ – Andrej Bauer Mar 23 '13 at 14:04
  • $\begingroup$ Could you provide a pointer? $\endgroup$ – Mohammad Al-Turkistany Mar 23 '13 at 14:48

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.