27

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

manu fava
  • 393
  • 4
    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. – Arshak Aivazian Dec 26 '22 at 15:14
  • 2
    Very Interesting! Do you have a reference on that? – manu fava Dec 26 '22 at 15:29
  • 3
    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. – Joel David Hamkins Dec 26 '22 at 17:17

3 Answers3

25

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.

Joel David Hamkins
  • 224,022
  • But isn't the problem given by wlad below an answer to the dual question? – manu fava Dec 26 '22 at 20:25
  • 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." – Joel David Hamkins Dec 26 '22 at 20:33
  • 1
    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. – Joe Miller Dec 29 '22 at 14:44
12

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.

Dino Rossegger
  • 515
  • 1
    +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.) – Joel David Hamkins Dec 26 '22 at 18:41
  • 2
    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! – Noah Schweber Dec 26 '22 at 18:50
9

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.

wlad
  • 4,823
  • 4
    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. https://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: https://mathoverflow.net/a/12434/1946 – Joel David Hamkins Dec 26 '22 at 19:21
  • 1
    Related (on the CS Theory StackExchange): Proof of undecidability not by reduction from the halting problem. – Timothy Chow Dec 27 '22 at 02:57
  • 2
    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. – Joel David Hamkins Dec 27 '22 at 03:51
  • It seems to me that every degree above a low degree is realized by such an $f$. I'm not sure whether every noncomputable degree has a low degree below it, but if so, then every noncomputable degree would be realized by such an $f$. ($A$ is low, if $A'\equiv_T 0'$.) – Joel David Hamkins Dec 27 '22 at 16:12
  • Ah, it is not true that every nonzero degree has a low degree below it, since there are minimal degrees of arbitrary jump value above $0'$. (But this doesn't settle the question whether every nonzero degree is realized by an $f$.) – Joel David Hamkins Dec 27 '22 at 16:51
  • 3
    They're called PA degrees. This might help - https://www.computability.org/zoo/ – François G. Dorais Dec 27 '22 at 17:00
  • Of course if you set a time limit beforehand, and limit the termination on the problem to the limit, the consistent guessing problem is trivially computable. So problem occurs because you can't choose time limit that satisfies the problem description. – Esa Pulkkinen Dec 27 '22 at 18:57
  • @FrançoisG.Dorais I knew that every PA degree computes such a separating function, since the PA model itself will have a separating set, but are you saying this is equivalent? If I can compute a separation, then I can build the diagram of a model of PA? I guess one would want to use the separating function to find a path through the tree of attempts to build a complete consistent Henkin theory. – Joel David Hamkins Dec 29 '22 at 14:54
  • @JoelDavidHamkins Yes, the key is to use that the language contains implication. The basic idea is when it comes time to decide $\phi$ is true or false, check whether $\psi_0 \land \psi_1 \land \cdots \land \psi_{n-1} \to \lnot\phi$ is in the separating set where $\phi_0,\ldots,\psi_{n-1}$ are the sentences you've decided positively so far. If it is then to decide $\phi$ negatively, otherwise decide $\phi$ positively. – François G. Dorais Dec 29 '22 at 16:06
  • That is what I had been thinking, but does this actually work? After all, I might decide $\phi$ negatively, because that's what the separating function $f$ told me, but actually $\psi_0\wedge\psi_1\wedge\cdots\wedge\psi_{n-1}\to\phi$ is provable, in which case I'm in trouble. – Joel David Hamkins Dec 29 '22 at 16:59
  • 1
    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 – Joel David Hamkins Dec 29 '22 at 18:38
  • @JoelDavidHamkins My earlier comment was unclear what we were checking and why and we got our wires crossed. Let me try again in the next comment... – François G. Dorais Dec 30 '22 at 16:48
  • Say we have an oracle that correctly tells us "PA doesn't prove $\phi$" or "PA doesn't refute $\phi$" for any given sentence $\phi$. We use this oracle to guide a Henkin-style construction. At some step of that construction, we have decided that $\psi_1,\ldots,\psi_n$ are true. Our construction now asks us to decide the sentence $\phi$. We ask the oracle about the formula $\psi_1\land\cdots\land\psi_n\to\lnot\phi$. If the oracle says "PA does not refute this", then we decide that $\phi$ is false. If the oracle says "PA does not prove this" then we decide that $\phi$ is true. – François G. Dorais Dec 30 '22 at 17:03
  • Suppose the separating set oracle tells us that PA proves $\phi$ and also that it proves $\neg\phi$ (or, in your way of saying it, that PA does prove $\phi$ and that it does refute $\phi$). This seems possible, since the separating oracle is not perfectly reliable, but only has to get the true $\Sigma_1$ answers right. We will have to decide whether to add $\phi$ or to add $\neg\phi$, but we don't know which one is actually right. It could be that only one of them is right, and so we might not build a consistent theory. – Joel David Hamkins Dec 30 '22 at 17:46
  • @JoelDavidHamkins I'm confused, the separating set never says anything about PA proving things, it only says that PA doesn't prove things (and it's always correct). (I might have also gotten the revision wrong, there's way to many negatives floating around for the holiday season :) ) – François G. Dorais Dec 30 '22 at 17:48
  • The separating set is a total function that separates the accepting programs from the rejecting programs. We can't tell the difference between the true acceptances and the ones that are falsely said by the separating set to be accepting. – Joel David Hamkins Dec 30 '22 at 17:53
  • Oh wait, perhaps it is fine! We consider the program that accepts $\phi$ if it is provable (from the $\psi$s), and rejects $\phi$ if $\neg\phi$ is provable from the $\psi$s. Now, if the oracle tells us that $\phi$ was accepted, then even if this isn't true, we know at least it can't be that $\neg\phi$ was actually provable, and so we can keep $\phi$ in the theory. (Sorry for my confusion about this.) – Joel David Hamkins Dec 30 '22 at 17:58
  • It's confusing to think about it that way.... Here's my point of view: I have a function $f$ such that if PA proves $\phi$ then $f(\phi)=1$ and if PA proves $\lnot\phi$ then $f(\phi)=0$. Then $f(\phi) = 1$ means PA doesn't prove $\lnot\phi$ (doesn't refute $\phi$) and $f(\phi)=0$ means PA doesn't prove $\phi$. (So "doesn't refute" is the positive side...) – François G. Dorais Dec 30 '22 at 17:59
  • I think that is the same as what I just described. – Joel David Hamkins Dec 30 '22 at 18:00
  • 1
    @JoelDavidHamkins Like I said, that's way to many negatives for the holiday season! By the way: best wishes for 2023! – François G. Dorais Dec 30 '22 at 18:06
  • 1
    You too! Happy new year. And thanks for straigtening me out about this. Now I know that the PA degrees = degrees of separations of theorems/refutations, or of accepting/rejecting. – Joel David Hamkins Dec 30 '22 at 18:07