[FOM] Crystal Ball Theory/more

[Harvey Friedman]

The importance of the Crystal Ball Theory posting,

http://www.cs.nyu.edu/pipermail/fom/2004-February/007983.html

as I see it, is as follows. Attacks on, and defense of, the ideas there
will, in my opinion, involve lots and lots of hard, deep, and highly
fruitful analysis, both conceptually and technically.

Here are my thoughts.

1. I am convinced that trying to take consistency statements like Con(ZFC +
measurable cardinals) or Con(ZFC + rank into itself), Con(ZF + inaccessible
rank into itself), etc., and force them into smaller and smaller Turing
machines not halting, with demonstrable equivalence in an extremely weak
system, is an open ended project, in the practical sense, that will create a
virtually unlimited opportunity, in the practical sense, for a stream of
ever and ever deeper mathematical ideas. Ideas that could come from
unexpected sources, ideas that could have independent deep ramifications,
ideas that -- well who knows what to expect. The benchmark is completely
clear - how many quadruples? At the very least, deep ideas about set theory
and large cardinals, but probably much more diverse deep ideas about, well,
the unexpected. Any branch of mathematics whatsoever might prove useful, or
even crucial, here. Whereas, we don't think that "any branch of mathematics"
might be useful in logic problems, normally. This is different.

2. Of course 1 becomes very difficult, as the sizes go down. Since the
number of quadruples involved are likely to stay at least around 100 for the
forseeable future (I have not yet played around with this), there will be a
large number of levels of difficulty in beating any current record for, say,
Con(ZFC), Con(ZFC + measurable cardinal), Con(ZFC + rank into itself),
Con(ZF + inaccessible rank into itself), etc. So such a contest will be
'perfect', at first with records broken with some frequency, and then with
records broken with less frequency. If the numbers were tiny, there would be
very little activity at the outset, which would be discouraging at the most
crucial time.

3. A number of deep conceptual issues arise also from the Crystal Ball
Theory posting. One obvious one is the following.

We know what we mean by, say, giving such a TM representation of Con(ZFC) or
Con(ZFC + a measurable cardinal), Con(ZFC + rank into itself), Con(ZF +
inaccessible rank into itself), as indicated above.

However, what do we mean by, say, giving such a TM representation of the
Riemann Hypothesis?

The problem is, what happens when RH is settled in a weak system, as we
expect to happen within 100 years? Many people in the know are more
optimistic than that.

What, then, is the significance of the numbers computed concerning TM
representations of RH?

People will have given TM's whose nonhalting was proved to be equivalent to
RH in a weak system. However, as soon as one has a proof of RH in a weak
system, one can use the TM with zero quadruples (or one quadruple, depending
on the exact setup).

There are a number of interesting ways to answer this, some leading to deep
matters. The most obvious really deep matter is this. What sense can be give
to the idea that a given proof of something does not have anything to do
with something quite different?

I.e., we believe that the proof of the 4 color theorem has "nothing to do
with RH". What does that mean?

And after you develop a good deep theory surrounding the previous paragraph,
then is it good enough to apply to the issue at hand? That the proofs of
these equivalences of RH with TM nonhaltings, have nothing to do with RH?

And, of course, there is the difficulty that these proofs of these
equivalences of RH with TM nonhaltings, DO in fact have something to do with
RH, because even to get RH in Pi01 form requires some knowledge about RH.

4. There is an extremely important, quite robust constant, in my opinion,
call it c, which is on the outer edge of the maximum number of quadruples it
takes to represent anything that humans find reasonably natural that can be
represented as TM halting - i.e., that can be put into Pi01 form.

There are serious difficulties in becoming clearer about what this constant
c is, conceptually, as indicated in considerations such as were discussed
in 3 above. Nevertheless, we get the feeling that we know what we mean by
this c. 

There is of course the problem of giving some sense to just how robust this
c is. 

There is also the following fascinating question. By various contests, we
can in fact determine a reasonable value for c - within the present
mathematical power that the human race has brought to these contests. Call
this the "apparent" value of c.

But how will the "apparent" value of c change over time? How does it change
over time compare to the numbers one gets in the specialized contests for
particular statements?

I.e., can we expect breakthroughs in the TM representations of particular
key statements to result in related breakthroughs for other key statements?
I think the answer is probably a qualified yes.

5. Number 4 above leads to the following question. What are the fundamental
constants of logic? Are there any that we can define better than the
fundamental constant alluded to in 4?

This is a question I have thought about. I have written down previously, a
rigorous account of predicate calculus with abbreviation power. There is a
rigorous notion of depth of a definition of a mathematical concept - using
set theory at the bottom.

What are the observed depths of definitions of mathematical notions from the
mathematical literature?

What are the actual least depths for definitions of mathematical notions
from the mathematical literature?

I have started to gather some serious amount of data regarding the first.
Regarding the second, it appears that making such computations is extremely
difficult. One has a contest oriented situation again, like the TM
representations in Crystal Ball Theory.

