patternMinor
Natural RE undecidable problems but not Turing-complete
Viewed 0 times
undecidablebutcompletenaturalturingproblemsnot
Problem
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?
What is the most natural undecidable RE problem which is not Turing-complete?
Solution
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.
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.
Context
StackExchange Computer Science Q#9772, answer score: 9
Revisions (0)
No revisions yet.