[FOM] Re: Crystal Ball Theory/more

[Timothy Y. Chow]

Thanks to Harvey Friedman for clarifying the Crystal Ball Theory.  I now
understand it much better.  The "fundamental constant c" makes a lot of 
sense.  I would state it this way: To significantly reduce the number of
quadruples needed for, say, the Riemann Hypothesis would most likely 
require a new insight into RH---e.g., proving on the basis of a weak 
system that RH is equivalent to some other very different-looking 
statement.  The constant c would provide a measure of progress ("How
close are we to proving RH [in a weak theory]?") and, if we are lucky, 
direct study of c might yield such new insights.

The idea of probabilistically verifying the Crystal Ball is also
interesting, but I have to say that I still don't see how it would
distinguish the hyperaliens from the ET's.  If we put a bound on the
number of steps of the TM---i.e., we ask not "Does this TM halt?" but
"Does this TM halt in 10^100 steps?"---then I can see how the methods
of probabilistically checkable proofs can be used to distinguish between
impostors and truth-tellers, with high probability and very little
computational effort on our part.  We wouldn't need to know how the
black box works and yet we could exploit its superior computational
power with negligible fear of being duped.

However, all this shows is that the limit of our ability to probe is a
larger finite number than one might naively think.  But it's still some
finite limit.  That is, it doesn't seem possible to me for there to be a
"PCP theorem for undecidable sets" that enables a prover to provide a
*finite* certificate of the (unbounded) non-halting of a TM that a
verifier could use to find impostors with high probability.  The ET's and
the hyperaliens would still look indistinguishable to us.

Perhaps you don't disagree with this, and are mainly trying to point out
that it would still be a major advance in our understanding to know that
(for example) there is no proof of a contradiction from ZF+MC in less than
10^100 steps.  So even if an alleged hypercomputer does break down at some
point, it doesn't matter---we can still exploit its power as far as it
goes, and we can tell (with high probability) how far it does in fact go.  
In that case I have no bone to pick, other than to say that I think that
these considerations belong squarely within the realm of classical
computation and aren't part of the subject of "hypercomputation" per se.

Tim