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


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?

  • $\begingroup$ What do you think? Have you tried solving the halting problem using CGP as an oracle? $\endgroup$ – Yuval Filmus May 30 '18 at 13:41
  • $\begingroup$ I mean, can I solve halting problem with CGP function? $\endgroup$ – smrt28 May 30 '18 at 13:46
  • $\begingroup$ Have you tried reducing the halting problem to CGP? $\endgroup$ – Yuval Filmus May 30 '18 at 13:47
  • $\begingroup$ I tried, no success. $\endgroup$ – smrt28 May 30 '18 at 13:57
  • 1
    $\begingroup$ See Comment #12 in your link. $\endgroup$ – 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.

  • $\begingroup$ I'm not sure about the proof syntax. What does L[i] mean? $\endgroup$ – smrt28 Jun 1 '18 at 14:09
  • 1
    $\begingroup$ 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]$. $\endgroup$ – Yuval Filmus Jun 1 '18 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.