"Natural" undecidable problems not reducible to the halting problem There is a lot of known examples of undecidable problems, a large amount of them not directly related to turing machines or equivalent models of computations, for example here: https://en.m.wikipedia.org/wiki/List_of_undecidable_problems
It is also known that the structure of turing degrees is extremely complicated, and that there are undecidable problems not reducible to the halting problems, the most basic example being "Does a turing machine with an oracle for the halting problem halts?"
So my question is: Is there a example of a problem not related to abstract machines that is undecidable but not reducible to the halting problem? (That is, that has turing degree different from 0')
 A: Aaronson's "Consistent Guessing" problem: Consider a total function $f : M \to \{0,1\}$, where:

*

*$M$ denotes the set of Turing machines which either accept or reject their inputs, or fail to terminate


*$f(m) = 1$ whenever $m$ terminates in an accepting state


*$f(m)=0$ whenever $m$ terminates in a rejecting state.


*The value of $f(m)$ when $m$ does not terminate is left unspecified. But the function must yield a value in $\{0,1\}$ regardless.
The problem is uncomputable.
The above problem is related to the problem LLPO in constructive logic: Decide for a computable real $x$ whether $x \leq 0$ or $x \geq 0$. The halting problem instead corresponds to the problem LPO in constructive logic: Decide for a computable real $x$ whether $x < 0$ or $x = 0$ or $x > 0$. LPO is stronger.
A: The problems reducible to the halting problem are exactly the problems of complexity $\Delta^0_2$ in the arithmetic hierarchy, and there are indeed many natural problems outside of this class. In this sense, you are asking for natural examples of decision problems of high arithmetic complexity.

*

*Arithmetic truth, to decide if a given arithmetic sentence $\sigma$ is true in the standard model $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, is undecidable, but not reducible to the halting problem.


*$\Sigma^0_n$ truth, restricted to sentences of this complexity, for $n\geq 2$ is undecidable, but not reducible to the halting problem.


*Projective truth, to decide if a given sentence $\sigma$ is true in the real field $\langle\mathbb{R},+,\cdot,0,1,<,\mathbb{Z}\rangle$, with the integers as a unary predicate, is undecidable, but not reducible to the halting problem.


*Set-theoretic truth in various models, to decide if a given sentence is true in the structure of hereditarily countable sets $\langle H_{\omega_1},\in\rangle$ or in the least Zermelo universe $V_{\omega+\omega}$ or the least Zermelo-Grothendieck universe $\langle V_\kappa,\in\rangle$, if there is one, is undecidable, but not reducible to the halting problem.


*To decide if a given c.e. group presentation is trivial generally has complexity $\Pi^0_2$ (because one must say every generator is trivial), and this will be undecidable, but not reducible to the halting problem. (Note, for c.e. presentations with finitely many generators, this is reducible to the halting problem.)


*To decide if a given c.e. graph on the natural numbers is connected generally has complexity $\Pi^0_2$, making it undecidable and not reducible to the halting problem.


*To decide if a given computable function is total has complexity $\Pi^0_2$, since one must say every input has a halting computation, and this is complete for that level of complexity, making it undecidable, but not reducible to the halting problem.


*To decide if a given computable function is surjective has complexity complete $\Pi^0_2$, and so this is undecidable, but not reducible to the halting problem. (Meanwhile, to decide if it is injective is $\Pi^0_1$ and hence reducible to the halting problem.)
There are many more examples. See for example the hierarchy of degrees of irrationality. All the examples higher in the hierarchy amount to undecidable decision problems that are not reducible to the halting problem.
A dual to your question. There is a dual version of your question that is fascinating and the subject of a research program in computability theory. Namely, are there natural decision problems that are undecidable, but such that the halting problem does not reduce to them?
To be sure, the Friedberg-Muchnik solution of Post's problem shows that there are undecidable c.e. Turing degrees strictly below the halting problem, and so there are indeed undecidable decision problems strictly below the halting problem. But these problems are constructed especially for this purpose, and in this sense, are not seen as "naturally" arising. Furthermore, it is widely regarded as an open question whether there are natural decision problems in this class (one proposal: the set of differences of primes). Although I often find such uses of "natural" to be empty, in computability theory there is a research program to formulate substantive versions of the question, via Martin's conjecture and other approaches. See my further discussion of this in my paper, Linearity and illfoundedness in the hierarchy of large cardinal consistency strength, especially sections 9, 10, and 11, which focus on naturality and computability theory.
A: There have already been excellent answers, with the property that they (with the exception of (3) and (4) of the above answer) are reducible to an iteration of the Turing jump along a computable well-ordering. So let me add a couple that are not.
The set of computable linear orderings that have a dense subordering,i.e., embed a copy of the rational numbers $\mathbb Q$, and the set of computable linear orderings that are not well-ordered, i.e., have an infinite descending sequence, are known to be $\Sigma^1_1$ complete. Conversely, the set of computable well-orderings is $\Pi^1_1$ complete. Not only are these sets not reducible to the Halting problem, even iterating the Turing jump along a computable well-ordering won't let you compute them.
