[FOM] Re: Crystal Ball Theory/more

[Harvey Friedman]

On 3/15/04 2:40 PM, "Timothy Y. Chow" <tchow at alum.mit.edu> wrote:

> 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.

In the case of the consistently of strong set theories rather than RH,
getting the smaller and smaller TM representations surely will involve
making extremely deep new connections between set theory and simple
mathematical constructions. An outcome would surely be some new kinds of
independence results in the finite.
 
> 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.

Here is one possible scenario which I will state in a very strong form, in
order to be more convincing than otherwise.

NOTE: For the purpose of this scenario, let's assume that the Crystal Ball
accepts <= 200 quadruples.

**********************************

1. After finding the Crystal Ball, the US Government has set up an extensive
Crystal Ball testing program. In consultation with mathematicians thorughout
the world, a Pi01 formula P(n) has been designated as the Crystal Ball
testing predicate. 

2. P has been simulated on a Turing machine with few enough quadruples so
that for any 100 bit positive integer n, P(n) can be simulated by a TM with
at most 200 quadruples.

2. Mathematicians all over the world have enthusiastically endorsed the
choice of P(n). They generally feel that no matter what positive integer n
is chosen, then P is so interesting, that there will be a lot of top people
willing to work on the special case P(n).

3. Over a period of many years, 100 bit numbers n have been randomly
selected and prizes have been posted for determining the truth value of
P(n). The average time needed for valid claims to these prizes is about 100
years. There have been about 100 trials, and all prizes have been claimed.

4. In all cases, the determination of the truth values, even if on the
Sigma01 side, have been incredibly deep, involving much of the most
original, deep, and complicated mathematics ever done on Earth.

5. In particular, on the Sigma01 side, lower bounds have also been given for
the least possible values of the existential quantifiers. These have all
been higher than the 100-th Ackerman number.

6. The Crystal Ball has been tested on all of the P(n) that have been used
in the Crystal Ball testing program. The Crystal Ball gives the truth values
correctly.

7. "Therefore", the Crystal Ball is correct - at least with regard to
statements of the form P(n), where n is a 100 bit integer.

8. This leads to the problem of just how to create such P's that cover more
and more of what we want to know. We can't just take something like

P(x) iff x codes a small TM that never halts

because presumably this is not "hard" in any relevant sense, for most x.

**************

Note that we can add an additional piece of the story:

***It is known that there is no circuit in various senses from theoretical
computer science, that correctly determines the truth values of randomly
selected  P(n), where n is a 100 bit number, that would fit into the Milky
Way Galaxy.***

Now the story also seems to provide a "proof" that human intelligence goes
well beyond any deterministic computational model, and perhaps more.

That startling conclusion follows just from *** and 3.

> 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.  

I am not sure about what our point of disagreement is. But I agree that it
would be a major advance to know that there is no proof of a contradiction
from ZFC + MC is less than 10^100 steps, under a reasonable formulation of
predicate calculus.

Harvey Friedman