The halting problem is the problem of taking as input a Turing machine M, returning true if it halts, false if it doesn’t halt. This is known to be uncomputable. The consistent guessing problem (named by Scott Aaronson) is the problem of taking as input a Turing machine M (which either returns a Boolean or never halts), and returning true or false; if M ever returns true, the oracle’s answer must be true, and likewise for false. This is also known to be uncomputable.
Scott Aaronson inquires as to whether the consistent guessing problem is strictly easier than the halting problem. This would mean there is no Turing machine that, when given access to a consistent guessing oracle, solves the halting problem, no matter which consistent guessing oracle (of which there are many) it has access too. As prior work, Andrew Drucker has written a paper describing a proof of this, although I find the proof hard to understand and have not checked it independently. In this post, I will prove this fact in a way that I at least find easier to understand. (Note that the other direction, that a Turing machine with access to a halting oracle can be a consistent guessing oracle, is trivial.)
First I will show that a Turing machine with access to a halting oracle cannot in general determine whether another machine with access to a halting oracle will halt. Suppose M(O, N) is a Turing machine that returns true if N(O) halts, false otherwise, when O is a halting oracle. Let T(O) be a machine that runs M(O, T), halting if it returns false, running forever if it returns true. Now M(O, T) must be its own negation, a contradiction.
In particular, this implies that the problem of deciding whether a Turing machine with access to a halting oracle halts cannot be a statement in the arithmetic hierarchy, since these statements can be decided by a machine with access to a halting oracle.
Now consider the problem of deciding whether a Turing machine with access to a consistent guessing oracle halts for all possible consistent guessing oracles. If this is a statement, then consistent guessing oracles must be strictly weaker than halting oracles. Since, if there were a reliable way to derive a halting oracle from a consistent guessing oracle, then any machine with access to a halting oracle can be translated to one making use of a consistent guessing oracle, that halts for all consistent guessing oracles if and only if the original halts when given access to a halting oracle. That would make the problem of deciding whether a Turing machine with access to a halting oracle halts a statement, which we have shown to be impossible.
What remains to be shown is that the problem of deciding whether a Turing machine with access to a consistent guessing oracle halts for all consistent guessing oracles, is a statement.
To do this, I will construct a recursively enumerable propositional theory T that depends on the Turing machine. Let M be a Turing machine that takes an oracle as input (where an oracle maps encodings of Turing machines to Booleans). Add to the T the following propositional variables:
for each Turing machine encoding N, representing the oracle’s answer about this machine.
H, representing that M(O) halts.
for each possible state s of the Turing machine, where the state includes the head state and the state of the tape, representing that s is reached by the machine’s execution.
Clearly, these variables are recursively enumerable and can be computably mapped to the natural numbers.
We introduce the following axiom schemas:
(a) For any machine N that halts and returns true, .
(b) For any machine N that halts and returns false, .
(c) For any Turing machine state s whose next step is to halt, .
(d) For any Turing machine state s whose next step is to go to state s’ without querying the oracle, .
(e) For any Turing machine state s whose next step is to query the oracle on N and go to state s’ if O(N) is true, and state s″ otherwise, .
(f) For the initial state , .
These axiom schemas are all recursively enumerable. For the first two schemas, note that Turing machines that halt and return true are recursively enumerable, and likewise for Turing machines that halt and return false.
Suppose M halts for any consistent guessing oracle input. We wish to show that H is true in all models of T. For contradiction, assume some model of T in which H is false. In this model, the variables must represent a consistent guessing oracle due to schemas (a) and (b). Let be the execution trace of M when given the oracle represented by the variables; this trace must be finite because M halts for any consistent guessing oracle input. is an axiom (so must be true in the model), and by induction each must be true in the model, using axiom schemas (d) and (e). Since is true in the model and is a final state, H must also be true in the model due to the axiom schema (c). This is a contradiction.
Suppose M fails to halt for some consistent guessing oracle input. We wish to show that H is false in some model of T (even if it is true in others). Set the variables according to the consistent guessing oracle on which M fails to halt. Let be the (infinite) execution trace of M on this oracle. We set to true for any non-negative integer i, and to false for all other s. Finally, we set H to false. This model satisfies all axiom schemas:
(a) and (b) are assured since are set according to a consistent guessing oracle.
(c) is assured since is only true when for some i, and none of these states are final.
(d) and (e) are assured since is only true when , and in these cases we also have .
(f) is assured since is true in the model.
Therefore, H is true in all models of T if and only if M halts for all consistent guessing oracle inputs. By the completeness theorem for propositional logic, H is true in all models of T if and only if T proves H. So T proves H if and only if M halts for all consistent guessing oracle inputs. Since T’s axioms are recursively enumerable, all theorems of T can be recursively enumerated. We can therefore recursively enumerate all machines for which the corresponding theory entails H. So, the question of whether a Turing machine M halts on all consistent guessing oracle inputs can be computably translated to a statement.
As we have shown earlier, this implies that the consistent guessing problem is strictly easier than the halting problem, that is, there is no Turing machine that reliably solves the halting problem when given access to a consistent guessing oracle.
Note that Andy Drucker is not claiming to have discovered this; the paper you link is expository.
Since Drucker doesn’t say this in the link, I’ll mention that the objects you’re discussing are conventionally know as PA degrees. The PA here stands for Peano arithmetic; a Turing degree solves the consistent guessing problem iff it computes some model of PA. This name may be a little misleading, in that PA isn’t really special here. A Turing degree computes some model of PA iff it computes some model of ZFC, or more generally any Σ1 theory capable of expressing arithmetic.
Drucker also doesn’t mention the name of the theorem that this result is a special case of: the low basis theorem. “Low” here suggests low computability strength. Explicitly, a Turing degree A is low if solving the halting problem for machines with an oracle for A is equivalent (in the sense of reductions) to solving the halting problem for Turing machines without any oracle. The low basis theorem says that every computable binary tree has a low path. We are able to apply the theorem to this problem, concluding that there is a consistent guessing oracle C which is low. So, we cannot use this oracle to solve the halting problem; if we could, then an oracle machine with access to C would be at least as strong as an oracle machine with access to the halting set, but we know that the halting set suffices to compute the halting problem for such a machine, which is a contradiction.
Various other things are known about PA degrees, though I’m not sure what might be of interest to you or others here. This stuff is discussed in books on computability theory, like Robert Soare’s Computability Theory and Applications. Though, I thought I learned about PA degrees from his earlier book, but now I don’t see them in there, so maybe I just learned about PA degrees around the same time, possibly following my interest in your and others’ work on reflective oracles. The basics of computability theory—Turing degrees, the Turing jump, and the arithmetic hierarchy in the computability sense—may be of interest to the extent there is anything there that you’re not already familiar with. With regard to PA degrees, in particular people like to talk about diagonally nonrecursive functions. This works as follows. Let φn denote the nth partial computable function according to some Goedel numbering. The PA degrees are exactly the Turing degrees that compute functions f:N→2 such that f(n)≠φn(n) for all numbers n at which the right-hand side is defined. This is suggestive of the ideas around reflective oracles, the Lawvere fixed-point theorem, etc. But I wouldn’t say that when I think about these things, I think of them in terms of diagonally nonrecursive functions; plausibly that’s not an interesting direction to point people in.
Are there any other nice decision problems that are low? A quick search only reveals existence theorems.
Intuitive guess: Can we get some hierarchy from oracles to increasingly sparse subsets of the digits of Chaitin’s constant?
Well, I guess describing a model of a computably enumerable theory, like PA or ZFC counts. We could also ask for a model of PA that’s nonstandard in a particular way that we want, e.g. by asking for a model of PA+¬Con(PA), and that works the same way. Describing a reflective oracle has low solutions too, though this is pretty similar to the consistent guessing problem. Another one, which is really just a restatement of the low basis theorem, but perhaps a more evocative one, is as follows. Suppose some oracle machine T has the property that there is some oracle that would cause it to run forever starting from an empty tape. Then, there is a low such oracle.
(Technically, these aren’t decision problems, since they don’t tell us what the right decision is, but just give us conditions that whatever decisions we make have to satisfy. I don’t know what to say instead; this is more general then e.g. promise problems. Maybe I’d use something like decision-class problems?)
All these have a somewhat similar flavour by the nature of the low basis theorem. We can enumerate a set of constraints, but we can’t necessarily compute a single object satisfying all the constraints. But the theorem tells us that there’s a low such object.
I don’t know what the situation is for subsets of the digits of Chaitin’s constant. Can it be as hard as the halting problem? You might try to refute this using some sort of incompressibility idea. Can it be low? I’d expect not, at least for computable subsets of indices of positive density. Plausibly computability theorists know about this stuff. They do like constructing posets of Turing degrees of various shapes, and they know about which shapes can be realized between 0 and the halting degree 0′. (E.g. this paper.)
Ah, the low basis theorem does make more sense of Drucker’s paper. I thought Turing degrees wouldn’t be helpful because there are multiple consistent guessing oracles, but it looks like they are helpful. I hadn’t heard of PA degrees, will look into it.
Yeah, there’s a sort of trick here. The natural question is uniform—we want a single reduction that can work from any consistent guessing oracle, and we think it would be cheating to do different things with different oracles. But this doesn’t matter for the solution, since we produce a single consistent guessing oracle that can’t be reduced to the halting problem.
This reminds me of the theory of enumeration degrees, a generalization of Turing degrees allowing open-set-flavoured behaviour like we see in partial recursive functions; if the answer to an oracle query is positive, the oracle must eventually tell you, but if the answer is negative it keeps you waiting indefinitely. I find the theory of enumeration degrees to be underemphasized in discussion of computability theory, but e.g. Odifreddi has a chapter on it all the way at the end of Classical Recursion Theory Volume II.
The consistent guessing problem isn’t a problem about enumeration degrees. It’s using a stronger kind of uniformity—we want to be uniform over oracles that differently guess consistently, not over a set of ways to give the same answers, but to present them differently. But there is again a kind of strangeness in the behaviour of uniformity, in that we get equivalent notions if we do or do not ask that a reduction between sets A, B be a single function that uniformly enumerates A from enumerations of B, so there might be some common idea here. More generally, enumeration degrees feel like they let us express more naturally things that are a bit awkward to say in terms of Turing degrees—it’s natural to think about the set of computations that are enumerable/Σ1 in a set—so it might be a useful keyword.