27
$\begingroup$

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

$\endgroup$
3
  • 4
    $\begingroup$ The problem of determining that a given computable function $\mathbb{N} \to \mathbb{N}$ is a bijection, for example. I don't remember right off the bat an argument proving this. I remember there were many such natural problems from my university course on computability theory. $\endgroup$ Dec 26, 2022 at 15:14
  • 2
    $\begingroup$ Very Interesting! Do you have a reference on that? $\endgroup$
    – manu fava
    Dec 26, 2022 at 15:29
  • 3
    $\begingroup$ Soare's book on the computably enumerable sets and degrees has a whole list of such problems, and he analyzes the arithmetic logical complexity of all them. But I think most books on the Turing degrees will do this. $\endgroup$ Dec 26, 2022 at 17:17

3 Answers 3

24
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ But isn't the problem given by wlad below an answer to the dual question? $\endgroup$
    – manu fava
    Dec 26, 2022 at 20:25
  • $\begingroup$ No, because some of the functions $f$ with his property are Turing equivalent to the halting problem — indeed, the most natural way to produce such a function is to consult (and encode) the halting problem. To construct one that isn't, one needs in effect at some point to undertake a priority argument construction in the style of Friedberg-Muchnik, which is exactly the kind of thing found supposedly to be "unnatural." $\endgroup$ Dec 26, 2022 at 20:33
  • 1
    $\begingroup$ It's true that wlad gave a very natural problem that can't be computably solved, can be solved with the halting problem, and which doesn't require the halting problem. However, the problem doesn't naturally have a Turing degree; put differently, there is no least Turing degree solution. To some extent, it depends on what you mean by "problem". Wlad's problem has Muchnik degree (or Medvedev degree), but doesn't give us a "natural" noncomputable Turing degree below the halting problem. $\endgroup$
    – Joe Miller
    Dec 29, 2022 at 14:44
12
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ +1. This is a canonical example. (....but notice that my examples of projective truth and set-theoretic truth also are not computable from any iteration of the Turing jump.) $\endgroup$ Dec 26, 2022 at 18:41
  • 2
    $\begingroup$ This isn't quite true actually - via mastercodes we can make sense of iterates of the jump past $\omega_1^{CK}$, and in particular get up to and past $\mathcal{O}$ (@JoelDavidHamkins' examples are more robust against mastercodes assuming $V\not=L$). But +1 nonetheless, of course! $\endgroup$ Dec 26, 2022 at 18:50
9
$\begingroup$

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.

$\endgroup$
21
  • 4
    $\begingroup$ The keyword for this phenomen is computably inseparable sets, which are disjoint c.e. sets $A$ and $B$ such that there is no computable set $C$ containing $A$ and disjoint from $B$. In this example, $A$ is the set of $m$ accepting their input, and $B$ is the set of $m$ rejecting their input. Other examples include: the set of theorems of PA and the set of negations of theorems of PA. en.wikipedia.org/wiki/Computably_inseparable. Computable inseparability can be used to prove Tennenbaum's theorem, and that there is no computable model of ZFC: mathoverflow.net/a/12434/1946 $\endgroup$ Dec 26, 2022 at 19:21
  • 1
    $\begingroup$ Related (on the CS Theory StackExchange): Proof of undecidability not by reduction from the halting problem. $\endgroup$ Dec 27, 2022 at 2:57
  • 2
    $\begingroup$ Although the functions $f$ in this answer are all noncomputable, some of them are strictly above the halting problem, some are Turing equivalent to the halting problem, and some are strictly below the halting problem (these latter examples are subtle, but I can explain if desired). In this sense, the example of the answer doesn't actually exhibit the property requested in the OP. $\endgroup$ Dec 27, 2022 at 3:51
  • 3
    $\begingroup$ They're called PA degrees. This might help - computability.org/zoo $\endgroup$ Dec 27, 2022 at 17:00
  • 1
    $\begingroup$ That is, couldn't the separating function tell me both that $\psi_0\wedge\cdots\wedge\psi_{n-1}\to\neg\phi$ and also $\psi_0\wedge\cdots\wedge\psi_{n-1}\to\phi$, but only the latter is actually right. @FrançoisG.Dorais $\endgroup$ Dec 29, 2022 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.