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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

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

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