# Are there known natural problems of intermediate degrees of unsolvability?

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?

-

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

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