# How strong “Consistent Guessing Problem” is?

I saw "Rosser’s Theorem via Turing machines" at:

https://www.scottaaronson.com/blog/?p=710

The modified halting problem (Consistent Guessing Problem) CGP is used in the proof:

CGP(M) - accepts if M accepts on a blank tape
CGP(M) - rejects if M rejects on a blank tape
CGP(M) - either accepting or rejecting if M runs forever on a blank tape


It's shown in the proof TM which solves CGP doesn't exist. Consider I have CGP as oraculum. Does it allow me to solve halting problem?

• What do you think? Have you tried solving the halting problem using CGP as an oracle? – Yuval Filmus May 30 '18 at 13:41
• I mean, can I solve halting problem with CGP function? – smrt28 May 30 '18 at 13:46
• Have you tried reducing the halting problem to CGP? – Yuval Filmus May 30 '18 at 13:47
• I tried, no success. – smrt28 May 30 '18 at 13:57
• See Comment #12 in your link. – Yuval Filmus May 30 '18 at 14:04

Andy Drucker, in a comment (with follow-up) to Scott Aaronson's blog post, shows that

HALT does not reduce to Consistent Guessing (CG).

Here is his proof (copied verbatim), which uses diagonalization:

We’ll build a language $L$ that’s a solution (i.e., refinement) of CG. On stage $i$ we’ll try to set finitely many bits of $L$ so as to ensure that the $i$th machine $M_i$ doesn’t solve HALT when given oracle access to $L$.

If this works, then we’re done! So assume for contradiction’s sake that we get stuck on some stage $i$. We’re going to use this premise to solve HALT — without an oracle. This absurdity will prove the result.

So — say we’re stuck at stage $i$, and we have some finite setting $L[i]$ to some of the bits of $L$, consistent with CG.

Let $L^*$ be $L[i]$ augmented with all of the bits ‘forced’ by CG: i.e., $L^*(M) = 0$ whenever $M$ halts with output $0$, and similarly for $1$. So, $L^*(M)$ still is undefined for all but finitely many of the machines $M$ that run forever.

Now, for each input $M$ to $M_i$, by our assumption we have that

$$M_i^{L’}(M) = HALT(M)$$

whenever $L’$ is an extension of $L^*$. An application of König’s lemma tells us that for each $M$ there is a number $n = n(M)$ such that any extension of $L^*$ with arbitrary values up through input lengths $n$, causes $M_i(M)$ to output $HALT(M)$.

So, here’s how we can determine the value $HALT(M)$: we dovetail simulations of all Turing machines. On stage $j$ we simulate the first $j$ machines for $j$ steps each. Whenever a machine halts with output ($0$ or $1$), we extend our finite approximation of $L^*$. (This approximation begins with the finitely many values of $L[i]$, hard-coded into the algorithm). Let $L^*[j]$ be the finite approximation to $L^*$ on the $j$th stage.

On the second part of stage $j$, we simulate $M_i(M)$ on all extensions of $L^*[j]$ up to length $j$. That is, we take the values we have so far, and we try extending them in all possible ways. We then simulate $M_i(M)$ on all of these extensions as oracle, for $j$ steps each. If on all such simulations, the machine halts with some output $b$, without ever trying to access an undefined oracle bit, then we output “$HALT(M) = b$”.

The claim is, this always halts with the right answer. Using our earlier analysis with König’s lemma (and the fact that $L^*[j]$ converges to $L^*$), we find that for large enough $j$, we will output the correct bit, if we reach stage $j$.

So we just need to argue that we never output a wrong bit earlier. But this is easy: at every stage $j$, at least one of our simulations is an initial segment of a correct simulation of $M_i(M)$ on a valid CG oracle. Thus that simulation always either halts with the correct output, or doesn’t halt, or tries to access an undefined oracle bit. So we never get a unanimous incorrect vote.

• I'm not sure about the proof syntax. What does L[i] mean? – smrt28 Jun 1 '18 at 14:09
• We think of $L$ as a Boolean function, which we construct in stages. At stage $i$, we have a partial function $L[i]$. The final $L$ is some extension of $L[i]$. – Yuval Filmus Jun 1 '18 at 16:37