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')



"Natural" undecidable problems not reducible to the halting problem
The problems reducible to the halting problem are exactly the problems of complexity $\Delta^0\_2$ in the [arithmetic hierarchy](https://en.wikipedia.org/wiki/Arithmetical_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](https://mathoverflow.net/a/53754/1946). 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](https://en.wikipedia.org/wiki/Friedberg%E2%80%93Muchnik_theorem) 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](https://arxiv.org/abs/2208.07445), especially sections 9, 10, and 11, which focus on naturality and computability theory.


