[FOM] Platonism and Formalism

[Harvey Friedman]

Reply to Franzen. 

On 9/27/03 9:14 PM, "Torkel Franzen" <torkel at sm.luth.se> wrote:

> In everyday life, and in ordinary reasoning, we take many things for
> granted. It is open to you, or to anybody, to question what we take
> for granted, but such questioning will be of little interest (to most
> people) as long as it does not provide any workable and
> fruitful alternatives. In the present case, a metaphysically sensitive
> person will reject the idea that "the number"
> 
>     25195908475657893494027183240048398571429282126204
>     03202777713783604366202070759555626401852588078440
>     69182906412495150821892985591491761845028084891200
>     72844992687392807287776735971418347270261896375014
>     97182469116507761337985909570009733045974880842840
>     17974291006424586918171951187461215151726546322822
>     16869987549182422433637259085141865462043576798423
>     38718477444792073993423658482382428119816381501067
>     48104516603773060562016196762561338441436038339044
>     14952634432190114657544454178424020924616515723350
>     77870774981712577246796292638635637328991215483143
>     81678998850404453640235273819513786365643912120103
>     97122822120720357
> 
> (which is the RSA $200,000 challenge number) has a determinate
> factorization which we don't as yet know, and perhaps will never
> know. Such metaphysical sensitivity is fine, but it will not have any
> impact on people's thinking unless it can be used in some illuminating
> alternative explanation of the relation or correlation between theory
> and practice in computation. Ethereal metaphysical misgivings about
> the "mysticism" involved in ordinary thinking about numbers are in
> themselves just unworldly complaints divorced from practical
> intellectual concerns. Since you mention absolute time, let us note
> that Einstein spent no time or effort arguing about the mystical
> character of the idea of absolute time.
> 

This is a very interesting example which Franzen uses to put certain
formalist viewpoints on the defensive in a particularly effective and
interesting way.

I didn't know about these challenge numbers, and so I looked up the
background on the RSA website at

http://www.rsasecurity.com/rsalabs/challenges/factoring/faq.html

As stated on that page, the above is a 2048 digit base 2 integer converted
to base 10. It was generated by the following process (modified in minor
ways from what was described on that page, for clarity):

i) attaching a standard HARDWARE random number generator to a PC;
ii) the PC runs a standard algorithm that randomly generates primes
(probably for this purpose, two 1024 digit base 2 primes), that is well
known to be foolproof (although the running time has a tiny probability of
being huge or infinite, but this is certified not to have happened);
iii) the PC then multiplies the two prime numbers and converts them to base
10;
iv) after the attached hardware random number generator finishes its work,
it is physically detached from the PC, and physically destroyed.

So we "know" that the above number, that resulted from this process, is in
fact the product of two primes. However, by the way RSA generated this
number, with i)-iv), we "see" that nobody knows just what these two primes
are. 

This whole interesting business, which RSA set up to help it benchmark just
how vulnerable their crypto products are, raises interesting foundational
problems. E.g., 

1. What kind of knowledge do we have that the above number is a product of
two primes? There are issues about physical processes, physical destruction,
physical randomness, correctness of software, correctness of highly
nontrivial mathematical theorems, cleanrooms, witnesses, human perception,
human communication, etc.

2. How can we rigorously formulate a statement, which might be true or might
not be true, that "no intelligent being will ever know what the factors of
this number are"? Or perhaps better stated as "the probability that some
intelligent being will ever know what the factors of this number are in x
years is at most y".

Of course, even if we  understand 1,2, we are in no position to actually
prove such statements (as in 2), as they immediately imply that there are no
"good" algorithms for NP complete problems, something we are not anywhere
near being able to prove. Also, there are well known number theorists who
think that there is a good chance that factoring is easy, at least on
average.

I think that with our present tools in f.o.m., as well as what is understood
in computer science, serious progress on 1,2 can be made now. I have some
ideas about this as I speak.

But my main point is not any ideas I have about this. It is about how this
is typical of the outer reaches of f.o.m.

There are countless interesting and important foundational situations that
are currently not covered by f.o.m. How could this be otherwise?

Also, with regard to many issues that contemporary f.o.m. is dealing with
quite well: still one has only scratched the surface of the surface of the
surface of the surface of them.

Since f.o.m. is amazingly fertile with constantly expanding scope, one can
stay conservatively within the main line, and still be dealing constantly
with matters of the highest general intellectual interest.

Or one can instead, or in addition, look to expand its scope in many many
independent directions, again dealing constantly with matters of the highest
general intellectual interest.

Both of these approaches are very fruitful. If anybody has some new
promising ideas related to f.o.m. - especially with some preliminary results
or imaginatively formulated questions - then they should present them online
on the FOM. It goes without saying that some major researchers in f.o.m.
will investigate them, if they see merit in them.

Harvey Friedman