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 Σ01 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 Σ01 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 Σ01 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 Σ01 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:
ON for each Turing machine encoding N, representing the oracle's answer about this machine.
H, representing that M(O) halts.
Rs 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, ON.
(b) For any machine N that halts and returns false, ¬ON.
(c) For any Turing machine state s whose next step is to halt, Rs→H.
(d) For any Turing machine state s whose next step is to go to state s' without querying the oracle, Rs→Rs′.
(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, (Rs∧ON→Rs′)∧(RS∧¬ON→Rs′′).
(f) For the initial state s0, Rs0.
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 ON variables must represent a consistent guessing oracle due to schemas (a) and (b). Let s0,…,sn be the execution trace of M when given the oracle represented by the ON variables; this trace must be finite because M halts for any consistent guessing oracle input. Rs0 is an axiom (so must be true in the model), and by induction each Rsi must be true in the model, using axiom schemas (d) and (e). Since Rsn is true in the model and sn 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 ON variables according to the consistent guessing oracle on which M fails to halt. Let s0,s1,… be the (infinite) execution trace of M on this oracle. We set Rsi to true for any non-negative integer i, and Rs to false for all other s. Finally, we set H to false. This model satisfies all axiom schemas:
(a) and (b) are assured since ON are set according to a consistent guessing oracle.
(c) is assured since Rs is only true when s=si for some i, and none of these states are final.
(d) and (e) are assured since Rs is only true when s=si, and in these cases we also have Rsi+1.
(f) is assured since Rs0 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 Σ01 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.
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 Σ01 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 Σ01 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 Σ01 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 Σ01 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:
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, ON.
(b) For any machine N that halts and returns false, ¬ON.
(c) For any Turing machine state s whose next step is to halt, Rs→H.
(d) For any Turing machine state s whose next step is to go to state s' without querying the oracle, Rs→Rs′.
(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, (Rs∧ON→Rs′)∧(RS∧¬ON→Rs′′).
(f) For the initial state s0, Rs0.
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 ON variables must represent a consistent guessing oracle due to schemas (a) and (b). Let s0,…,sn be the execution trace of M when given the oracle represented by the ON variables; this trace must be finite because M halts for any consistent guessing oracle input. Rs0 is an axiom (so must be true in the model), and by induction each Rsi must be true in the model, using axiom schemas (d) and (e). Since Rsn is true in the model and sn 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 ON variables according to the consistent guessing oracle on which M fails to halt. Let s0,s1,… be the (infinite) execution trace of M on this oracle. We set Rsi to true for any non-negative integer i, and Rs to false for all other s. Finally, we set H to false. This model satisfies all axiom schemas:
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 Σ01 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.