NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/sci/math/10229

Text File | 1992-08-13 | 3.7 KB | 84 lines

Newsgroups: sci.math
Path: sparky!uunet!snorkelwacker.mit.edu!galois!riesz!jbaez
From: [e-mail] (John C. Baez)
Subject: Re: Puzzles
Message-ID: <[e-mail]>
Sender: [e-mail]
Nntp-Posting-Host: riesz
Organization: MIT Department of Mathematics, Cambridge, MA
References: <[e-mail]>
Date: Thu, 13 Aug 92 17:25:31 GMT
Lines: 71

In article <[e-mail]> [e-mail] (Bill Taylor) writes:

>[A-P] (1) it is provable that "for almost all n, P(n)".
>      (2) for any particular N, it is not provable that "P(N)".
>
>In this case, P(n) is the statement that n cannot be produced by a program
>of length <= E.  E is unspecified, but a value can be calculated (in principle).
>Now my first reaction to this meta-theorem is that it's clearly not true
>unless the "any particular N" in (2) is a bit more closely specified.

Sorry, not so.  It's really true that for ALL N, it is not provable that
P(N), even though P(N) is true for all but finitely many N.

>For instance, it follows from (1) that we can define a unique number M, by
>M = smallest positive integer requiring a program of length > E.
>
>Now this (unambiguously defined) M  satisfies P, (by definition).

That's true.  However, it's not PROVABLY true within the system in
question (say ZFC for example).  Of course the value of E which works
must depend on the formal system in question as well as the computer
language in question. For more powerful formal systems E must
be taken to be larger.

>Anyway, I would also like to see an answer to
>
>[Question 2] What is a good value for E ?
>~~~~~~~~(I don't recall seeing an answer posted; I can't even guess at it.)

Of course E depends on the programming language in question and the
formal system in question.  Let's take the canonical choices - C and
ZFC.  :-)

Some kind soul pointed out that one needn't write a program in C that
can accept and run C programs to get the job done. Let me give away the
answer to the problem (how to prove the "almost-paradox" A-P above).

One need only write
a program that looks through statements in ZFC to find those of the form
"N cannot be printed by a program in C of length < E", and check
which are provable in ZFC.  If it finds one, the program should print
out the number N.  Note that the length of this program is about K + ln
E, since it takes ln E digits to write the number E in the program, and
K (some number) to write the rest of the stuff.  Thus if there are any
numbers N which can be proved in ZFC not be printed by any program of
length < E, our program will find them and print them.  If our program
is of length < E this will be a contradiction!  So if

K + ln E < E

there cannot be any numbers for which one can prove in ZFC that no
program of length < E prints them out.

This gives an explicit bound on E once we know K.  That is, about
how long a C program does it take to do the stuff I mentioned.  A decent
hacker should be able to estimate it or even write the darn program.
(One may prefer to use a simpler language than C.)

The same kind soul gave an estimate for K.  Let me give a ridiculously
bad upper-bound/guess that K is 10^9.  (I'm sure it's a lot less.)
Then I bet that E = 10^9 + 1000 satisfies the inequality above.  It
would be nice to get better lower bounds on E because it is an
interesting "fundamental constant of nature" (even though it depends on
a choice of axiom system and programming language).

>[Question 3] Are there any "more natural" properties P, to which [A-P] applies ?
>~~~~~~~~~~~  i.e. more traditionally mathematical than the logico-computing
>                  property P given above.

Probably.