[FOM] Graham's Number, Re: 271:Clarification of Smith Article
aberdein at fit.edu
Tue Mar 28 16:08:28 EST 2006
On 27 Mar 2006, at 4:42 pm, Andreas Weiermann wrote:
> It might be of some general interest to see whether the lower bound in
> H. Friedman's Theorem 2 (cited below) is larger
> than the Graham number holding the world record for
> a natural number appearing in a mathematical proof.
>> THEOREM 2. Theorem 1 can be proved in strictly finite mathematics.
>> any such proof in ACA_0 + Pi12-BI must use at least 2^ symbols.
>> Here 2^ is an exponential stack of 2's of height 1000.
The Graham number is much, much larger than this.
The Knuth up arrow, here written as ^, is defined by:
a ^ n = a to the n-th power
a ^^ n = an exponential stack of a's of height n.
a [k arrows] n = a [k-1 arrows] stack of a's of height n.
So Friedman's number could be written as 2^^1000.
Graham's number has been stated in several different ways, some of them
larger than others. When I asked him, the one which Ron Graham himself
endorsed was Martin Gardner's version. He has Graham's number = G(63),
where G(0) = 3^^^^3 and G(n) = 3^...^3 with G(n-1) arrows. Even G(0)
would be vastly larger than 2^^1000.
I have seen some much smaller statements of Graham's number, including
3^^^^^^43 and 3^...^3 with 64 ^s, which I suspect are misstatements.
Each of these numbers are between G(0) and G(1), and therefore also
larger than Friedman's number.
A n d r e w A b e r d e i n, P h. D.
Humanities and Communication,
Florida Institute of Technology,
Melbourne, Florida 32901-6975, U.S.A.
[+1] (321) 674 8368 http://my.fit.edu/~aberdein/
More information about the FOM