17 December 1976, Volume 194, Number 4271 SCIENCE
This is a pretty big number; at least, if a
monkey sits at a typewriter and types at
random, the average number of trials
before he types perfectly the entire text
of Shakespeare's Hamlet would be
Mathematics and Computer Science: much, much less than this: it is merely a
1 followed by about 40,000 zeros. The
Coping with Finiteness general rule is
k arrows
Advances in our ability to compute are bringing us x1t... In
substantially closer to ultimate limitations. k-i k-I k-I
Downloaded from http://science.sciencemag.org/ on September 17, 2019
=x1.. T(xt... T
Tn... Ttx)ime
Donald E. Knuth n times
Thus, one arrow is defined in terms of
none, two in terms of one, three in terms
of two, and so on.
A well-known book entitled One, Two, any interest. It is hard to debunk such a In order to see how these arrow func-
Three, ... Infinity was published by Ga- notion, since there are no accepted stan- tions behave, let us look at a very small
mov about 30 years ago (1), and he began dards for demonstrating that something example
by telling a story about two Hungarian is interesting, especially when something 10tTtt3
noblemen. It seems that the two gentle- finite is compared with something tran-
men were out riding, and one suggested scendent. Yet I believe that the climate This is equal to
to the other that they play a game: Who of thought is changing, since finite pro-
can name the largest number. "Good," cesses are proving to be such fascinating 1011t1 (10111t10)
said the second man, "you go first." objects of study. so we should first evaluate 1011t 10.
After several minutes of intense concen- In the first place, it is important to This is
tration, the first nobleman announced understand that finite numbers can be
the largest number he could think of: extremely large. Let us start with some 1Ot1 (1Ott (1Ott (1OT (1Ott
"Three." Now it was the other man's very familiar and fairly small numbers: (10 t t (101t (10 t t (10 1T 10))))))))
turn, and he thought furiously, but after the value of xn is x + x + * * + x, added
about a quarter of an hour he gave up. n times. Similarly we can define a num- and that is
"You win," he said. ber I shall write as x t n, which means I
In this article I will try to assess how xx .x multiplied n times. For example, 10t 1 (10t1(101 1(101T (10
10
much further we have come, by dis- 101 10 = 10*10-10 10 10-10 10 10 10*10- 10
10
cussing how well we can now deal with = 10,000,000,000 is 10 billion; this is 10
10
large qutantities. Although we have cer- usually written 1010, but it will be clear in 10
10
tainly narrowed the gap between three a minute why I prefer to use an upward
(101t (10 t t (10 t t 1010
10
and infinity, recent results indicate that arrow. In fact, the next step uses two
we will never actually be able to go very arrows =1011 (lOttT (lOt tT (10 TT (lOtt
far in practice. My purpose is to explore xttn = xt (xt( T x) ...)) 10
relationships between the finite and the
infinite, in the light of these devel- where we take powers n times. For ex- ( 10 t t ( 10 T t 1010 )))
opments. ample
10
where the stack of 1O's is 101t 1O levels
10
10 tall. We take the huge number at the
Some Large Finite Numbers 10
10 right of this formula, which I cannot
10
10 even write down without using the arrow
10
Since the time of Greek philosophy, 10tt10= 1010 notation, and repeat the double-arrow
men have prided thzmselves on their 10
operation, getting an even huger num-
ability to understand something about 10
10 ber, and then we must do the same thing
infinity; and it has become traditional in 10
10 again and again. Let us call the final
some circles to regard finite things as 10
10
The author is professor of computer science at
essentially trivial, too limited to be of = 1 followed by 1010 zeros Stanford University, Stanford, California 94305.
17 DECEMBER 1976 1235
This study source was downloaded by 100000899194722 from CourseHero.com on 05-30-2025 13:26:52 GMT -05:00
https://www.coursehero.com/file/249890368/finitenesspdf/
, result W. (It is such an immense number, the automobile, has changed our lives,
we cannot use just an ordinary letter for and note that computers have increased
it.) our calculation speeds by six orders of
Of course we are not done yet, we magnitude; that is more than the ratio of
have only evaluated 10 1 t 10; to com- the fastest airplane velocity to a snail's
plete the job we need to stick this gigan- pace.
tic number into the formula for I do not mean to claim that computers
10 t t t t 3, namely do everything a million times faster than
1T0T1T3 = 10T TTC 40 BILLION people can; mere mortals like us can do
(NOT DRAWN LIGHT YEARS
some things much better. For example,
= 10 t t (10 t t (10 t t t (10 t t 10) ...)) Fig. 1. The known universe fits inside this
box. you and I can even recognize the face of
Ye times a friend who has recently grown a mous-
tache; and for tasks like filing, a comput-
The three dots ." here suppress a lot er may be only ten or so times faster than
of detail-maybe I should halve used four light
rays take to travel 10-13 cm, the a good secretary. But when it comes to
dots. At any rate it seems to me that the total number of time units since the dawn arithmetic, computers appear to be al-
magnitude of this number 10 IT t T 3 is so of the universe is only one fourth the most infinitely fast compared with
large as to be beyond human comprehen- number of little cubes along a single edge people.
sion. of the big cube in Fig. 1, assuming that As a result, we have begun to think
On the other hand, it is very small as the universe is 10 billion years old. about computational problems that used
finite numbers go. We might have used W Coming down to earth, it is instructive to be unthinkable. Our appetite for calcu-
arrows instead of just four, but even that to consider typical transportation lation has caused us to deal with finite
Downloaded from http://science.sciencemag.org/ on September 17, 2019
would not get us much further-almost speeds. numbers much larger than those we con-
all finite numbers are larger than this. I sidered before, and this has opened up a
think this example helps open our eyes Snail 0.006 mile/hour rich vein of challenging problems, just as
to the fact that some numbers are very Man walking
U.S. automobile 55
4 mile/hour
exciting as the problems about infinity
mile/hour
large even if they are merely finite. Thus, Jet plane 600 mile/hour which have inspired mathematicians for
mathematicians who stick mostly to Supersonic jet 1200 mile/hour so many centuries.
working with finite numbers are not real- Of course, computers are not infinitely
ly limiting themselves too severely. I would never think of walking from
California to Boston, but the plane flight fast, and our expectations have become
is only 150 times faster. Compare this to inflated even faster than our computa-
the situation with respect to the follow- tional capabilities. We are forced to real-
Realistic Numbers ize that there are limits beyond which we
ing computation speeds, given 10-digit
cannot go. The numbers we can deal
This discussion has set the stage for numbers. with are not only finite, they are very
the next point I want to make, namely Man (pencil and paper) 0.2/sec finite, and we do not have the time or
that our total resources are not actually Man (abacus) 1/sec space to solve certain problems even
very large. Let us try to see how big the Mechanical calculator 4/sec with the aid of the fastest computers.
known universe is. Archimedes began Medium-speed computer 200,000/sec Thus, the theme of this article is coping
such an investigation many years ago, in Fast computer 200,000,000/sec
with finiteness: What useful things can
his famous discussion of the number of A medium-fast computer can add 1 mil- we say about these finite limitations?
grains of sand that would completely fill lion times faster than we can, and the How have people learned to deal with
the earth and sky; he did not have the fastest machines are 1000 times faster the situation?
benefit of modern astronomy, but his yet. Such a ratio of speeds is unprece-
estimate was qualitatively the same as dented in history: consider how much a
what we would say today. The distance mere factor of 10 in speed, provided by Advances in Technology and Techniques
to the farthest observable galaxies is
thought to be at most about 10 billion During the last 15 years computer de-
light years. On the other hand, the funda- 1 2 2 1 2 1 2 signers have made computing machines
mental nucleons that make up matter are about 1000 times faster. Mathematicians
about 10-12 centimeter in diameter. In 2 3 2 2 3 2
and computer scientists have also discov-
order to get a generous upper bound on 2 2 2 2 2 3 3 2 3 ered a variety of new techniques, by
the size of the universe, let us imagine a which many problems can now be solved
1 3 2 3 2 2
cube that is 40 billion light years on each enormously faster than they could be-
side, and fill it with tiny cubes that are 3 3 2 fore. I will present several examples of
smaller than protons and neutrons, say 3 3 2 this; the first one, which is somehow
10-13 cm on each side (see Fig. 1). The symbolic of our advances in arithmetic
total number of little cubes comes to less 3 2 1 2 3
ability, is the following factorization of a
than 10125. We might say that this is an 3 3 3 2 3 2 2 very large number, completed in 1970 by
"astronomically large" number, but ac- 3 Morrison and Brillhart (2).
1 3 1 2 3
tually it has only 125 digits.
Instead of talking only about large 332 2 1 3 3 340,282,366,920,
numbers of objects, let us also consider 2 2 2
1 I 2 12 2 938,463,463,374,607,431,768,211,457
the time dimension. Here the numbers Fig. 2. A "random" path from the lower left
are much smaller; for example, if we corner to the upper right corner of a 10 x 10 = 5,704,689,200,685,129,054,721 x
take as a unit the amount of time that grid. 59,649,589,127,497,217
1236 SCIENCE, VOL. 194
This study source was downloaded by 100000899194722 from CourseHero.com on 05-30-2025 13:26:52 GMT -05:00
https://www.coursehero.com/file/249890368/finitenesspdf/
This is a pretty big number; at least, if a
monkey sits at a typewriter and types at
random, the average number of trials
before he types perfectly the entire text
of Shakespeare's Hamlet would be
Mathematics and Computer Science: much, much less than this: it is merely a
1 followed by about 40,000 zeros. The
Coping with Finiteness general rule is
k arrows
Advances in our ability to compute are bringing us x1t... In
substantially closer to ultimate limitations. k-i k-I k-I
Downloaded from http://science.sciencemag.org/ on September 17, 2019
=x1.. T(xt... T
Tn... Ttx)ime
Donald E. Knuth n times
Thus, one arrow is defined in terms of
none, two in terms of one, three in terms
of two, and so on.
A well-known book entitled One, Two, any interest. It is hard to debunk such a In order to see how these arrow func-
Three, ... Infinity was published by Ga- notion, since there are no accepted stan- tions behave, let us look at a very small
mov about 30 years ago (1), and he began dards for demonstrating that something example
by telling a story about two Hungarian is interesting, especially when something 10tTtt3
noblemen. It seems that the two gentle- finite is compared with something tran-
men were out riding, and one suggested scendent. Yet I believe that the climate This is equal to
to the other that they play a game: Who of thought is changing, since finite pro-
can name the largest number. "Good," cesses are proving to be such fascinating 1011t1 (10111t10)
said the second man, "you go first." objects of study. so we should first evaluate 1011t 10.
After several minutes of intense concen- In the first place, it is important to This is
tration, the first nobleman announced understand that finite numbers can be
the largest number he could think of: extremely large. Let us start with some 1Ot1 (1Ott (1Ott (1OT (1Ott
"Three." Now it was the other man's very familiar and fairly small numbers: (10 t t (101t (10 t t (10 1T 10))))))))
turn, and he thought furiously, but after the value of xn is x + x + * * + x, added
about a quarter of an hour he gave up. n times. Similarly we can define a num- and that is
"You win," he said. ber I shall write as x t n, which means I
In this article I will try to assess how xx .x multiplied n times. For example, 10t 1 (10t1(101 1(101T (10
10
much further we have come, by dis- 101 10 = 10*10-10 10 10-10 10 10 10*10- 10
10
cussing how well we can now deal with = 10,000,000,000 is 10 billion; this is 10
10
large qutantities. Although we have cer- usually written 1010, but it will be clear in 10
10
tainly narrowed the gap between three a minute why I prefer to use an upward
(101t (10 t t (10 t t 1010
10
and infinity, recent results indicate that arrow. In fact, the next step uses two
we will never actually be able to go very arrows =1011 (lOttT (lOt tT (10 TT (lOtt
far in practice. My purpose is to explore xttn = xt (xt( T x) ...)) 10
relationships between the finite and the
infinite, in the light of these devel- where we take powers n times. For ex- ( 10 t t ( 10 T t 1010 )))
opments. ample
10
where the stack of 1O's is 101t 1O levels
10
10 tall. We take the huge number at the
Some Large Finite Numbers 10
10 right of this formula, which I cannot
10
10 even write down without using the arrow
10
Since the time of Greek philosophy, 10tt10= 1010 notation, and repeat the double-arrow
men have prided thzmselves on their 10
operation, getting an even huger num-
ability to understand something about 10
10 ber, and then we must do the same thing
infinity; and it has become traditional in 10
10 again and again. Let us call the final
some circles to regard finite things as 10
10
The author is professor of computer science at
essentially trivial, too limited to be of = 1 followed by 1010 zeros Stanford University, Stanford, California 94305.
17 DECEMBER 1976 1235
This study source was downloaded by 100000899194722 from CourseHero.com on 05-30-2025 13:26:52 GMT -05:00
https://www.coursehero.com/file/249890368/finitenesspdf/
, result W. (It is such an immense number, the automobile, has changed our lives,
we cannot use just an ordinary letter for and note that computers have increased
it.) our calculation speeds by six orders of
Of course we are not done yet, we magnitude; that is more than the ratio of
have only evaluated 10 1 t 10; to com- the fastest airplane velocity to a snail's
plete the job we need to stick this gigan- pace.
tic number into the formula for I do not mean to claim that computers
10 t t t t 3, namely do everything a million times faster than
1T0T1T3 = 10T TTC 40 BILLION people can; mere mortals like us can do
(NOT DRAWN LIGHT YEARS
some things much better. For example,
= 10 t t (10 t t (10 t t t (10 t t 10) ...)) Fig. 1. The known universe fits inside this
box. you and I can even recognize the face of
Ye times a friend who has recently grown a mous-
tache; and for tasks like filing, a comput-
The three dots ." here suppress a lot er may be only ten or so times faster than
of detail-maybe I should halve used four light
rays take to travel 10-13 cm, the a good secretary. But when it comes to
dots. At any rate it seems to me that the total number of time units since the dawn arithmetic, computers appear to be al-
magnitude of this number 10 IT t T 3 is so of the universe is only one fourth the most infinitely fast compared with
large as to be beyond human comprehen- number of little cubes along a single edge people.
sion. of the big cube in Fig. 1, assuming that As a result, we have begun to think
On the other hand, it is very small as the universe is 10 billion years old. about computational problems that used
finite numbers go. We might have used W Coming down to earth, it is instructive to be unthinkable. Our appetite for calcu-
arrows instead of just four, but even that to consider typical transportation lation has caused us to deal with finite
Downloaded from http://science.sciencemag.org/ on September 17, 2019
would not get us much further-almost speeds. numbers much larger than those we con-
all finite numbers are larger than this. I sidered before, and this has opened up a
think this example helps open our eyes Snail 0.006 mile/hour rich vein of challenging problems, just as
to the fact that some numbers are very Man walking
U.S. automobile 55
4 mile/hour
exciting as the problems about infinity
mile/hour
large even if they are merely finite. Thus, Jet plane 600 mile/hour which have inspired mathematicians for
mathematicians who stick mostly to Supersonic jet 1200 mile/hour so many centuries.
working with finite numbers are not real- Of course, computers are not infinitely
ly limiting themselves too severely. I would never think of walking from
California to Boston, but the plane flight fast, and our expectations have become
is only 150 times faster. Compare this to inflated even faster than our computa-
the situation with respect to the follow- tional capabilities. We are forced to real-
Realistic Numbers ize that there are limits beyond which we
ing computation speeds, given 10-digit
cannot go. The numbers we can deal
This discussion has set the stage for numbers. with are not only finite, they are very
the next point I want to make, namely Man (pencil and paper) 0.2/sec finite, and we do not have the time or
that our total resources are not actually Man (abacus) 1/sec space to solve certain problems even
very large. Let us try to see how big the Mechanical calculator 4/sec with the aid of the fastest computers.
known universe is. Archimedes began Medium-speed computer 200,000/sec Thus, the theme of this article is coping
such an investigation many years ago, in Fast computer 200,000,000/sec
with finiteness: What useful things can
his famous discussion of the number of A medium-fast computer can add 1 mil- we say about these finite limitations?
grains of sand that would completely fill lion times faster than we can, and the How have people learned to deal with
the earth and sky; he did not have the fastest machines are 1000 times faster the situation?
benefit of modern astronomy, but his yet. Such a ratio of speeds is unprece-
estimate was qualitatively the same as dented in history: consider how much a
what we would say today. The distance mere factor of 10 in speed, provided by Advances in Technology and Techniques
to the farthest observable galaxies is
thought to be at most about 10 billion During the last 15 years computer de-
light years. On the other hand, the funda- 1 2 2 1 2 1 2 signers have made computing machines
mental nucleons that make up matter are about 1000 times faster. Mathematicians
about 10-12 centimeter in diameter. In 2 3 2 2 3 2
and computer scientists have also discov-
order to get a generous upper bound on 2 2 2 2 2 3 3 2 3 ered a variety of new techniques, by
the size of the universe, let us imagine a which many problems can now be solved
1 3 2 3 2 2
cube that is 40 billion light years on each enormously faster than they could be-
side, and fill it with tiny cubes that are 3 3 2 fore. I will present several examples of
smaller than protons and neutrons, say 3 3 2 this; the first one, which is somehow
10-13 cm on each side (see Fig. 1). The symbolic of our advances in arithmetic
total number of little cubes comes to less 3 2 1 2 3
ability, is the following factorization of a
than 10125. We might say that this is an 3 3 3 2 3 2 2 very large number, completed in 1970 by
"astronomically large" number, but ac- 3 Morrison and Brillhart (2).
1 3 1 2 3
tually it has only 125 digits.
Instead of talking only about large 332 2 1 3 3 340,282,366,920,
numbers of objects, let us also consider 2 2 2
1 I 2 12 2 938,463,463,374,607,431,768,211,457
the time dimension. Here the numbers Fig. 2. A "random" path from the lower left
are much smaller; for example, if we corner to the upper right corner of a 10 x 10 = 5,704,689,200,685,129,054,721 x
take as a unit the amount of time that grid. 59,649,589,127,497,217
1236 SCIENCE, VOL. 194
This study source was downloaded by 100000899194722 from CourseHero.com on 05-30-2025 13:26:52 GMT -05:00
https://www.coursehero.com/file/249890368/finitenesspdf/
