Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



GRAHAM'S NUMBER AND RAPIDLY GROWING FUNCTIONS
Posted:
Mar 4, 2002 1:03 PM


I first learned about Graham's number in Craig Smorynski's article
"Some rapidly growing functions", The Mathematical Intelligencer 2 (1980), 149154.
Here is how Smorynski defines Graham's number (p. 149) >>>
Let N be the natural numbers. First, we define K: N^2 > N.
K(0,n) = n^n K(m+1, n) = K(m, K(m,n))
Next, we define G: N > N using K.
G(0) = K(3,3) G(n+1) = K(G(n), 3)
Smorynski then defines Graham's number to be G(64).
However, this definition gives a vastly smaller number than what I've seen in other places. In fact, as I'll show below, Smorynski's function G(n) has the growth rate of a constant base with a linear hypertetrated exponent, whereas the function G(n) that other sources define has a growth rate associated with the (w+1)'st level of the GrzegorczykWainer hierarchy (i.e. a growth rate associated with 1'st level iterations of the Ackermann function).
CONTENTS
0. WARMING UP  SOME ORDINARY LARGE NUMBERS 1. TETRATION AND HYPERTETRATION 2. SMORYNSKI'S G(n) IS ESSENTIALLY HYPERTETRATION 3. THE GRZEGORCZYKWAINER HIERARCHY 4. HOW BIG IS GRAHAM'S NUMBER? 5. CONWAY'S CHAINED ARROW NOTATION 6. SOME REFERENCES FOR LARGE NUMBERS
Dave L. Renfro
***************************************** *****************************************
0. WARMING UP  SOME ORDINARY LARGE NUMBERS
4 x 10^14  This many bacteria weigh about a pound.
1.6 x 10^18  Number of inches to Alpha Centauri (nearest star).
2 X 10^22  The aggregate impact of this many fleas falling 1 cm at the Earth's surface will equal the energy released in a 20 kiloton atomic bomb (size dropped during WW II).
6 x 10^23  Avogadro's number.
5 x 10^(67)  Gravitational force (in Newtons) between two electrons that are 1 cm apart.
8 x 10^67  Number of ways to shuffle a deck of cards.
10^80  Number of elementary particles in the known universe.
10^(200)  The probability that an electron in a 1s orbital of a hydrogen atom is 5 nanometers from the nucleus.
10^(1080)  Probability of flipping a coin once a second for an hour and getting all heads.
10^(10^8)  Probability of flipping a coin once a second for 100 years and getting all heads. 10^(10^8) is also the number of terms of the divergent series SUM(k=2 to infinity) [k*ln(k)]^(1) that are needed for a partial sum to exceed 20.
10^(5.2 X 10^18)  Using nonrelativistic quantum mechanics, this is the probability that an electron in a 1s orbital of a hydrogen atom is 240,000 miles from the nucleus (distance to the Moon).
10^(10^36)  Probability given by life insurance tables that someone will live 1000 years. [This appears on page 1 of Volume I of William Feller's text "Probability Theory and its Applications".]
Using nonrelativistic quantum mechanics, this is also the probability that an electron in a 1s orbital of a hydrogen atom is 10 billion light years away from the nucleus.
10^(10^50)  Estimate by G. H. Hardy of the number of possible chess games. However, this is probably much too high. I think the number is around 10^70. See the other estimates (for 40 move games) given at http://mathworld.wolfram.com/Chess.html
10^(10^93)  Using nonrelativistic quantum mechanics, the probability that every electron in all the hydrogen atoms in the sun are 10 billion light years away is more than this. [This number is [10^(10^36)]^n, where n = 10^57 is the mass of the sun divided by the mass of a hydrogen atom. ("More than", because the sun is 91% hydrogen and I would imagine that very few of these electrons are in the lowest energy 1s orbital.)]
10^(10^100)  One googleplex.
10^(9.9566 x 10^101)  The factorial of a google.
10^(10^125)  Upper bound on the number of known universes at any specific time. This is (10^80)^(10^123), the number of ways the 10^80 particles in our universe can be placed into the 10^123 particlesized locations in our universe, with repetitions allowed (i.e. more than one particle can be put into a single location).
10^(10^166)  Upper bound on the number of 10 billion year long "universes". This is [10^(10^125)]^(10^41), the number of sequences of length 10^41 (the number of 10^(24) second intervals in 10 billion years) each of whose terms can be any of the 10^(10^125) arrangements of particles in the known universe. This is an upper bound on the number of branches for the known universe, for 10 billion years, in the "many worlds interpretation of quantum mechanics". This is also equivalent to the number of (10^41)move "universal chess games" in which there are 10^80 *distinct* chess pieces and any number of these chess pieces can relocate to any of 10^123 locations during each move (and more than one chess piece can occupy each location).
10^(10^(2,000,000))  The number of terms of the divergent series SUM(k=2 to infinity) [k*ln(k)*ln(ln k)]^(1) that are needed for a partial sum to exceed 20.
10^(10^(10^34))  Skewes number. http://mathworld.wolfram.com/SkewesNumber.html http://www.math.niu.edu/~rusin/knownmath/97/skewes http://www.math.niu.edu/~rusin/knownmath/99/primedistr
10^(10^(10^41))  The number of terms of the divergent series SUM(k=2 to infinity) [k*ln(k)*ln(ln k)]^(1) that are needed for a partial sum to exceed 100.
***************************************** *****************************************
1. TETRATION AND HYPERTETRATION
Since multiplication is repeated addition and exponentiation is repeated multiplication, it is natural to consider continuing this process. To see how to carry out such a continuation, we formalize this observation about multiplication and exponentiation as a pair of inductive statements.
x*(y+1) = x + (x*y) multiplication
x^(y+1) = x * (x^y) exponentiation
Because + and * are commutative, the order we used on the right hand sides of these equations does not matter. However, the higher order operations wind up being neither commutative nor associative. The definitions given below conform to the standard practice of evaluating exponent and hyperexponent towers in a topdown manner.
x^^1 = x x^^(y+1) = x ^ (x^^y) tetration
x^^^1 = x x^^^(y+1) = x ^^ (x^^^y) hypertetration
For each of ^^ and ^^^, I'll refer to the left input number as the "base" and the right input number as the "exponent".
**** EXAMPLES ****
3^^3 = 3^3^3 = 3^27 = 7,625,597,484,987 [Has 13 digits.]
3^^4 = 3^(3^^3) = 3^(3^27) = 3^(7,625,597,484,987) [Has about 8.4 x 10^12 digits.]
3^^5 = 3^(3^^4) [If n is the number of digits that 3^^5 has, then n has about 8.4 x 10^12 digits.]
10,000! has 35,660 digits, which in turn has 5 digits. The number of digits in the number of digits of n^^n is 2 for n=3, 154 for n=4, and approximately 1.3 x 10^2184 for n=5.
Let *(n,k) be the kiterate of the number of digits that n has. Thus, *(5^^5, 2) is about 1.3 x 10^2184, *(5^^5, 3) = 2185, *(5^^5, 4) = 4, and *(5^5, 5) = 1. Let @(n) be the smallest number k such that *(n,k) = 1. Then @(5^^5) = 5. For constant i, @(i^^n) is essentially n. [Equal to n for small values of i, asymptotic (in a strong way) to n for any i.] The values for i = 10 are particularly easy to calculate >>>
@(10^^2) = 2 @(10^^3) = 3 @(10^^4) = 4 @(10^^5) = 5 * * *
Unlike the situation for tetrated growth (above), hypertetrated growth is virtually unaffected by an application of our @slowdown operation >>>
@(10^^^2) = 10 = 10^^^1 @(10^^^3) = 10^^10 = 10^^^2 @(10^^^4) = 10^^(10^^10) = 10^^^3 @(10^^^5) = 10^^(10^^^3) = 10^^^4
[[ An analogous situation occurs when applying a digit count to the values of 10^^n. ]]
To successfully slow down ^^^growth, we would have to count the number of applications of the @operation that are needed to reach 1. These considerations should indicate the vast size of the numbers we're dealing with, to say nothing of the numbers obtainable by the still higherorder operations that occur in Sections 3 and 4 below.
LEMMA: Let i and j be fixed. Then for each n > 2, (n^^i)^^j is between n^^(i+j1) and n^^(i+j).
This is easy to see informally by considering a few representative examples written in ^tower notation. You'll find that the value of (n^^i)^^j is much closer to n^^(i+j1) than it is to n^^(i+j). However, this difference will be unimportant when we begin looking at Smorynski's function G(n).
***************************************** *****************************************
2. SMORYNSKI'S G(n) IS ESSENTIALLY HYPERTETRATION
We recall the definition of Smorynski's K(m,n):
K(0,n) = n^n K(m+1, n) = K(m, K(m,n))
First, let's get some upper and lower bounds on K(m,n) that are easy to work with.
K(1,n) = K(0, K(0,n)) = K(0, n^n) = (n^n)^(n^n) Thus, K(1,n) is between n^^3 and n^^4.
K(2,n) = K(1, K(1,n)), and so K(2,n) is between K(1, n^^3) and K(1, n^^4). Hence, K(2,n) is between (n^^3)^^3 and (n^^4)^^4. Using the Lemma just above, we find that K(2,n) is between n^^5 and n^^8.
Continuing in this manner, it is easy to see that
K(3,n) is between n^^9 and n^^16
and K(4,n) is between n^^17 and n^^32.
In general, K(m,n) is between n ^^ (2^m + 1) and n ^^ 2^(m+1).
Hence, for m > 1 and being very generous, we have
K(m,3) is between 2^^(2^m) and 3^^(3^m) K(m,3) is between 2^^m and 3^^(3^^m).
Now let's look at Smorynski's function G(n) using these last (and most generous) bounds on K(m,3). Recall that G(n) is defined by
G(0) = K(3,3) G(n+1) = K(G(n), 3).
G(0) = K(3,3) is between 2^^2 = 2^^^2 and 3^^(3^^3) = 3^^^3.
G(1) = K(G(0), 3) is between 2^^G(0) and 3^^(3^^G(0)). Hence, G(1) is between 2^^(2^^^2) = 2^^^3 and 3^^(3^^(3^^^3)) = 3^^(3^^^4) = 3^^^5.
In the same way it is easy to see that G(2) is between 2^^^4 and 3^^^7. Note that each succeeding application of the lower bound for K(m,3) increases the ^^tower length by 1 (i.e. adds one to the ^^^exponent) and each succeeding application of the upper bound for K(m,3) increases the ^^tower length by 2 (i.e. adds two to the ^^^exponent). Hence, using the bounds that we've already found, it follows that G(n) is between 2^^^(n+2) and 3^^^(2n+3).
From this we conclude >>>
** Smorynski's function G(n) has the growth rate of a constant base with a linear ^^^exponent.
** Smorynski's definition of Graham's number results in a number that is between 2^^^66 and 3^^^131.
***************************************** *****************************************
3. THE GRZEGORCZYKWAINER HIERARCHY
For operations beyond ^^ and ^^^, it becomes increasingly necessary to have a notation that includes the operation level as a numerical parameter.
After some experimentation I found the following notation reasonably convenient and readable for ASCII format, especially when ordinals are used for the operation level.
b#(x,y) will represent the b'th order operation evaluated at (x,y) = (base, exponent).
1#(x,y) = x+y
2#(x,y) = x*y
3#(x,y) = x^y
4#(x,y) = x^^y
5#(x,y) = x^^^y
We continue inductively by defining
(n+1) # (x, y+1) = n # (x, (n+1)#(x,y)).
**** REMARKS ****
** Knuth's "x nupperarrows y" is equal to (n+2) # (x,y).
** Robert P. Munafo's "hy(x,n,y)" is equal to n#(x,y). See [26].
** A(x,y) = [x # (2, y+3)]  3, where A(x,y) is Ackermann's function. See [22] and [39].
We can diagonalize ourselves past all of these operations by defining
w # (x,y) = y # (x,y).
In this equation 'w' is the lower case Greek letter "omega". I will be using ordinals to denote the operation levels. However, because this sometimes causes confusion, I need to be explicit about a couple of things.
First, no matter what (constructively obtainable) ordinal we use for 'b', the expression b#(x,y) will be a natural number when x and y are natural numbers. Second, when 'b' is a limit ordinal, this notion depends on a specific fundamental sequence associated with 'b' (i.e. a sequence of ordinals smaller than 'b' whose limit is 'b'), and not just on 'b' itself. For ordinals less than Cantor's epsilon_0 it is fairly obvious what to use for the fundamental sequences. Although the assignments can be defined rigorously, a few examples will suffice for us.
[[ NOTE: The ordinal w+w is usually denoted by w*2, but to conform with polynomial notation (which, at least for me, makes it easier to compare their sizes), I'm reversing the order for multiplication. Thus, w+w+w = 3w, (w^5)+(w^5) = 2*w^5, etc. ]]
w = sup{1, 2, 3, ...}
3w = sup{2w+1, 2w+2, 2w+3, ...}
w^2 = sup{w, 2w, 3w, ...}
w^w = sup{w, w^2, w^3, ...}
2*w^w + w^5 = sup{2*w^w + w^4, 2*w^w + 2*w^4, 2*w^w + 3*w^4, ...}
epsilon_0 = sup{w, w^w, w^(w^w), w^(w^(w^w)), ...}
This can be continued for much larger ordinals but, as the ordinals get larger and larger, it becomes increasingly difficult to define "natural" fundamental sequences in a unique way for each limit ordinal. However, up to epsilon_0 is more than enough for our present needs and the situation is very straightforward for this much.
For a nice "picture" of epsilon_0, see
"How to Count Up to the First Epsilon" by Libor Behounek http://www.ff.cuni.cz/~behounek/eps55.htm
Another useful web page is the following excerpt from Rudy Rucker's book INFINITY AND THE MIND
http://www.anselm.edu/homepage/dbanach/infin.htm
Recall that w # (x,y) = y # (x,y). I could have defined this to be x # (x,y). However, it makes more sense to me to diagonalize the pair (operation level, exponent) rather than the pair (operation level, base). In any case, the difference between these choices essentially disappears when we pass to the next operation level.
(w+1) # (x, y+1) = w # (x, (w+1)#(x,y))
(w+2) # (x, y+1) = (w+1) # (x, (w+2)#(x,y))
(w+3) # (x, y+1) = (w+2) # (x, (w+3)#(x,y))
* * *
2w # (x,y) = (w+y) # (x,y)
(2w+1) # (x, y+1) = 2w # (x, (2w+1)#(x,y))
(2w+2) # (x, y+1) = (2w+1) # (x, (2w+2)#(x,y))
(2w+3) # (x, y+1) = (2w+2) # (x, (2w+3)#(x,y))
* * *
3w # (x,y) = (2w+y) # (x,y)
* * *
4w # (x,y) = (3w+y) # (x,y)
* * *
w^2 # (x,y) = (yw) # (x,y)
* * *
w^3 # (x,y) = (w^2 + yw) # (x,y)
* * *
w^w # (x,y) = (w^y) # (x,y)
* * *
To get a handle on these dizzyingly rapid growth rates, note that the 2w'th operation is to the w'th operation (the w'th operation is essentially Ackermann's function) as the w'th operation is to the successor function. Moreover, the 3w'th operation has the same relation to the 2w'th operation. Furthermore, no matter how many times you make an wlevel jump (6 times, googleplex times, 5^^^5 times, 3w # (5,5) times, etc.), you will never reach the growth rate that the w^2 operation represents. Finally, if we extend our concept of "number of times" into the transfinite, and we increase our "step size" from w operations to w^2 operations (thus, one step takes us from the successor operation to the w^2 operation; the next step takes us to the 2*w^2 operation), it will take w^w steps to reach the w^w operation!
It seems inconceivable that anyone would ever have a use for an operation such as w^w # (x,y), let alone for epsilon_0 # (x,y). Nonetheless, the epsilon_0'th operation and several that are WAY WAY past this play important roles in mathematical logic (the specific area being proof theory).
To give you just a tiny peek of what I mean by "WAY WAY past this", note that the ordinal epsilon_0 is defined by taking a supremum of those ordinals that can be described in a finite way using the operations +, *, and ^. One can use the higher order operations above to describe MUCH larger ordinals. The ordinal gamma_0 is, roughly speaking, the supremum of anything that you can obtain in this manner. If you utilize finitely many ordinals less than gamma_0 along with finitely many operations whose levels are less than gamma_0, then the result will be an ordinal less than gamma_0. Unbelievably, the growth rate associated with the gamma_0'th operation plays a pivotal role in proof theory, and there are growth rates of independent interest that are WAY past even this! For more about these matters, see:
(a) The references in Renfro [28].
(b) http://www.dcs.ed.ac.uk/home/pgh/dybjer.html This web page by Peter Hancock lists some "watershed" ordinals and discusses "Various Veblen hierarchies".
(c) http://www.cs.fsu.edu/~levitz/research.html Hilbert Levitz, "Transfinite ordinals and their notations: For the uninitiated", Version 1.1, 8 pages. [A 220 K .ps file for this paper is at the above URL.]
***************************************** *****************************************
4. HOW BIG IS GRAHAM'S NUMBER?
The definitions given in [22], [35], and [39] give rise to a vastly larger number than what Smorynski defines.
Here's what these references say >>>
Let G(0) = 6#(3,3) and continue by letting G(n+1) = G(n)#(3,3).
Then Graham's number is G(63).
[[ Actually, we want "3 G(0)uparrows 3", which is (2+G(0)) # (3,3), but I think you'll agree that it's pointless to worry about adding 2 to numbers like G(0), G(1), etc. ]]
Since 6#(3,3) is 3^^^^3, which is MUCH LARGER than 3^^^131 (note that 3^^^^3 = 3^^^(3^^^3), and 3^^^3 is a tad bit larger than 131), even G(0) is larger than the very generous upper bound that I got for Smorynski's version of Graham's number in Section 2.
I suspect that Smorynski took G(n) to be an iteration of the number of applications of a single arrow operation to 3's, rather than an iteration of the number of arrows to be employed.
Anyway, this much faster growing function G(n) is a 1'st order iteration of the w'th level operation >>>
G(0) is 6#(3,3), which is less than w#(6,6).
G(1) is G(0)#(3,3), which is less than w # (6, w#(6,6))
Clearly, G(63) will involve a nesting of 64 w'th level operations, and so G(63) is somewhere around (w+1)#(3,64). For sure, Graham's number is between (w+1)#(3,63) and (w+1)#(3,65).
[[ Those who might be concerned about the accumulating effect of using "exponents" of G(0), G(1), etc. when the (w+1)'st operation is carried out (as opposed to the consistent use of an "exponent" of 3 in the definition of G(n)) might wish to consider that a difference in just two uparrows (if not just one) completely overwhelms this. ]]
***************************************** *****************************************
5. CONWAY'S CHAINED ARROW NOTATION
I was going to discuss where Conway's chained arrow operations fit into the GrzegorczykWainer Hierarchy, but after looking into the matter a bit I'm still not sure. I *think* 4arrow chains correspond to descriptions under the w^2 operation level, 5arrow chains correspond to descriptions under the w^3 operation level, and so on. However, they might be smaller, with each increment in chain length corresponding to just an wjump in operation level (this would mean that the w^2 operation exceeds the growth rate associated with any finite chained arrow length).
In any case, I'm almost certain that the w^w operation exceeds the growth rate associated with any finite chained arrow length. My guess is that w^w # (n,n) is roughly the same as
n > n > . . . > n (n horizontal arrows),
and that these "diagonalized chained arrow numbers" form a much slower growing sequence than (w^w + 1) # (n,n) does.
I'd be interested, and I'm sure many others would be as well, if anyone can correctly locate Conway's Chained Arrow Operations in the GrzegorczykWainer Hierarchy.
***************************************** *****************************************
6. SOME REFERENCES FOR LARGE NUMBERS
[1] Isaac Asimov, "TFormation", Magazine of Fantasy and Science Fact, August 1963. [Reprinted in ADDING A DIMENSION (1964) and on pp. 4556 of ASIMOV ON NUMBERS (1977).] For some excerpts from this article, see http://www.angelfire.com/scifi/dreamweaver/quotes/qtwriters1.html
[2] G. R. Blakley and I. Borosh, "Knuth's iterated powers", Advances in Math. 34 (1979), 109136.
[3] Wilfried Buchholz and Stan Wainer, "Provably computable functions and the fast growing hierarchy", Contemporary Math. 65 (1987), 179198.
[4] Andrew D Burbanks, "FastGrowing Functions and Unprovable Theorems".
http://www.maths.bris.ac.uk/~maadb/research/seminars/online/fgfut/
[5] E. A. Cichon, "A short proof of two recently discovered independence results using recursion theoretic methods", Proc. Amer. Math. Soc. 87 (1983), 704706.
[6] E. A. Cichon and Stan S. Wainer, "The slowgrowing and the Grzegorczyk hierarchies", J. Symbolic Logic 48 (1983), 399408.
[7] John H. Conway and Richard K. Guy, THE BOOK OF NUMBERS, SpringerVerlag, 1996. [See pp. 5962.]
[8] R. E. Crandall, "The challenge of large numbers", Scientific American 276 (Feb. 1997), 7479. http://www.fortunecity.com/emachines/e11/86/largeno.html http://www.cryptosoft.com/snews/feb97/15029700.htm
[9] D. Van Dantzig, "Is 10^10^10 a finite number?", Dialectica 9 (1955), 273277.
[10] Philip J. Davis, THE LORE OF LARGE NUMBERS, New Mathematical Library, The Mathematical Association of America, 1961. http://www.maa.org/pubs/books/nml06.html
[11] E. C. DennisJones and Stan S. Wainer, "Subrecursive hierarchies via direct limits", pp. 117128 in COMPUTATION AND PROOF THEORY, Lecture Notes in Math. #1104, SpringerVerlag, 1984.
[12] Jean E. Gallier, "What's so special about Kruskal's theorem and the ordinal $\Gamma_0$? A survey of some results in proof theory", Ann. Pure and Appl. Logic 53 (1991), 199260. [For a correction to the proof of theorem 4.5 (line 11 and below on p. 208), see APAL 89 (1997), p. 275.]
[13] George Gamov, ONE, TWO, THREE, ... INFINITY, Viking, 1947. [See chapter 1. But note the incorrect c = $\aleph_0$ identification that slipped in during his discussion of cardinal numbers .]
[14] Martin Gardner, "Mathematical Games", Scientific American 237 (Nov. 1977), 1828.
[15] R. L. Goodstein, "On the restricted ordinal theorem", J. Symbolic Logic 9 (1944), 3341.
[16] Douglas R. Hofstadter, "On Number Numbness", Metamagical Themas column, Scientific America, May 1982. [Reprinted on pp. 115131 of Hofstadter, METAMAGICAL THEMAS, Basic Books, 1985.]
[17] Matt Hudelson, "Extremely Large Numbers".
http://www.sci.wsu.edu/math/faculty/hudelson/moser.html
[18] Edward Kasner and James R. Newman, "New names for old", MATHEMATICS AND THE IMAGINATION, Simon and SSchuster, 1940. [Reprinted on pp. 19962010 of James R. Newman (editor), THE WORLD OF MATHEMATICS, Simon and Schuster, 1956.] [I believe this is the first publication of the terms "google" and "googleplex".]
[19] J. Ketonen and Robert Solovay, "Rapidly growing Ramsey functions", Annals of Math. 113 (1981), 267314.
[20] Laurie Kirby and Jeff Paris, "Accessible independence results for Peano arithmetic", Bull. London Math. Soc. 14 (1982), 285293.
[21] Donald E. Knuth, "Mathematics and computer science: Coping with finiteness", Science 194 (1976), 12351242.
[22] Robert Kosara, "The Ackerman Function".
http://www.kosara.net/thoughts/ackermann.html
[23] J. E. Littlewood, "Large Numbers", Mathematical Gazette 32 #300 (July 1948). [Reprinted on pp. 100113 of Bela Bollobas, LITTLEWOOD'S MISCELLANY, Cambridge Univ. Press, 1986. http://uk.cambridge.org/mathematics/catalogue/052133702X/default.htm
[24] M. H. Lob and Stan S. Wainer, "Hierarchies of numbertheoretic functions I [II]", Archiv fur Math. Logik und Grundlagenforschung 13 (1970), 3951 [97113].
[25] Justin T. Miller, "On the Independence of Goodstein's Theorem", Undergraduate Honors Thesis, University of Arizona, April 2001.
http://www.u.arizona.edu/~miller/thesis/
[26] Robert P. Munafo, "Large Numbers".
http://home.earthlink.net/~mrob/pub/math/largenum.html http://home.earthlink.net/~mrob/pub/math/largenum2.html http://home.earthlink.net/~mrob/pub/math/largenum3.html http://home.earthlink.net/~mrob/pub/math/largenum4.html
[27] K. K. Nambiar, "Ackermann functions and transfinite ordinals", Appl. Math. Lett. 8(6) (1995), 5153.
[28] Dave L. Renfro, Selected sci.math posts on large numbers, rapidly growing functions, and large constructively obtainable ordinals. See the references at the end of
http://mathforum.org/epigone/sci.math/frunyixblou/bu9vfdf6wcev@legacy
[29] Rudy Rucker, INFINITY AND THE MIND, Princeton University Press, 1995. http://pup.princeton.edu/TOCs/c5656.html http://www.anselm.edu/homepage/dbanach/infin.htm
[30] Stephen G. Simpson, "Unprovable theorems and fastgrowing functions", Contemporary Mathematics 65 (1987), 359394.
[31] Craig Smorynski, "Some rapidly growing functions", The Mathematical Intelligencer 2 (197980), 149154. [See pp. 149150 for Graham's number.]
[32] Craig Smorynski, "The varieties of arboreal experience", The Mathematical Intelligencer 4 (1982), 182189. [Reprinted on pp. 381397 of L. A. Harrington et al. (editors), HARVEY FRIEDMAN'S RESEARCH ON THE FOUNDATIONS OF MATHEMATICS, North Holland, 1985.] [See under "Ordinal 4" in "A Table of Some Growth Rates" on p. 188 for the assertion that G(n) grows at the hypertetration rate.]
[33] Craig Smorynski, " "Big" news from Archimedes to Friedman", Notices of the Amer. Math. Society 30 (1983), 251256. [Reprinted on pp. 353366 of L. A. Harrington et al. (editors), HARVEY FRIEDMAN'S RESEARCH ON THE FOUNDATIONS OF MATHEMATICS, North Holland, 1985.]
[34] Joel Spencer, "Large numbers and unprovable theorems", Amer. Math. Monthly 90 (1983), 669675.
[35] Susan Stepney, "Big Numbers" and "Graham's Number".
http://public.logica.com/~stepneys/cyc/b/big.htm http://public.logica.com/~stepneys/cyc/g/graham.htm
[36] Stan S. Wainer, "Ordinal recursion, and a refinement of the extended Grzegorezyk hierarchy", J. Symbolic Logic 37 (1972), 281292. [See my comment for Wainer (1989).]
[37] Stan S. Wainer, "The "slowgrowing" $\Pi_{1}^{2}$ approach to Hierarchies", pp. 487502 in Proc. Symposium in Pure Math. 42, Amer. Math. Soc., 1985.
[38] Stan S. Wainer, "Slow growing versus fast growing", J. Symbolic Logic 54 (1989), 608614. [Wainer mentioned as an aside in Wainer (1972) that the slowgrowing hierarchy catches up to the fastgrowing hierarchy at the gamma_0 level. It was later shown by J.Y. Girard in 1981 that the first place it catches up is well past this. (Indeed, the Howard ordinal level of the slowgrowing hierarchy is just the epsilon_0 level of the fastgrowing hierarchy.) In the present paper Wainer gives a simplified proof of Girard's result and some generalizations of it.]
[39] Eric W. Weisstein, "Graham's Number", "Arrow Notation", "Ackermann Function", and "Goodstein Sequence" (MathWorld).
http://mathworld.wolfram.com/GrahamsNumber.html http://mathworld.wolfram.com/ArrowNotation.html http://mathworld.wolfram.com/AckermannFunction.html http://mathworld.wolfram.com/GoodsteinSequence.html
***************************************** *****************************************



