Are there known natural problems of intermediate degrees of unsolvability?

Question

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?

Answer 1

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".

Answer 2

"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).