6. I now come to the various deep questions - conceptually and technically -
that arise when attempting to make "proofs" that the Crystal Ball from the
hyperaliens is "the real thing" and that the information gleaned from its
use is "proved". 

I believe very strongly that rather subtle probabilistic arguments combined
with rather clever TMs, will show, in various "rigorous" senses, that the
Crystal Ball is the real thing (provided it is in fact the real thing).

There is the idea that the hyperaliens have monitored us for what we will
ask and what we know, and have fooled us.

The big problem is to refute this paranoia.

One must randomize the sets of quadruples that are thrown to the Crystal
Ball, in such a way that we become convinced that the Crystal Ball is the
real thing. 

How to do this, and how to justify such a method as "rigorous" conceptually,
is rather deep - but I think very doable. And definitely looks to be a
rather fundamental problem, probably related to a lot of other matters in
unexpected ways. 

One might also take a more "local" approach. One may wish to do this kind of
deep analysis, using randomness and probabilistic arguments, surrounding
only variants of a particular statement we are interested in. Say Con(ZFC),
Con(ZFC + measurable), Con(ZFC + rank into itself), Con(ZF + inaccessible
rank into itself). 

On 3/14/04 6:54 PM, "Timothy Y. Chow" <tchow at alum.mit.edu> wrote:

> Harvey Friedman <friedman at math.ohio-state.edu> wrote:
>> These experiments are done on the device as a "black box" with
>> absolutely no understanding whatsoever of its internal mechanism.
>> 
>> I claim that we would then obtain a "proof" that Goldbach conjecture is
>> false, that is not as convincing as one would hope, but substantially
>> more convincing than any knowledge that we presently have in the
>> sciences and engineering outside mathematics.
> 
> I don't directly disagree with this, but I don't really see what this has
> to do with hypercomputation per se.  We have "proofs" of this kind already
> of all kinds of mathematical statements---e.g., that such-and-such a
> probabilistic prime is really a prime, that the next 10^10 zeroes of the
> Riemann zeta function that we bother to compute will lie on the critical
> line, that ZFC is consistent, and so on.  The hyperaliens do not seem to
> add anything qualitatively different to this situation.

It has everything to do with how we recognize that in fact a weak
hypercomputer that has been built does in fact work. This is important for
the discussion whether we have built it or whether aliens have secretly
built it, providiing no information about its construction.

In fact, it would probably be even more convincing if we had worked out a
prior method of "proving" the correctness of a given weak hypercomputer,
without being aware at all of its inner workings. We would apply this method
to a given weak hypercomputer that was later built by humans, and be happy
to know that the method could be applied without prejudice.

Here are some more specific comments on what you wrote.

There is a formalizable "rigor" to these prime recognition arguments. This
"rigor" is perhaps not at the level that it could be in a more logically
systematic treatment of probabilistic arguments from a focused f.o.m.
perspective, but this can certainly be done quite well. I am less sure about
the "next 10^10 zeroes of the Riemann zeta function" case, but I may well be
equally convinced of this when I look at the relevant work.

However, this has nothing to do with the ZFC case, where one seems to have
nothing analogous. If someone insists that this is even more rigorous
because the cumulative hierarchy obviously satisfies ZFC, then one just ups
the ante to the highest large cardinals with choice, or even "ZF +
inaccessible rank into itself", and this generally puts an end to such
uncontrolled tendencies.

The big problem is to turn the information gleaned from the Crystal Ball
into a proof that is as rigorous as, say, the probabilistic prime proofs.
This might well be quite hard and deep, but totally doable - and worthwhile.

> Let me put it this way.  Soon after Harvey Friedman's aliens show up,
> another group of extraterrestrials arrives.  Seeing the situation, the
> ET's roll their eyes and tell us, "I see you've met the hyperaliens.
> Don't believe a word they say; they're charlatans.  They've monitored
> your mathematical progress and they know exactly what you've proved so
> far and all the things you're capable of verifying with your limited
> resources, and have hardcoded the `right' answers into their black box.
> We made the mistake of forking over lots of cash for one of their black
> boxes, and our scientists analyzed it and found that it's no better than
> snake oil.  You'd be much better off using one of *our* computers, which
> is just a conventional computer but 10^100 times more powerful than
> yours.  We don't claim to break the Church-Turing barrier, but your
> confidence will be a lot better founded if you base it on our machine
> rather than theirs."

The idea is to refute that it is snake oil. For one, we can ask the new
group of aliens to come up with a TM that refutes the Crystal Ball left by
the original group of aliens. They should be able to do that, if it is
indeed snake oil.

Also, we want to prove that if any second group comes along with their
competing Crystal Ball, then after we do our testing, we know that the two
Crystal Balls will never disagree about any TM we put to them.
> 
> I see no real difference between choosing to believe the aliens versus
> choosing to believe the ET's.  So this seems orthogonal to the issue of
> hypercomputation.
> 

If they both pass our tests, we will "know" that they are both legitimate,
and in particular that they cannot disagree with each other.

Harvey Friedman