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), 149-154.
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 hyper-tetrated exponent, whereas the function
G(n) that other sources define has a growth rate associated with
the (w+1)'st level of the Grzegorczyk-Wainer 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 HYPER-TETRATION
2. SMORYNSKI'S G(n) IS ESSENTIALLY HYPER-TETRATION
3. THE GRZEGORCZYK-WAINER 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 non-relativistic 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 non-relativistic 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 non-relativistic 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
particle-sized 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/known-math/97/skewes
http://www.math.niu.edu/~rusin/known-math/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 HYPER-TETRATION
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 hyper-exponent towers in a top-down manner.
x^^1 = x
x^^(y+1) = x ^ (x^^y) tetration
x^^^1 = x
x^^^(y+1) = x ^^ (x^^^y) hyper-tetration
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 k-iterate 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), hyper-tetrated
growth is virtually unaffected by an application of our
@-slow-down 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 higher-order 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+j-1) 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+j-1) 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 HYPER-TETRATION
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 GRZEGORCZYK-WAINER 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 n-upper-arrows 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 w-level 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)-up-arrows 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 up-arrows (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 Grzegorczyk-Wainer Hierarchy, but after looking
into the matter a bit I'm still not sure. I *think* 4-arrow
chains correspond to descriptions under the w^2 operation level,
5-arrow 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 w-jump
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 Grzegorczyk-Wainer Hierarchy.
*****************************************
*****************************************
6. SOME REFERENCES FOR LARGE NUMBERS
[1] Isaac Asimov, "T-Formation", Magazine of Fantasy and Science
Fact, August 1963. [Reprinted in ADDING A DIMENSION (1964)
and on pp. 45-56 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), 109-136.
[3] Wilfried Buchholz and Stan Wainer, "Provably computable
functions and the fast growing hierarchy", Contemporary
Math. 65 (1987), 179-198.
[4] Andrew D Burbanks, "Fast-Growing 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), 704-706.
[6] E. A. Cichon and Stan S. Wainer, "The slow-growing and the
Grzegorczyk hierarchies", J. Symbolic Logic 48 (1983),
399-408.
[7] John H. Conway and Richard K. Guy, THE BOOK OF NUMBERS,
Springer-Verlag, 1996. [See pp. 59-62.]
[8] R. E. Crandall, "The challenge of large numbers", Scientific
American 276 (Feb. 1997), 74-79.
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), 273-277.
[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. Dennis-Jones and Stan S. Wainer, "Subrecursive
hierarchies via direct limits", pp. 117-128 in COMPUTATION
AND PROOF THEORY, Lecture Notes in Math. #1104,
Springer-Verlag, 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), 199-260.
[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), 18-28.
[15] R. L. Goodstein, "On the restricted ordinal theorem",
J. Symbolic Logic 9 (1944), 33-41.
[16] Douglas R. Hofstadter, "On Number Numbness", Metamagical
Themas column, Scientific America, May 1982. [Reprinted
on pp. 115-131 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. 1996-2010 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), 267-314.
[20] Laurie Kirby and Jeff Paris, "Accessible independence results
for Peano arithmetic", Bull. London Math. Soc. 14 (1982),
285-293.
[21] Donald E. Knuth, "Mathematics and computer science: Coping
with finiteness", Science 194 (1976), 1235-1242.
[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. 100-113 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 number-theoretic
functions I [II]", Archiv fur Math. Logik und
Grundlagenforschung 13 (1970), 39-51 [97-113].
[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/largenum-2.html
http://home.earthlink.net/~mrob/pub/math/largenum-3.html
http://home.earthlink.net/~mrob/pub/math/largenum-4.html
[27] K. K. Nambiar, "Ackermann functions and transfinite ordinals",
Appl. Math. Lett. 8(6) (1995), 51-53.
[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 fast-growing
functions", Contemporary Mathematics 65 (1987), 359-394.
[31] Craig Smorynski, "Some rapidly growing functions", The
Mathematical Intelligencer 2 (1979-80), 149-154.
[See pp. 149-150 for Graham's number.]
[32] Craig Smorynski, "The varieties of arboreal experience",
The Mathematical Intelligencer 4 (1982), 182-189.
[Reprinted on pp. 381-397 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 hyper-tetration rate.]
[33] Craig Smorynski, " "Big" news from Archimedes to Friedman",
Notices of the Amer. Math. Society 30 (1983), 251-256.
[Reprinted on pp. 353-366 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), 669-675.
[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),
281-292. [See my comment for Wainer (1989).]
[37] Stan S. Wainer, "The "slow-growing" $\Pi_{1}^{2}$ approach
to Hierarchies", pp. 487-502 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), 608-614. [Wainer mentioned as an aside in
Wainer (1972) that the slow-growing hierarchy catches up to
the fast-growing 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 slow-growing hierarchy is just the epsilon_0 level of the
fast-growing 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
*****************************************
*****************************************
|
|
|
|
