The consistent guessing problem is easier than the halting problem

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 claiming to prove 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 $\Sigma^0_1$ 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 $\Sigma^0_1$ 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 $\Sigma^0_1$ 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 $\Sigma^0_1$ 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:

$O_N$ for each Turing machine encoding N, representing the oracle’s answer about this machine.
H, representing that M(O) halts.
$R_s$ 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, $O_N$ .
(b) For any machine N that halts and returns false, $\neg O_N$ .
(c) For any Turing machine state s whose next step is to halt, $R_s \rightarrow H$ .
(d) For any Turing machine state s whose next step is to go to state s’ without querying the oracle, $R_s \rightarrow R_{s'}$ .
(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, $(R_s \wedge O_N \rightarrow R_{s'}) \wedge (R_S \wedge \neg O_N \rightarrow R_{s''})$ .
(f) For the initial state $s_0$ , $R_{s_0}$ .

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 $O_N$ variables must represent a consistent guessing oracle due to schemas (a) and (b). Let $s_0, \ldots, s_n$ be the execution trace of M when given the oracle represented by the $O_N$ variables; this trace must be finite because M halts for any consistent guessing oracle input. $R_{s_0}$ is an axiom (so must be true in the model), and by induction each $R_{s_i}$ must be true in the model, using axiom schemas (d) and (e). Since $R_{s_n}$ is true in the model and $s_n$ 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 $O_N$ variables according to the consistent guessing oracle on which M fails to halt. Let $s_0, s_1, \ldots$ be the (infinite) execution trace of M on this oracle. We set $R_{s_i}$ to true for any non-negative integer i, and $R_s$ to false for all other s. Finally, we set H to false. This model satisfies all axiom schemas:

(a) and (b) are assured since $O_N$ are set according to a consistent guessing oracle.
(c) is assured since $R_s$ is only true when $s = s_i$ for some i, and none of these states are final.
(d) and (e) are assured since $R_s$ is only true when $s = s_i$ , and in these cases we also have $R_{s_{i+1}}$ .
(f) is assured since $R_{s_0}$ 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 $\Sigma^0_1$ 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 consistent guessing problem is easier than the halting problem

Published by Jessica Taylor

Leave a comment Cancel reply

Share this:

Related

Published by Jessica Taylor

Leave a comment Cancel reply