Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know there exist intermediate degrees of unsolvability, i.e. there are undecidable problems which can be reduced to the Halting Problem, but not vice versa. Are there any "natural" problems known or suspected to fall into this category?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

No, there are no natural problems that are known to be or suspected to be intermediate. It is a remarkable phenomenon in computability theory. There has been some discussion about it from time to time on the FOM email list; you can find it by searching for "intermediate Turing degree".

share|improve this answer
add comment

"Natural" is kind of a sliding scale, but I would intuitively expect some variation of

Is the number of $N$-state two-symbol Turing machines (up to renumbering of states) that halt on the empty input, odd?

to have intermediate Turing degree. At least this is slightly less unnatural than the extremely synthetic problems that result from the priority construction. On the other hand it is not recursively enumerable (which is required by the discussion you link to, but not by your own reformulation).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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