281 views

Skip to first unread message

Mar 4, 2002, 1:03:17 PM3/4/02

to

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 <http://www.ii.com/math/ch/confusion/>.]

[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

*****************************************

*****************************************

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu