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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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".
"Natural" is kind of a sliding scale, but I would intuitively expect some variation of
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).