best essay about the biggest possible numbers by making a sequence that grows faster than any other sequence
None
1999-05-07
<div><p></p><table><tbody><tr><td></td>
<td>
<p><a href="http://www.geocities.ws/soidsenatas/articulos/31mnum.pdf">[This essay in Spanish]</a>
<br /><a href="http://blog.smwhr.net/index.php?2007/09/30/609-la-course-aux-grands-nombres">[This essay in French]</a>
<br /><a href="https://www.jianshu.com/p/35052a45e20f">[This essay in Chinese]</a>
</p><p>In an old joke, two noblemen vie to name the bigger number. The first, after
ruminating for hours, triumphantly announces "Eighty-three!" The second,
mightily impressed, replies "You win."</p>
<p>A biggest number contest is clearly pointless when the contestants take
turns. But what if the contestants write down their numbers simultaneously,
neither aware of the others? To introduce a talk on "Big Numbers," I invite two
audience volunteers to try exactly this. I tell them the rules:</p>
<i>
<p>You have fifteen seconds. Using standard math notation, English words, or
both, name a single whole numbernot an infinityon a blank index card. Be
precise enough for any reasonable modern mathematician to determine exactly what
number youve named, by consulting only your card and, if necessary, the
published literature.</p></i>
<p>So contestants cant say "the number of sand grains in the Sahara," because
sand drifts in and out of the Sahara regularly. Nor can they say "my opponents
number plus one," or "the biggest number anyones ever thought of plus
one"again, these are ill-defined, given what our reasonable mathematician has
available. Within the rules, the contestant who names the bigger number
wins.</p><i>
<p>Are you ready? Get set. Go.</p></i>
<p>The contests results are never quite what Id hope. Once, a seventh-grade
boy filled his card with a string of successive 9s. Like many other big-number
tyros, he sought to maximize his number by stuffing a 9 into every place value.
Had he chosen easy-to-write 1s rather than curvaceous 9s, his number could
have been millions of times bigger. He still would been decimated, though, by
the girl he was up against, who wrote a string of 9s followed by the
superscript <sup>999</sup>. Aha! An exponential: a number multiplied by itself
999 times. Noticing this innovation, I declared the girls victory without
bothering to count the 9s on the cards.</p>
<p>And yet the girls number could have been much bigger still, had she stacked
the mighty exponential more than once. Take , for example. This
behemoth, equal to 9<sup>387,420,489</sup>, has 369,693,100 digits. By
comparison, the number of elementary particles in the observable universe has a meager 85
digits, give or take. Three 9s, when stacked exponentially, already lift us
incomprehensibly beyond all the matter we can observeby a factor of about
10<sup>369,693,015</sup>. And weve said nothing of or
. </p>
<p>Place value, exponentials, stacked exponentials: each can express boundlessly
big numbers, and in this sense theyre all equivalent. But the notational
systems differ dramatically in the numbers they can express <i>concisely</i>.
Thats what the fifteen-second time limit illustrates. It takes the same amount
of time to write 9999, 99<sup>99</sup>, and yet the first
number is quotidian, the second astronomical, and the third hyper-mega
astronomical. The key to the biggest number contest is not swift penmanship, but
rather a potent paradigm for concisely capturing the gargantuan. </p>
<p>Such paradigms are historical rarities. We find a flurry in antiquity,
another flurry in the twentieth century, and nothing much in between. But when a
new way to express big numbers concisely does emerge, its often a byproduct of
a major scientific revolution: systematized mathematics, formal logic, computer
science. Revolutions this momentous, as any Kuhnian could tell you, only happen
under the right social conditions. Thus is the story of big numbers a story of
human progress.</p>
<p>And herein lies a parallel with another mathematical story. In his remarkable
and underappreciated book <i>A History of π</i>, Petr
Beckmann argues that the ratio of circumference to diameter is "a quaint little
mirror of the history of man." In the rare societies where science and reason
found refugethe early Athens of Anaxagoras and Hippias, the Alexandria of
Eratosthenes and Euclid, the seventeenth-century England of Newton and
Wallismathematicians made tremendous strides in calculating π. In Rome and medieval Europe, by contrast, knowledge of
π stagnated. Crude approximations such as the
Babylonians 25/8 held sway.</p>
<p>This same pattern holds, I think, for big numbers. Curiosity and openness
lead to fascination with big numbers, and to the buoyant view that no quantity,
whether of the number of stars in the galaxy or the number of possible bridge
hands, is too immense for the mind to enumerate. Conversely, ignorance and
irrationality lead to fatalism concerning big numbers. Historian Ilan Vardi cites the ancient Greek
term <i>sand-hundred</i>,
colloquially meaning <i>zillion</i>; as well as a passage from Pindars
<i>Olympic Ode II</i> asserting that "sand escapes counting."</p>
<p>¨ </p>
<p>But sand doesnt escape counting, as Archimedes recognized in the third
century B.C. Heres how he began <i>The Sand-Reckoner</i>, a sort of pop-science
article addressed to the King of Syracuse:</p>
<p>There are some ... who think that the number of the sand is infinite in
multitude ... again there are some who, without regarding it as infinite, yet
think that no number has been named which is great enough to exceed its
multitude ... But I will try to show you [numbers that] exceed not only the
number of the mass of sand equal in magnitude to the earth ... but also that of
a mass equal in magnitude to the universe.</p>
<p>This Archimedes proceeded to do, essentially by using the ancient Greek term
<i>myriad</i>, meaning ten thousand, as a base for exponentials. Adopting a
prescient cosmological model of Aristarchus, in which the "sphere of the fixed
stars" is vastly greater than the sphere in which the Earth revolves around the
sun, Archimedes obtained an upper bound of 10<sup>63</sup> on the number of sand
grains needed to fill the universe. (Supposedly 10<sup>63</sup> is the biggest
number with a lexicographically standard American name: <i>vigintillion</i>. But
the staid vigintillion had better keep vigil lest it be encroached upon by the
more whimsically-named <i>googol</i>, or 10<sup>100</sup>, and
<i>googolplex</i>, or .) Vast though it was, of course, 10<sup>63</sup>
wasnt to be enshrined as the all-time biggest number. Six centuries later,
Diophantus developed a simpler notation for exponentials, allowing him to
surpass . Then, in the Middle Ages, the rise of Arabic
numerals and place value made it easy to stack exponentials higher still. But
Archimedes paradigm for expressing big numbers wasnt fundamentally surpassed
until the twentieth century. And even today, exponentials dominate popular
discussion of the immense. </p>
<p>Consider, for example, the oft-repeated legend of the Grand Vizier in Persia
who invented chess. The King, so the legend goes, was delighted with the new
game, and invited the Vizier to name his own reward. The Vizier replied that,
being a modest man, he desired only one grain of wheat on the first square of a
chessboard, two grains on the second, four on the third, and so on, with twice
as many grains on each square as on the last. The innumerate King agreed, not
realizing that the total number of grains on all 64 squares would be
2<sup>64</sup>-1, or 18.6 quintillionequivalent to the worlds present wheat
production for 150 years.</p>
<p>Fittingly, this same exponential growth is what makes chess itself so
difficult. There are only about 35 legal choices for each chess move, but the
choices multiply exponentially to yield something like 10<sup>50</sup> possible board
positionstoo many for even a computer to search exhaustively. Thats why it
took until 1997 for a computer, Deep Blue, to defeat the human world chess
champion. And in Go, which has a 19-by-19 board and over 10<sup>150</sup>
possible positions, even an amateur human can still rout the worlds top-ranked
computer programs. Exponential growth plagues computers in other guises as well.
The traveling salesman problem asks for the shortest route connecting a set of
cities, given the distances between each pair of cities. The rub is that the
number of possible routes grows exponentially with the number of cities. When
there are, say, a hundred cities, there are about 10<sup>158</sup> possible
routes, and, although various shortcuts are possible, no known computer
algorithm is fundamentally better than checking each route one by one. The
traveling salesman problem belongs to a class called NP-complete, which includes
hundreds of other problems of practical interest. (NP stands for the technical
term Nondeterministic Polynomial-Time.) Its known that if theres an efficient
algorithm for any NP-complete problem, then there are efficient algorithms for
all of them. Here efficient means using an amount of time proportional to at
most the problem size raised to some fixed powerfor example, the number of
cities cubed. Its conjectured, however, that no efficient algorithm for
NP-complete problems exists. Proving this conjecture, called P¹ NP, has been a great unsolved problem of computer science
for thirty years.</p>
<p>Although computers will probably never solve NP-complete problems
efficiently, theres more hope for another grail of computer science:
replicating human intelligence. The human brain has roughly a hundred billion
neurons linked by a hundred trillion synapses. And though the function of an
individual neuron is only partially understood, its thought that each neuron
fires electrical impulses according to relatively simple rules up to a thousand
times each second. So what we have is a highly interconnected computer capable
of maybe 10<sup>14</sup> operations per second; by comparison, the worlds
fastest parallel supercomputer, the 9200-Pentium Pro teraflops machine at Sandia
National Labs, can perform 10<sup>12</sup> operations per second. Contrary to
popular belief, gray mush is not only hard-wired for intelligence: it surpasses
silicon even in raw computational power. But this is unlikely to remain true for
long. The reason is Moores Law, which, in its 1990s formulation, states that
the amount of information storable on a silicon chip grows exponentially,
doubling roughly once every two years. Moores Law will eventually play out, as
microchip components reach the atomic scale and conventional lithography
falters. But radical new technologies, such as optical computers, DNA computers,
or even quantum computers, could conceivably usurp silicons place. Exponential
growth in computing power cant continue forever, but it may continue long
enough for computersat least in processing powerto surpass human brains.</p>
<p>To prognosticators of artificial intelligence, Moores Law is a glorious
herald of exponential growth. But exponentials have a drearier side as well. The
human population recently passed six billion and is doubling about once every
forty years. At this exponential rate, if an average person weighs seventy
kilograms, then by the year 3750 the entire Earth will be composed of human
flesh. But before you invest in deodorant, realize that the population will stop
increasing long before thiseither because of famine, epidemic disease, global
warming, mass species extinctions, unbreathable air, or, entering the
speculative realm, birth control. Its not hard to fathom why physicist Albert
Bartlett asserted "the greatest shortcoming of the human race" to be "our
inability to understand the exponential function." Or why Carl Sagan advised us
to "never underestimate an exponential." In his book <i>Billions &amp;
Billions</i>, Sagan gave some other depressing consequences of exponential
growth. At an inflation rate of five percent a year, a dollar is worth only
thirty-seven cents after twenty years. If a uranium nucleus emits two neutrons,
both of which collide with other uranium nuclei, causing <i>them</i> to emit two
neutrons, and so forthwell, did I mention nuclear holocaust as a possible end
to population growth?</p>
<p>¨ </p>
<p>Exponentials are familiar, relevant, intimately connected to the physical
world and to human hopes and fears. Using the notational systems Ill discuss
next, we can concisely name numbers that make exponentials picayune by
comparison, that subjectively speaking exceed as much as the
latter exceeds 9. But these new systems may seem more abstruse than
exponentials. In his essay "On Number Numbness," Douglas Hofstadter leads his
readers to the precipice of these systems, but then avers:</p>
<p>If we were to continue our discussion just one zillisecond longer, we would
find ourselves smack-dab in the middle of the theory of recursive functions and
algorithmic complexity, and that would be too abstract. So lets drop the topic
right here.</p>
<p>But to drop the topic is to forfeit, not only the biggest number contest, but
any hope of understanding how stronger paradigms lead to vaster numbers. And so
we arrive in the early twentieth century, when a school of mathematicians called
the formalists sought to place all of mathematics on a rigorous axiomatic basis.
A key question for the formalists was what the word computable means. That is,
how do we tell whether a sequence of numbers can be listed by a definite,
mechanical procedure? Some mathematicians thought that computable coincided
with a technical notion called primitive recursive. But in 1928 Wilhelm
Ackermann disproved them by constructing a sequence of numbers thats clearly
computable, yet grows too quickly to be primitive recursive. </p>
<p>Ackermanns idea was to create an endless procession of arithmetic
operations, each more powerful than the last. First comes addition. Second comes
multiplication, which we can think of as repeated addition: for example, 5´3 means 5 added to itself 3 times, or 5+5+5 = 15. Third
comes exponentiation, which we can think of as repeated multiplication. Fourth
comes ... what? Well, we have to invent a weird new operation, for repeated
exponentiation. The mathematician Rudy Rucker calls it tetration. For example,
5 tetrated to the 3 means 5 raised to its own power 3 times, or
, a number with 2,185 digits. We can go on. Fifth comes repeated
tetration: shall we call it pentation? Sixth comes repeated pentation:
hexation? The operations continue infinitely, with each one standing on its
predecessor to peer even higher into the firmament of big numbers.</p>
<p>If each operation were a candy flavor, then the Ackermann sequence would be
the sampler pack, mixing one number of each flavor. First in the sequence is
1+1, or (dont hold your breath) 2. Second is 2´2, or
4. Third is 3 raised to the 3<sup>rd</sup> power, or 27. Hey, these numbers
arent so big!</p><i>
<p>Fee. Fi. Fo. Fum.</p></i>
<p>Fourth is 4 tetrated to the 4, or , which has
10<sup>154</sup> digits. If youre planning to write this number out, better
start now. Fifth is 5 pentated to the 5, or with 5 pentated
to the 4 numerals in the stack. This number is too colossal to describe in any
ordinary terms. And the numbers just get bigger from there.</p>
<p>Wielding the Ackermann sequence, we can clobber unschooled opponents in the
biggest-number contest. But we need to be careful, since there are several
definitions of the Ackermann sequence, not all identical.
Under the fifteen-second time limit, heres what I might write to avoid
ambiguity: </p><i>
<p>A(111)Ackermann seqA(1)=1+1, A(2)=2´2, A(3)=3<sup>3</sup>,
etc</p></i>
<p>Recondite as it seems, the Ackermann sequence does have some applications. A
problem in an area called Ramsey theory asks for the minimum dimension of a
hypercube satisfying a certain property. The true dimension is thought to be 6,
but the lowest dimension anyones been able is prove is so huge that it can only
be expressed using the same weird arithmetic that underlies the Ackermann
sequence. Indeed, the <i>Guinness Book of World Records</i> once listed this
dimension as the biggest number ever used in a mathematical proof. (Another
contender for the title once was Skewes number, about ,
which arises in the study of how prime numbers are distributed. The famous
mathematician G. H. Hardy quipped that Skewes was "the largest number which has
ever served any definite purpose in mathematics.") Whats more, Ackermanns
briskly-rising cavalcade performs an occasional cameo in computer science. For
example, in the analysis of a data structure called Union-Find, a term gets
multiplied by the inverse of the Ackermann sequencemeaning, for each whole
number X, the first number N such that the N<sup>th</sup> Ackermann number is
bigger than X. The inverse grows as slowly as Ackermanns original sequence
grows quickly; for all practical purposes, the inverse is at most 4.</p>
<p>¨ </p>
<p>Ackermann numbers are pretty big, but theyre not yet big enough. The quest
for still bigger numbers takes us back to the formalists. After Ackermann
demonstrated that primitive recursive isnt what we mean by computable, the
question still stood: what <i>do</i> we mean by computable? In 1936, Alonzo
Church and Alan Turing independently answered this question. While Church
answered using a logical formalism called the lambda calculus, Turing answered
using an idealized computing machinethe Turing machinethat, in essence, is
equivalent to every Compaq, Dell, Macintosh, and Cray in the modern world.
Turings paper describing his machine, "On Computable Numbers," is rightly
celebrated as the founding document of computer science.</p>
<p>"Computing," said Turing,</p>
<p>is normally done by writing certain symbols on paper. We may suppose this
paper to be divided into squares like a childs arithmetic book. In elementary
arithmetic the 2-dimensional character of the paper is sometimes used. But such
use is always avoidable, and I think it will be agreed that the two-dimensional
character of paper is no essential of computation. I assume then that the
computation is carried out on one-dimensional paper, on a tape divided into
squares.</p>
<p>Turing continued to explicate his machine using ingenious reasoning from
first principles. The tape, said Turing, extends infinitely in both directions,
since a theoretical machine ought not be constrained by physical limits on
resources. Furthermore, theres a symbol written on each square of the tape,
like the 1s and 0s in a modern computers memory. But how are the symbols
manipulated? Well, theres a tape head moving back and forth along the tape,
examining one square at a time, writing and erasing symbols according to
definite rules. The rules are the tape heads program: change them, and you
change what the tape head does.</p>
<p>Turings august insight was that we can program the tape head to carry out
<i>any</i> computation. Turing machines can add, multiply, extract cube roots,
sort, search, spell-check, parse, play Tic-Tac-Toe, list the Ackermann sequence.
If we represented keyboard input, monitor output, and so forth as symbols on the
tape, we could even run Windows on a Turing machine. But theres a problem. Set
a tape head loose on a sequence of symbols, and it might stop eventually, or it
might run foreverlike the fabled programmer who gets stuck in the shower
because the instructions on the shampoo bottle read "lather, rinse, repeat." If
the machines going to run forever, itd be nice to know this in advance, so
that we dont spend an eternity waiting for it to finish. But how can we
determine, in a finite amount of time, whether something will go on endlessly?
If you bet a friend that your watch will never stop ticking, when could you
declare victory? But maybe theres some ingenious program that can examine other
programs and tell us, infallibly, whether theyll ever stop running. We just
havent thought of it yet.</p>
<p>Nope. Turing proved that this problem, called the Halting Problem, is
unsolvable by Turing machines. The proof is a beautiful example of
self-reference. It formalizes an old argument about why you can never have
perfect introspection: because if you could, then you could determine what you
were going to do ten seconds from now, and then do something else. Turing
imagined that there was a special machine that could solve the Halting Problem.
Then he showed how we could have this machine analyze itself, in such a way that
it has to halt if it runs forever, and run forever if it halts. Like a hound
that finally catches its tail and devours itself, the mythical machine vanishes
in a fury of contradiction. (Thats the sort of thing you dont say in a
research paper.) </p>
<p>¨ </p>
<p>"Very nice," you say (or perhaps you say, "not nice at all"). "But what does
all this have to do with big numbers?" Aha! The connection wasnt published
until May of 1962. Then, in the <i>Bell System Technical Journal</i>, nestled
between pragmatically-minded papers on "Multiport Structures" and "Waveguide
Pressure Seals," appeared the modestly titled "On Non-Computable Functions" by
Tibor Rado. In this paper, Rado introduced the biggest numbers anyone had ever
imagined. </p>
<p>His idea was simple. Just as we can classify words by how many letters they
contain, we can classify Turing machines by how many rules they have in the tape
head. Some machines have only one rule, others have two rules, still others have
three rules, and so on. But for each fixed whole number N, just as there are
only finitely many distinct words with N letters, so too are there only finitely many distinct
machines with N rules. Among these machines, some halt and others run forever
when started on a blank tape. Of the ones that halt, asked Rado, whats the
maximum number of steps that any machine takes <i>before</i> it halts?
(Actually, Rado asked mainly about the maximum number of symbols any machine can
write on the tape before halting. But the maximum number of steps, which Rado
called S(n), has the same basic properties and is easier to reason about.)</p>
<p>Rado called this maximum the N<sup>th</sup> "Busy Beaver" number. (Ah yes,
the early 1960s were a more innocent age.) He visualized each Turing machine as
a beaver bustling busily along the tape, writing and erasing symbols. The
challenge, then, is to find the <i>busiest</i> beaver with exactly N rules,
albeit not an infinitely busy one. We can interpret this challenge as one of
finding the "most complicated" computer program N bits long: the one that does
the most amount of stuff, but not an infinite amount. </p>
<p>Now, suppose we knew the N<sup>th</sup> Busy Beaver number, which well call
BB(N). Then we could decide whether any Turing machine with N rules halts on a
blank tape. Wed just have to run the machine: if it halts, fine; but if it
doesnt halt within BB(N) steps, then we know it never <i>will</i> halt, since
BB(N) is the maximum number of steps it could make before halting. Similarly, if
you knew that all mortals died before age 200, then if Sally lived to be 200,
you could conclude that Sally was immortal. So no Turing machine can list the
Busy Beaver numbersfor if it could, it could solve the Halting Problem, which
we already know is impossible.</p>
<p>But heres a curious fact. Suppose we could name a number <i>greater</i> than
the N<sup>th</sup> Busy Beaver number BB(N). Call this number D for dam, since
like a beaver dam, its a roof for the Busy Beaver below. With D in hand,
computing BB(N) itself becomes easy: we just need to simulate all the Turing
machines with N rules. The ones that havent halted within D stepsthe ones that
bash through the dams roofnever will halt. So we can list exactly which
machines halt, and among these, the maximum number of steps that any machine
takes before it halts is BB(N).</p>
<p>Conclusion? The sequence of Busy Beaver numbers, BB(1), BB(2), and so on,
grows faster than <i>any</i> computable sequence. Faster than exponentials,
stacked exponentials, the Ackermann sequence, you name it. Because if a Turing
machine could compute a sequence that grows faster than Busy Beaver, then it
could use that sequence to obtain the Dsthe beaver dams. And with those Ds,
it could list the Busy Beaver numbers, which (sound familiar?) we already know
is impossible. The Busy Beaver sequence is non-computable, solely because it
grows stupendously fasttoo fast for any computer to keep up with it, even in
principle. </p>
<p>This means that no computer program could list all the Busy Beavers one by
one. It doesnt mean that specific Busy Beavers need remain eternally
unknowable. And in fact, pinning them down has been a computer science pastime
ever since Rado published his article. Its easy to verify that BB(1), the first
Busy Beaver number, is 1. Thats because if a one-rule Turing machine doesnt
halt after the very first step, itll just keep moving along the tape endlessly.
Theres no room for any more complex behavior. With two rules we can do more,
and a little grunt work will ascertain that BB(2) is 6. Six steps. What about
the third Busy Beaver? In 1965 Rado, together with Shen Lin, proved that BB(3)
is 21. The task was an arduous one, requiring human analysis of many machines to
prove that they dont haltsince, remember, theres no algorithm for listing the
Busy Beaver numbers. Next, in 1983, Allan Brady proved that BB(4) is 107.
Unimpressed so far? Well, as with the Ackermann sequence, dont be fooled by the
first few numbers. </p>
<p>In 1984, A.K. Dewdney devoted a <i>Scientific American</i> column to Busy
Beavers, which inspired amateur mathematician George Uhing to build a
special-purpose device for simulating Turing machines. The device, which cost
Uhing less than $100, found a five-rule machine that runs for 2,133,492 steps
before haltingestablishing that BB(5) must be at least as high. Then, in 1989,
Heiner Marxen and Jürgen Buntrock discovered that BB(5) is at least 47,176,870.
To this day, BB(5) hasnt been pinned down precisely, and it could turn out to
be much higher still. As for BB(6), Marxen and Buntrock set another record in
1997 by proving that its at least 8,690,333,381,690,951. A formidable
accomplishment, yet Marxen, Buntrock, and the other Busy Beaver hunters are
merely wading along the shores of the unknowable. Humanity may never know the
value of BB(6) for certain, let alone that of BB(7) or any higher number in the
sequence.</p>
<p>Indeed, already the top five and six-rule contenders elude us: we cant
explain how they work in human terms. If creativity imbues their design, its
not because humans put it there. One way to understand this is that even small
Turing machines can encode profound mathematical problems. Take Goldbachs
conjecture, that every even number 4 or higher is a sum of two prime numbers:
10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could
design a Turing machine with, oh, lets say 100 rules, that tests each even
number to see whether its a sum of two primes, and halts when and if it finds a
counterexample to the conjecture. Then knowing BB(100), we could in principle run
this machine for BB(100) steps, decide whether it halts, and thereby resolve
Goldbachs conjecture. We need not venture far in the sequence to enter the lair
of basilisks.</p>
<p>But as Rado stressed, even if we cant list the Busy Beaver numbers, theyre
perfectly well-defined mathematically. If you ever challenge a friend to the
biggest number contest, I suggest you write something like this:</p><i>
<p>BB(11111)Busy Beaver shift #1, 6, 21, etc</p></i>
<p>If your friend doesnt know about Turing machines or anything similar, but
only about, say, Ackermann numbers, then youll win the contest. Youll still
win even if you grant your friend a handicap, and allow him the entire lifetime
of the universe to write his number. The key to the biggest number contest is a
potent paradigm, and Turings theory of computation is potent indeed.</p>
<p>¨ </p>
<p>But what if your friend knows about Turing machines as well? Is there a
notational system for big numbers more powerful than even Busy Beavers?</p>
<p>Suppose we could endow a Turing machine with a magical ability to solve the
Halting Problem. What would we get? Wed get a super Turing machine: one with
abilities beyond those of any ordinary machine. But now, how hard is it to
decide whether a <i>super</i> machine halts? Hmm. It turns out that not even
super machines can solve this super Halting Problem, for the same reason that
ordinary machines cant solve the ordinary Halting Problem. To solve the Halting
Problem for super machines, wed need an even <i>more</i> powerful machine: a
super duper machine. And to solve the Halting Problem for super duper
machines, wed need a super duper pooper machine. And so on endlessly. This
infinite hierarchy of ever more powerful machines was formalized by the logician
Stephen Kleene in 1943 (although he didnt use the term super duper pooper).
</p>
<p>Imagine a novel, which is imbedded in a longer novel, which itself is
imbedded in an even <i>longer</i> novel, and so on ad infinitum. Within each
novel, the characters can debate the literary merits of any of the sub-novels.
But, by analogy with classes of machines that cant analyze themselves, the
characters can never critique the novel that they <i>themselves</i> are in.
(This, I think, jibes with our ordinary experience of novels.) To fully
understand some reality, we need to go outside of that reality. This is the
essence of Kleenes hierarchy: that to solve the Halting Problem for some class
of machines, we need a yet more powerful class of machines. </p>
<p>And theres no escape. Suppose a Turing machine had a magical ability to
solve the Halting Problem, <i>and</i> the super Halting Problem, <i>and</i> the
super duper Halting Problem, <i>and</i> the super duper pooper Halting Problem,
and so on endlessly. Surely this would be the Queen of Turing machines? Not
quite. As soon as we want to decide whether a Queen of Turing machines halts,
we need a still more powerful machine: an Empress of Turing machines. And
Kleenes hierarchy continues. </p>
<p>But hows this relevant to big numbers? Well, each level of Kleenes
hierarchy generates a faster-growing Busy Beaver sequence than do all the
previous levels. Indeed, each levels sequence grows so rapidly that it can only
be computed by a higher level. For example, define BB<sub>2</sub>(N) to be the
maximum number of steps a super machine with N rules can make before halting. If
this super Busy Beaver sequence were computable by super machines, then those
machines could solve the super Halting Problem, which we know is impossible. So
the super Busy Beaver numbers grow too rapidly to be computed, <i>even</i> if we
could compute the ordinary Busy Beaver numbers. </p>
<p>You might think that now, in the biggest-number contest, you could obliterate
even an opponent who uses the Busy Beaver sequence by writing something like
this: </p><i>
<p>BB<sub>2</sub>(11111).</p></i>
<p>But not quite. The problem is that Ive never seen these "higher-level Busy
Beavers" defined anywhere, probably because, to people who know computability
theory, theyre a fairly obvious extension of the ordinary Busy Beaver numbers.
So our reasonable modern mathematician wouldnt know what number you were
naming. If you want to use higher-level Busy Beavers in the biggest number
contest, heres what I suggest. First, publish a paper formalizing the concept
in some obscure, low-prestige journal. Then, during the contest, cite the paper
on your index card.</p>
<p>To exceed higher-level Busy Beavers, wed presumably need some new
computational model surpassing even Turing machines. I cant imagine what such a
model would look like. Yet somehow I doubt that the story of notational systems
for big numbers is over. Perhaps someday humans will be able concisely to name
numbers that make Busy Beaver 100 seem as puerile and amusingly small as our
noblemans eighty-three. Or if well never name such numbers, perhaps other
civilizations will. Is a biggest number contest afoot throughout the galaxy?</p>
<p>¨ </p>
<p>You might wonder why we cant transcend the whole parade of paradigms, and
name numbers by a system that encompasses and surpasses them all. Suppose you
wrote the following in the biggest number contest: </p><i>
<p>The biggest whole number nameable with 1,000 characters of English
text</p></i>
<p>Surely this number exists. Using 1,000 characters, we can name only finitely
many numbers, and among these numbers there has to be a biggest. And yet weve
made no reference to how the numbers named. The English text could invoke
Ackermann numbers, or Busy Beavers, or higher-level Busy Beavers, or even some
yet more sweeping concept that nobodys thought of yet. So unless our opponent
uses the same ploy, weve got him licked. What a brilliant idea! Why didnt we
think of this earlier?</p>
<p>Unfortunately it doesnt work. We might as well have written</p><i>
<p>One plus the biggest whole number nameable with 1,000 characters of English
text</p></i>
<p>This number takes at least 1,001 characters to name. Yet weve just named it
with only 80 characters! Like a snake that swallows itself whole, our colossal
number dissolves in a tumult of contradiction. What gives? </p>
<p>The paradox Ive just described was first published by Bertrand Russell, who
attributed it to a librarian named G. G. Berry. The Berry Paradox arises not
from mathematics, but from the ambiguity inherent in the English language.
Theres no surefire way to convert an English phrase into the number it names
(or to decide whether it names a number at all), which is why I invoked a
"reasonable modern mathematician" in the rules for the biggest number contest.
To circumvent the Berry Paradox, we need to name numbers using a precise,
mathematical notational system, such as Turing machineswhich is exactly the
idea behind the Busy Beaver sequence. So in short, theres no wily language
trick by which to surpass Archimedes, Ackermann, Turing, and Rado, no royal road
to big numbers. </p>
<p>You might also wonder why we cant use infinity in the contest. The answer
is, for the same reason why we cant use a rocket car in a bike race. Infinity
is fascinating and elegant, but its not a whole number. Nor can we subtract
from infinity to yield a whole number. Infinity minus 17 is still infinity,
whereas infinity minus infinity is undefined: it could be 0, 38, or even
infinity again. Actually I should speak of infinities, plural. For in the late
nineteenth century, Georg Cantor proved that there are different levels of
infinity: for example, the infinity of points on a line is greater than the
infinity of whole numbers. Whats more, just as theres no biggest number, so
too is there no biggest infinity. But the quest for big infinities is more
abstruse than the quest for big numbers. And it involves, not a succession of
paradigms, but essentially one: Cantors. </p>
<p>¨ </p>
<p>So here we are, at the frontier of big number knowledge. As Euclids disciple
supposedly asked, "what is the <i>use</i> of all this?" Weve seen that progress
in notational systems for big numbers mirrors progress in broader realms:
mathematics, logic, computer science. And yet, though a mirror reflects reality,
it doesnt necessarily influence it. Even within mathematics, big numbers are
often considered trivialities, their study an idle amusement with no broader
implications. I want to argue a contrary view: that understanding big numbers is
a key to understanding the world. </p>
<p>Imagine trying to explain the Turing machine to Archimedes. The genius of
Syracuse listens patiently as you discuss the papyrus tape extending infinitely
in both directions, the time steps, states, input and output sequences. At last
he explodes. </p>
<p>"Foolishness!" he declares (or the ancient Greek equivalent). "All youve
given me is an elaborate definition, with no value outside of itself."</p>
<p>How do you respond? Archimedes has never heard of computers, those
cantankerous devices that, twenty-three centuries from his time, will transact
the worlds affairs. So you cant claim practical application. Nor can you
appeal to Hilbert and the formalist program, since Archimedes hasnt heard of
those either. But then it hits you: the Busy Beaver sequence. You define the
sequence for Archimedes, convince him that BB(1000) is more than his
10<sup>63</sup> grains of sand filling the universe, more even than
10<sup>63</sup> raised to its own power 10<sup>63</sup> times. You defy him to
name a bigger number without invoking Turing machines or some equivalent. And as
he ponders this challenge, the power of the Turing machine concept dawns on him.
Though his intuition may never apprehend the Busy Beaver numbers, his reason
compels him to acknowledge their immensity. Big numbers have a way of imbuing
abstract notions with reality.</p>
<p>Indeed, one could define science as reasons attempt to compensate for our
inability to perceive big numbers. If we could run at 280,000,000 meters per
second, thered be no need for a special theory of relativity: itd be obvious
to everyone that the faster we go, the heavier and squatter we get, and the
faster time elapses in the rest of the world. If we could live for 70,000,000
years, thered be no theory of evolution, and <i>certainly</i> no creationism:
we could watch speciation and adaptation with our eyes, instead of painstakingly
reconstructing events from fossils and DNA. If we could bake bread at 20,000,000
degrees Kelvin, nuclear fusion would be not the esoteric domain of physicists
but ordinary household knowledge. But we cant do any of these things, and so we
have science, to deduce about the gargantuan what we, with our infinitesimal
faculties, will never sense. If people fear big numbers, is it any wonder that
they fear science as well and turn for solace to the comforting smallness of
mysticism?</p>
<p>But <i>do</i> people fear big numbers? Certainly they do. Ive met people who
dont know the difference between a million and a billion, and dont care. We
play a lottery with six ways to win!, overlooking the twenty million ways to
lose. We yawn at
six billion tons of carbon dioxide released into the atmosphere each year, and
speak of sustainable development in the jaws of exponential growth. Such
cases, it seems to me, transcend arithmetical ignorance and represent a basic
unwillingness to grapple with the immense.</p>
<p>Whence the cowering before big numbers, then? Does it have a biological
origin? In 1999, a group led by neuropsychologist
Stanislas Dehaene reported evidence in <i>Science</i> that two separate brain systems contribute
to mathematical thinking. The group trained Russian-English bilinguals to solve
a set of problems, including two-digit addition, base-eight addition, cube
roots, and logarithms. Some subjects were trained in Russian, others in English.
When the subjects were then asked to solve problems approximatelyto choose the
closer of two estimatesthey performed equally well in both languages. But when
asked to solve problems exactly, they performed better in the language of their
training. Whats more, brain-imaging evidence showed that the subjects parietal
lobes, involved in spatial reasoning, were more active during approximation
problems; while the left inferior frontal lobes, involved in verbal reasoning,
were more active during exact calculation problems. Studies of patients with
brain lesions paint the same picture: those with parietal lesions sometimes
cant decide whether 9 is closer to 10 or to 5, but remember the multiplication
table; whereas those with left-hemispheric lesions sometimes cant decide
whether 2+2 is 3 or 4, but know that the answer is closer to 3 than to 9.
Dehaene et al. conjecture that humans represent numbers in two ways. For
approximate reckoning we use a mental number line, which evolved long ago and
which we likely share with other animals. But for exact computation we use
numerical symbols, which evolved recently and which, being language-dependent,
are unique to humans. This hypothesis neatly explains the experiments findings:
the reason subjects performed better in the language of their training for exact
computation but not for approximation problems is that the former call upon the
verbally-oriented left inferior frontal lobes, and the latter upon the
spatially-oriented parietal lobes.</p>
<p>If Dehaene et al.s hypothesis is correct, then which representation do we
use for big numbers? Surely the symbolic onefor nobodys mental number line
could be long enough to contain , 5 pentated to the 5, or
BB(1000). And here, I suspect, is the problem. When thinking about 3, 4, or 7,
were guided by our spatial intuition, honed over millions of years of
perceiving 3 gazelles, 4 mates, 7 members of a hostile clan. But when thinking
about BB(1000), we have only language, that evolutionary neophyte, to rely upon.
The usual neural pathways for representing numbers lead to dead ends. And this,
perhaps, is why people are afraid of big numbers.</p>
<p>Could early intervention mitigate our big number phobia? What if second-grade
math teachers took an hour-long hiatus from stultifying busywork to ask their
students, "How do you name really, <i>really</i> big numbers?" And then told
them about exponentials and stacked exponentials, tetration and the Ackermann
sequence, maybe even Busy Beavers: a cornucopia of numbers vaster than any
theyd ever conceived, and ideas stretching the bounds of their
imaginations.</p>
<p>Who can name the bigger number? Whoever has the deeper paradigm. Are you
ready? Get set. Go.</p><b>
<p>References</p></b>
<p>Petr Beckmann, <i>A History of Pi</i>, Golem Press, 1971.</p>
<p>Allan H. Brady, "The Determination of the Value of Rados Noncomputable
Function Sigma(k) for Four-State Turing Machines," <i>Mathematics of
Computation</i>, vol. 40, no. 162, April 1983, pp 647-
665.</p>
<p>Gregory J. Chaitin, "The Berry Paradox," <i>Complexity</i>, vol. 1, no. 1,
1995, pp. 26- 30. At <a href="http://www.umcs.maine.edu/%7Echaitin/unm2.html">http://www.umcs.maine.edu/~chaitin/unm2.html</a>.</p>
<p>A.K. Dewdney, <i>The New Turing Omnibus: 66 Excursions in Computer
Science</i>, W.H. Freeman, 1993.</p>
<p>S. Dehaene and E. Spelke and P. Pinel and R. Stanescu and S. Tsivkin,
"Sources of Mathematical Thinking: Behavioral and Brain-Imaging Evidence,"
<i>Science</i>, vol. 284, no. 5416, May 7, 1999, pp. 970- 974.</p>
<p>Douglas Hofstadter, <i>Metamagical Themas: Questing for the Essence of Mind
and Pattern</i>, Basic Books, 1985. Chapter 6, "On Number Numbness," pp.
115- 135.</p>
<p>Robert Kanigel, <i>The Man Who Knew Infinity: A Life of the Genius
Ramanujan</i>, Washington Square Press, 1991.</p>
<p>Stephen C. Kleene, "Recursive predicates and quantifiers," <i>Transactions of
the American Mathematical Society</i>, vol. 53, 1943, pp. 41- 74.</p>
<p>Donald E. Knuth, <i>Selected Papers on Computer Science</i>, CSLI
Publications, 1996. Chapter 2, "Mathematics and Computer Science: Coping with
Finiteness," pp. 31- 57.</p>
<p>Dexter C. Kozen, <i>Automata and Computability</i>, Springer-Verlag,
1997.</p>
<p>, <i>The Design and Analysis of Algorithms</i>, Springer-Verlag, 1991.</p>
<p>Shen Lin and Tibor Rado, "Computer studies of Turing machine problems,"
<i>Journal of the Association for Computing Machinery</i>, vol. 12, no. 2, April
1965, pp. 196- 212.</p>
<p>Heiner Marxen, Busy Beaver, at <a href="http://www.drb.insel.de/%7Eheiner/BB/">http://www.drb.insel.de/~heiner/BB/</a>.</p>
<p> and Jürgen Buntrock, "Attacking the Busy Beaver 5," <i>Bulletin of the
European Association for Theoretical Computer Science</i>, no. 40, February
1990, pp. 247- 251.</p>
<p>Tibor Rado, "On Non-Computable Functions," <i>Bell System Technical
Journal</i>, vol. XLI, no. 2, May 1962, pp. 877-
884.</p>
<p>Rudy Rucker, <i>Infinity and the Mind</i>, Princeton University Press,
1995.</p>
<p>Carl Sagan, <i>Billions &amp; Billions</i>, Random House, 1997.</p>
<p>Michael Somos, "Busy Beaver Turing Machine." At <a href="http://grail.cba.csuohio.edu/%7Esomos/bb.html">http://grail.cba.csuohio.edu/~somos/bb.html</a>.</p>
<p>Alan Turing, "On computable numbers, with an application to the
Entscheidungsproblem," <i>Proceedings of the London Mathematical Society</i>,
Series 2, vol. 42, pp. 230- 265, 1936. Reprinted in
Martin Davis (ed.), <i>The Undecidable</i>, Raven, 1965.</p>
<p>Ilan Vardi, "Archimedes, the Sand Reckoner," at <a href="http://www.ihes.fr/%7Eilan/sand_reckoner.ps">http://www.ihes.fr/~ilan/sand_reckoner.ps</a>.</p>
<p>Eric W. Weisstein, <i>CRC Concise Encyclopedia of Mathematics</i>, CRC Press,
1999. Entry on "Large Number" at <a href="http://www.treasure-troves.com/math/LargeNumber.html">http://www.treasure-troves.com/math/LargeNumber.html</a>.</p>
</td></tr></tbody></table>
<p></p></div>||||I||||Who Can Name the Bigger Number?
by Scott Aaronson
[Author's blog]

 [This essay in Spanish]                               
 [This essay in French]                               
 [This essay in Chinese]                               
                               
 In an old joke, two noblemen vie to name the bigger number. The first, after ruminating for hours, triumphantly announces "Eighty-three!" The second, mightily impressed, replies "You win."                            
                               
 A biggest number contest is clearly pointless when the contestants take turns. But what if the contestants write down their numbers simultaneously, neither aware of the others? To introduce a talk on "Big Numbers," I invite two audience volunteers to try exactly this. I tell them the rules:                           
                               
 You have fifteen seconds. Using standard math notation, English words, or both, name a single whole numbernot an infinityon a blank index card. Be precise enough for any reasonable modern mathematician to determine exactly what number youve named, by consulting only your card and, if necessary, the published literature.                          
                               
 So contestants cant say "the number of sand grains in the Sahara," because sand drifts in and out of the Sahara regularly. Nor can they say "my opponents number plus one," or "the biggest number anyones ever thought of plus one"again, these are ill-defined, given what our reasonable mathematician has available. Within the rules, the contestant who names the bigger number wins.                         
                               
 Are you ready? Get set. Go.                               
                               
 The contests results are never quite what Id hope. Once, a seventh-grade boy filled his card with a string of successive 9s. Like many other big-number tyros, he sought to maximize his number by stuffing a 9 into every place value. Had he chosen easy-to-write 1s rather than curvaceous 9s, his number could have been millions of times bigger. He still would been decimated, though, by the girl he was up against, who wrote a string of 9s followed by the superscript 999. Aha! An exponential: a number multiplied by itself 999 times. Noticing this innovation, I declared the girls victory without bothering to count the 9s on the cards.                     
                               
 And yet the girls number could have been much bigger still, had she stacked the mighty exponential more than once. Take , for example. This behemoth, equal to 9387,420,489, has 369,693,100 digits. By comparison, the number of elementary particles in the observable universe has a meager 85 digits, give or take. Three 9s, when stacked exponentially, already lift us incomprehensibly beyond all the matter we can observeby a factor of about 10369,693,015. And weve said nothing of or .                       
                               
 Place value, exponentials, stacked exponentials: each can express boundlessly big numbers, and in this sense theyre all equivalent. But the notational systems differ dramatically in the numbers they can express concisely. Thats what the fifteen-second time limit illustrates. It takes the same amount of time to write 9999, 9999, and yet the first number is quotidian, the second astronomical, and the third hyper-mega astronomical. The key to the biggest number contest is not swift penmanship, but rather a potent paradigm for concisely capturing the gargantuan.                      
                               
 Such paradigms are historical rarities. We find a flurry in antiquity, another flurry in the twentieth century, and nothing much in between. But when a new way to express big numbers concisely does emerge, its often a byproduct of a major scientific revolution: systematized mathematics, formal logic, computer science. Revolutions this momentous, as any Kuhnian could tell you, only happen under the right social conditions. Thus is the story of big numbers a story of human progress.                        
                               
 And herein lies a parallel with another mathematical story. In his remarkable and underappreciated book A History of π, Petr Beckmann argues that the ratio of circumference to diameter is "a quaint little mirror of the history of man." In the rare societies where science and reason found refugethe early Athens of Anaxagoras and Hippias, the Alexandria of Eratosthenes and Euclid, the seventeenth-century England of Newton and Wallismathematicians made tremendous strides in calculating π. In Rome and medieval Europe, by contrast, knowledge of π stagnated. Crude approximations such as the Babylonians 25/8 held sway.                     
                               
 This same pattern holds, I think, for big numbers. Curiosity and openness lead to fascination with big numbers, and to the buoyant view that no quantity, whether of the number of stars in the galaxy or the number of possible bridge hands, is too immense for the mind to enumerate. Conversely, ignorance and irrationality lead to fatalism concerning big numbers. Historian Ilan Vardi cites the ancient Greek term sand-hundred, colloquially meaning zillion; as well as a passage from Pindars Olympic Ode II asserting that "sand escapes counting."                       
                               
 ¨                               
                               
 But sand doesnt escape counting, as Archimedes recognized in the third century B.C. Heres how he began The Sand-Reckoner, a sort of pop-science article addressed to the King of Syracuse:                            
                               
 There are some ... who think that the number of the sand is infinite in multitude ... again there are some who, without regarding it as infinite, yet think that no number has been named which is great enough to exceed its multitude ... But I will try to show you [numbers that] exceed not only the number of the mass of sand equal in magnitude to the earth ... but also that of a mass equal in magnitude to the universe.                         
                               
 This Archimedes proceeded to do, essentially by using the ancient Greek term myriad, meaning ten thousand, as a base for exponentials. Adopting a prescient cosmological model of Aristarchus, in which the "sphere of the fixed stars" is vastly greater than the sphere in which the Earth revolves around the sun, Archimedes obtained an upper bound of 1063 on the number of sand grains needed to fill the universe. (Supposedly 1063 is the biggest number with a lexicographically standard American name: vigintillion. But the staid vigintillion had better keep vigil lest it be encroached upon by the more whimsically-named googol, or 10100, and googolplex, or .) Vast though it was, of course, 1063 wasnt to be enshrined as the all-time biggest number. Six centuries later, Diophantus developed a simpler notation for exponentials, allowing him to surpass . Then, in the Middle Ages, the rise of Arabic numerals and place value made it easy to stack exponentials higher still. But Archimedes paradigm for expressing big numbers wasnt fundamentally surpassed until the twentieth century. And even today, exponentials dominate popular discussion of the immense.             
                               
 Consider, for example, the oft-repeated legend of the Grand Vizier in Persia who invented chess. The King, so the legend goes, was delighted with the new game, and invited the Vizier to name his own reward. The Vizier replied that, being a modest man, he desired only one grain of wheat on the first square of a chessboard, two grains on the second, four on the third, and so on, with twice as many grains on each square as on the last. The innumerate King agreed, not realizing that the total number of grains on all 64 squares would be 264-1, or 18.6 quintillionequivalent to the worlds present wheat production for 150 years.                     
                               
 Fittingly, this same exponential growth is what makes chess itself so difficult. There are only about 35 legal choices for each chess move, but the choices multiply exponentially to yield something like 1050 possible board positionstoo many for even a computer to search exhaustively. Thats why it took until 1997 for a computer, Deep Blue, to defeat the human world chess champion. And in Go, which has a 19-by-19 board and over 10150 possible positions, even an amateur human can still rout the worlds top-ranked computer programs. Exponential growth plagues computers in other guises as well. The traveling salesman problem asks for the shortest route connecting a set of cities, given the distances between each pair of cities. The rub is that the number of possible routes grows exponentially with the number of cities. When there are, say, a hundred cities, there are about 10158 possible routes, and, although various shortcuts are possible, no known computer algorithm is fundamentally better than checking each route one by one. The traveling salesman problem belongs to a class called NP-complete, which includes hundreds of other problems of practical interest. (NP stands for the technical term Nondeterministic Polynomial-Time.) Its known that if theres an efficient algorithm for any NP-complete problem, then there are efficient algorithms for all of them. Here efficient means using an amount of time proportional to at most the problem size raised to some fixed powerfor example, the number of cities cubed. Its conjectured, however, that no efficient algorithm for NP-complete problems exists. Proving this conjecture, called P¹ NP, has been a great unsolved problem of computer science for thirty years.    
                               
 Although computers will probably never solve NP-complete problems efficiently, theres more hope for another grail of computer science: replicating human intelligence. The human brain has roughly a hundred billion neurons linked by a hundred trillion synapses. And though the function of an individual neuron is only partially understood, its thought that each neuron fires electrical impulses according to relatively simple rules up to a thousand times each second. So what we have is a highly interconnected computer capable of maybe 1014 operations per second; by comparison, the worlds fastest parallel supercomputer, the 9200-Pentium Pro teraflops machine at Sandia National Labs, can perform 1012 operations per second. Contrary to popular belief, gray mush is not only hard-wired for intelligence: it surpasses silicon even in raw computational power. But this is unlikely to remain true for long. The reason is Moores Law, which, in its 1990s formulation, states that the amount of information storable on a silicon chip grows exponentially, doubling roughly once every two years. Moores Law will eventually play out, as microchip components reach the atomic scale and conventional lithography falters. But radical new technologies, such as optical computers, DNA computers, or even quantum computers, could conceivably usurp silicons place. Exponential growth in computing power cant continue forever, but it may continue long enough for computersat least in processing powerto surpass human brains.       
                               
 To prognosticators of artificial intelligence, Moores Law is a glorious herald of exponential growth. But exponentials have a drearier side as well. The human population recently passed six billion and is doubling about once every forty years. At this exponential rate, if an average person weighs seventy kilograms, then by the year 3750 the entire Earth will be composed of human flesh. But before you invest in deodorant, realize that the population will stop increasing long before thiseither because of famine, epidemic disease, global warming, mass species extinctions, unbreathable air, or, entering the speculative realm, birth control. Its not hard to fathom why physicist Albert Bartlett asserted "the greatest shortcoming of the human race" to be "our inability to understand the exponential function." Or why Carl Sagan advised us to "never underestimate an exponential." In his book Billions & Billions, Sagan gave some other depressing consequences of exponential growth. At an inflation rate of five percent a year, a dollar is worth only thirty-seven cents after twenty years. If a uranium nucleus emits two neutrons, both of which collide with other uranium nuclei, causing them to emit two neutrons, and so forthwell, did I mention nuclear holocaust as a possible end to population growth?           
                               
 ¨                               
                               
 Exponentials are familiar, relevant, intimately connected to the physical world and to human hopes and fears. Using the notational systems Ill discuss next, we can concisely name numbers that make exponentials picayune by comparison, that subjectively speaking exceed as much as the latter exceeds 9. But these new systems may seem more abstruse than exponentials. In his essay "On Number Numbness," Douglas Hofstadter leads his readers to the precipice of these systems, but then avers:                       
                               
 If we were to continue our discussion just one zillisecond longer, we would find ourselves smack-dab in the middle of the theory of recursive functions and algorithmic complexity, and that would be too abstract. So lets drop the topic right here.                           
                               
 But to drop the topic is to forfeit, not only the biggest number contest, but any hope of understanding how stronger paradigms lead to vaster numbers. And so we arrive in the early twentieth century, when a school of mathematicians called the formalists sought to place all of mathematics on a rigorous axiomatic basis. A key question for the formalists was what the word computable means. That is, how do we tell whether a sequence of numbers can be listed by a definite, mechanical procedure? Some mathematicians thought that computable coincided with a technical notion called primitive recursive. But in 1928 Wilhelm Ackermann disproved them by constructing a sequence of numbers thats clearly computable, yet grows too quickly to be primitive recursive.                   
                               
 Ackermanns idea was to create an endless procession of arithmetic operations, each more powerful than the last. First comes addition. Second comes multiplication, which we can think of as repeated addition: for example, 5´3 means 5 added to itself 3 times, or 5+5+5 = 15. Third comes exponentiation, which we can think of as repeated multiplication. Fourth comes ... what? Well, we have to invent a weird new operation, for repeated exponentiation. The mathematician Rudy Rucker calls it tetration. For example, 5 tetrated to the 3 means 5 raised to its own power 3 times, or , a number with 2,185 digits. We can go on. Fifth comes repeated tetration: shall we call it pentation? Sixth comes repeated pentation: hexation? The operations continue infinitely, with each one standing on its predecessor to peer even higher into the firmament of big numbers.                  
                               
 If each operation were a candy flavor, then the Ackermann sequence would be the sampler pack, mixing one number of each flavor. First in the sequence is 1+1, or (dont hold your breath) 2. Second is 2´2, or 4. Third is 3 raised to the 3rd power, or 27. Hey, these numbers arent so big!                           
                               
 Fee. Fi. Fo. Fum.                               
                               
 Fourth is 4 tetrated to the 4, or , which has 10154 digits. If youre planning to write this number out, better start now. Fifth is 5 pentated to the 5, or with 5 pentated to the 4 numerals in the stack. This number is too colossal to describe in any ordinary terms. And the numbers just get bigger from there.                          
                               
 Wielding the Ackermann sequence, we can clobber unschooled opponents in the biggest-number contest. But we need to be careful, since there are several definitions of the Ackermann sequence, not all identical. Under the fifteen-second time limit, heres what I might write to avoid ambiguity:                           
                               
 A(111)Ackermann seqA(1)=1+1, A(2)=2´2, A(3)=33, etc                              
                               
 Recondite as it seems, the Ackermann sequence does have some applications. A problem in an area called Ramsey theory asks for the minimum dimension of a hypercube satisfying a certain property. The true dimension is thought to be 6, but the lowest dimension anyones been able is prove is so huge that it can only be expressed using the same weird arithmetic that underlies the Ackermann sequence. Indeed, the Guinness Book of World Records once listed this dimension as the biggest number ever used in a mathematical proof. (Another contender for the title once was Skewes number, about , which arises in the study of how prime numbers are distributed. The famous mathematician G. H. Hardy quipped that Skewes was "the largest number which has ever served any definite purpose in mathematics.") Whats more, Ackermanns briskly-rising cavalcade performs an occasional cameo in computer science. For example, in the analysis of a data structure called Union-Find, a term gets multiplied by the inverse of the Ackermann sequencemeaning, for each whole number X, the first number N such that the Nth Ackermann number is bigger than X. The inverse grows as slowly as Ackermanns original sequence grows quickly; for all practical purposes, the inverse is at most 4.           
                               
 ¨                               
                               
 Ackermann numbers are pretty big, but theyre not yet big enough. The quest for still bigger numbers takes us back to the formalists. After Ackermann demonstrated that primitive recursive isnt what we mean by computable, the question still stood: what do we mean by computable? In 1936, Alonzo Church and Alan Turing independently answered this question. While Church answered using a logical formalism called the lambda calculus, Turing answered using an idealized computing machinethe Turing machinethat, in essence, is equivalent to every Compaq, Dell, Macintosh, and Cray in the modern world. Turings paper describing his machine, "On Computable Numbers," is rightly celebrated as the founding document of computer science.                    
                               
 "Computing," said Turing,                               
                               
 is normally done by writing certain symbols on paper. We may suppose this paper to be divided into squares like a childs arithmetic book. In elementary arithmetic the 2-dimensional character of the paper is sometimes used. But such use is always avoidable, and I think it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, on a tape divided into squares.                        
                               
 Turing continued to explicate his machine using ingenious reasoning from first principles. The tape, said Turing, extends infinitely in both directions, since a theoretical machine ought not be constrained by physical limits on resources. Furthermore, theres a symbol written on each square of the tape, like the 1s and 0s in a modern computers memory. But how are the symbols manipulated? Well, theres a tape head moving back and forth along the tape, examining one square at a time, writing and erasing symbols according to definite rules. The rules are the tape heads program: change them, and you change what the tape head does.                     
                               
 Turings august insight was that we can program the tape head to carry out any computation. Turing machines can add, multiply, extract cube roots, sort, search, spell-check, parse, play Tic-Tac-Toe, list the Ackermann sequence. If we represented keyboard input, monitor output, and so forth as symbols on the tape, we could even run Windows on a Turing machine. But theres a problem. Set a tape head loose on a sequence of symbols, and it might stop eventually, or it might run foreverlike the fabled programmer who gets stuck in the shower because the instructions on the shampoo bottle read "lather, rinse, repeat." If the machines going to run forever, itd be nice to know this in advance, so that we dont spend an eternity waiting for it to finish. But how can we determine, in a finite amount of time, whether something will go on endlessly? If you bet a friend that your watch will never stop ticking, when could you declare victory? But maybe theres some ingenious program that can examine other programs and tell us, infallibly, whether theyll ever stop running. We just havent thought of it yet.              
                               
 Nope. Turing proved that this problem, called the Halting Problem, is unsolvable by Turing machines. The proof is a beautiful example of self-reference. It formalizes an old argument about why you can never have perfect introspection: because if you could, then you could determine what you were going to do ten seconds from now, and then do something else. Turing imagined that there was a special machine that could solve the Halting Problem. Then he showed how we could have this machine analyze itself, in such a way that it has to halt if it runs forever, and run forever if it halts. Like a hound that finally catches its tail and devours itself, the mythical machine vanishes in a fury of contradiction. (Thats the sort of thing you dont say in a research paper.)                   
                               
 ¨                               
                               
 "Very nice," you say (or perhaps you say, "not nice at all"). "But what does all this have to do with big numbers?" Aha! The connection wasnt published until May of 1962. Then, in the Bell System Technical Journal, nestled between pragmatically-minded papers on "Multiport Structures" and "Waveguide Pressure Seals," appeared the modestly titled "On Non-Computable Functions" by Tibor Rado. In this paper, Rado introduced the biggest numbers anyone had ever imagined.                        
                               
 His idea was simple. Just as we can classify words by how many letters they contain, we can classify Turing machines by how many rules they have in the tape head. Some machines have only one rule, others have two rules, still others have three rules, and so on. But for each fixed whole number N, just as there are only finitely many distinct words with N letters, so too are there only finitely many distinct machines with N rules. Among these machines, some halt and others run forever when started on a blank tape. Of the ones that halt, asked Rado, whats the maximum number of steps that any machine takes before it halts? (Actually, Rado asked mainly about the maximum number of symbols any machine can write on the tape before halting. But the maximum number of steps, which Rado called S(n), has the same basic properties and is easier to reason about.)                  
                               
 Rado called this maximum the Nth "Busy Beaver" number. (Ah yes, the early 1960s were a more innocent age.) He visualized each Turing machine as a beaver bustling busily along the tape, writing and erasing symbols. The challenge, then, is to find the busiest beaver with exactly N rules, albeit not an infinitely busy one. We can interpret this challenge as one of finding the "most complicated" computer program N bits long: the one that does the most amount of stuff, but not an infinite amount.                       
                               
 Now, suppose we knew the Nth Busy Beaver number, which well call BB(N). Then we could decide whether any Turing machine with N rules halts on a blank tape. Wed just have to run the machine: if it halts, fine; but if it doesnt halt within BB(N) steps, then we know it never will halt, since BB(N) is the maximum number of steps it could make before halting. Similarly, if you knew that all mortals died before age 200, then if Sally lived to be 200, you could conclude that Sally was immortal. So no Turing machine can list the Busy Beaver numbersfor if it could, it could solve the Halting Problem, which we already know is impossible.                     
                               
 But heres a curious fact. Suppose we could name a number greater than the Nth Busy Beaver number BB(N). Call this number D for dam, since like a beaver dam, its a roof for the Busy Beaver below. With D in hand, computing BB(N) itself becomes easy: we just need to simulate all the Turing machines with N rules. The ones that havent halted within D stepsthe ones that bash through the dams roofnever will halt. So we can list exactly which machines halt, and among these, the maximum number of steps that any machine takes before it halts is BB(N).                      
                               
 Conclusion? The sequence of Busy Beaver numbers, BB(1), BB(2), and so on, grows faster than any computable sequence. Faster than exponentials, stacked exponentials, the Ackermann sequence, you name it. Because if a Turing machine could compute a sequence that grows faster than Busy Beaver, then it could use that sequence to obtain the Dsthe beaver dams. And with those Ds, it could list the Busy Beaver numbers, which (sound familiar?) we already know is impossible. The Busy Beaver sequence is non-computable, solely because it grows stupendously fasttoo fast for any computer to keep up with it, even in principle.                     
                               
 This means that no computer program could list all the Busy Beavers one by one. It doesnt mean that specific Busy Beavers need remain eternally unknowable. And in fact, pinning them down has been a computer science pastime ever since Rado published his article. Its easy to verify that BB(1), the first Busy Beaver number, is 1. Thats because if a one-rule Turing machine doesnt halt after the very first step, itll just keep moving along the tape endlessly. Theres no room for any more complex behavior. With two rules we can do more, and a little grunt work will ascertain that BB(2) is 6. Six steps. What about the third Busy Beaver? In 1965 Rado, together with Shen Lin, proved that BB(3) is 21. The task was an arduous one, requiring human analysis of many machines to prove that they dont haltsince, remember, theres no algorithm for listing the Busy Beaver numbers. Next, in 1983, Allan Brady proved that BB(4) is 107. Unimpressed so far? Well, as with the Ackermann sequence, dont be fooled by the first few numbers.               
                               
 In 1984, A.K. Dewdney devoted a Scientific American column to Busy Beavers, which inspired amateur mathematician George Uhing to build a special-purpose device for simulating Turing machines. The device, which cost Uhing less than $100, found a five-rule machine that runs for 2,133,492 steps before haltingestablishing that BB(5) must be at least as high. Then, in 1989, Heiner Marxen and Jürgen Buntrock discovered that BB(5) is at least 47,176,870. To this day, BB(5) hasnt been pinned down precisely, and it could turn out to be much higher still. As for BB(6), Marxen and Buntrock set another record in 1997 by proving that its at least 8,690,333,381,690,951. A formidable accomplishment, yet Marxen, Buntrock, and the other Busy Beaver hunters are merely wading along the shores of the unknowable. Humanity may never know the value of BB(6) for certain, let alone that of BB(7) or any higher number in the sequence.                 
                               
 Indeed, already the top five and six-rule contenders elude us: we cant explain how they work in human terms. If creativity imbues their design, its not because humans put it there. One way to understand this is that even small Turing machines can encode profound mathematical problems. Take Goldbachs conjecture, that every even number 4 or higher is a sum of two prime numbers: 10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could design a Turing machine with, oh, lets say 100 rules, that tests each even number to see whether its a sum of two primes, and halts when and if it finds a counterexample to the conjecture. Then knowing BB(100), we could in principle run this machine for BB(100) steps, decide whether it halts, and thereby resolve Goldbachs conjecture. We need not venture far in the sequence to enter the lair of basilisks.                  
                               
 But as Rado stressed, even if we cant list the Busy Beaver numbers, theyre perfectly well-defined mathematically. If you ever challenge a friend to the biggest number contest, I suggest you write something like this:                            
                               
 BB(11111)Busy Beaver shift #1, 6, 21, etc                              
                               
 If your friend doesnt know about Turing machines or anything similar, but only about, say, Ackermann numbers, then youll win the contest. Youll still win even if you grant your friend a handicap, and allow him the entire lifetime of the universe to write his number. The key to the biggest number contest is a potent paradigm, and Turings theory of computation is potent indeed.                         
                               
 ¨                               
                               
 But what if your friend knows about Turing machines as well? Is there a notational system for big numbers more powerful than even Busy Beavers?                             
                               
 Suppose we could endow a Turing machine with a magical ability to solve the Halting Problem. What would we get? Wed get a super Turing machine: one with abilities beyond those of any ordinary machine. But now, how hard is it to decide whether a super machine halts? Hmm. It turns out that not even super machines can solve this super Halting Problem, for the same reason that ordinary machines cant solve the ordinary Halting Problem. To solve the Halting Problem for super machines, wed need an even more powerful machine: a super duper machine. And to solve the Halting Problem for super duper machines, wed need a super duper pooper machine. And so on endlessly. This infinite hierarchy of ever more powerful machines was formalized by the logician Stephen Kleene in 1943 (although he didnt use the term super duper pooper).                  
                               
 Imagine a novel, which is imbedded in a longer novel, which itself is imbedded in an even longer novel, and so on ad infinitum. Within each novel, the characters can debate the literary merits of any of the sub-novels. But, by analogy with classes of machines that cant analyze themselves, the characters can never critique the novel that they themselves are in. (This, I think, jibes with our ordinary experience of novels.) To fully understand some reality, we need to go outside of that reality. This is the essence of Kleenes hierarchy: that to solve the Halting Problem for some class of machines, we need a yet more powerful class of machines.                     
                               
 And theres no escape. Suppose a Turing machine had a magical ability to solve the Halting Problem, and the super Halting Problem, and the super duper Halting Problem, and the super duper pooper Halting Problem, and so on endlessly. Surely this would be the Queen of Turing machines? Not quite. As soon as we want to decide whether a Queen of Turing machines halts, we need a still more powerful machine: an Empress of Turing machines. And Kleenes hierarchy continues.                        
                               
 But hows this relevant to big numbers? Well, each level of Kleenes hierarchy generates a faster-growing Busy Beaver sequence than do all the previous levels. Indeed, each levels sequence grows so rapidly that it can only be computed by a higher level. For example, define BB2(N) to be the maximum number of steps a super machine with N rules can make before halting. If this super Busy Beaver sequence were computable by super machines, then those machines could solve the super Halting Problem, which we know is impossible. So the super Busy Beaver numbers grow too rapidly to be computed, even if we could compute the ordinary Busy Beaver numbers.                     
                               
 You might think that now, in the biggest-number contest, you could obliterate even an opponent who uses the Busy Beaver sequence by writing something like this:                             
                               
 BB2(11111).                               
                               
 But not quite. The problem is that Ive never seen these "higher-level Busy Beavers" defined anywhere, probably because, to people who know computability theory, theyre a fairly obvious extension of the ordinary Busy Beaver numbers. So our reasonable modern mathematician wouldnt know what number you were naming. If you want to use higher-level Busy Beavers in the biggest number contest, heres what I suggest. First, publish a paper formalizing the concept in some obscure, low-prestige journal. Then, during the contest, cite the paper on your index card.                      
                               
 To exceed higher-level Busy Beavers, wed presumably need some new computational model surpassing even Turing machines. I cant imagine what such a model would look like. Yet somehow I doubt that the story of notational systems for big numbers is over. Perhaps someday humans will be able concisely to name numbers that make Busy Beaver 100 seem as puerile and amusingly small as our noblemans eighty-three. Or if well never name such numbers, perhaps other civilizations will. Is a biggest number contest afoot throughout the galaxy?                       
                               
 ¨                               
                               
 You might wonder why we cant transcend the whole parade of paradigms, and name numbers by a system that encompasses and surpasses them all. Suppose you wrote the following in the biggest number contest:                            
                               
 The biggest whole number nameable with 1,000 characters of English text                              
                               
 Surely this number exists. Using 1,000 characters, we can name only finitely many numbers, and among these numbers there has to be a biggest. And yet weve made no reference to how the numbers named. The English text could invoke Ackermann numbers, or Busy Beavers, or higher-level Busy Beavers, or even some yet more sweeping concept that nobodys thought of yet. So unless our opponent uses the same ploy, weve got him licked. What a brilliant idea! Why didnt we think of this earlier?                       
                               
 Unfortunately it doesnt work. We might as well have written                              
                               
 One plus the biggest whole number nameable with 1,000 characters of English text                              
                               
 This number takes at least 1,001 characters to name. Yet weve just named it with only 80 characters! Like a snake that swallows itself whole, our colossal number dissolves in a tumult of contradiction. What gives?                            
                               
 The paradox Ive just described was first published by Bertrand Russell, who attributed it to a librarian named G. G. Berry. The Berry Paradox arises not from mathematics, but from the ambiguity inherent in the English language. Theres no surefire way to convert an English phrase into the number it names (or to decide whether it names a number at all), which is why I invoked a "reasonable modern mathematician" in the rules for the biggest number contest. To circumvent the Berry Paradox, we need to name numbers using a precise, mathematical notational system, such as Turing machineswhich is exactly the idea behind the Busy Beaver sequence. So in short, theres no wily language trick by which to surpass Archimedes, Ackermann, Turing, and Rado, no royal road to big numbers.                   
                               
 You might also wonder why we cant use infinity in the contest. The answer is, for the same reason why we cant use a rocket car in a bike race. Infinity is fascinating and elegant, but its not a whole number. Nor can we subtract from infinity to yield a whole number. Infinity minus 17 is still infinity, whereas infinity minus infinity is undefined: it could be 0, 38, or even infinity again. Actually I should speak of infinities, plural. For in the late nineteenth century, Georg Cantor proved that there are different levels of infinity: for example, the infinity of points on a line is greater than the infinity of whole numbers. Whats more, just as theres no biggest number, so too is there no biggest infinity. But the quest for big infinities is more abstruse than the quest for big numbers. And it involves, not a succession of paradigms, but essentially one: Cantors.                 
                               
 ¨                               
                               
 So here we are, at the frontier of big number knowledge. As Euclids disciple supposedly asked, "what is the use of all this?" Weve seen that progress in notational systems for big numbers mirrors progress in broader realms: mathematics, logic, computer science. And yet, though a mirror reflects reality, it doesnt necessarily influence it. Even within mathematics, big numbers are often considered trivialities, their study an idle amusement with no broader implications. I want to argue a contrary view: that understanding big numbers is a key to understanding the world.                      
                               
 Imagine trying to explain the Turing machine to Archimedes. The genius of Syracuse listens patiently as you discuss the papyrus tape extending infinitely in both directions, the time steps, states, input and output sequences. At last he explodes.                           
                               
 "Foolishness!" he declares (or the ancient Greek equivalent). "All youve given me is an elaborate definition, with no value outside of itself."                             
                               
 How do you respond? Archimedes has never heard of computers, those cantankerous devices that, twenty-three centuries from his time, will transact the worlds affairs. So you cant claim practical application. Nor can you appeal to Hilbert and the formalist program, since Archimedes hasnt heard of those either. But then it hits you: the Busy Beaver sequence. You define the sequence for Archimedes, convince him that BB(1000) is more than his 1063 grains of sand filling the universe, more even than 1063 raised to its own power 1063 times. You defy him to name a bigger number without invoking Turing machines or some equivalent. And as he ponders this challenge, the power of the Turing machine concept dawns on him. Though his intuition may never apprehend the Busy Beaver numbers, his reason compels him to acknowledge their immensity. Big numbers have a way of imbuing abstract notions with reality.                 
                               
 Indeed, one could define science as reasons attempt to compensate for our inability to perceive big numbers. If we could run at 280,000,000 meters per second, thered be no need for a special theory of relativity: itd be obvious to everyone that the faster we go, the heavier and squatter we get, and the faster time elapses in the rest of the world. If we could live for 70,000,000 years, thered be no theory of evolution, and certainly no creationism: we could watch speciation and adaptation with our eyes, instead of painstakingly reconstructing events from fossils and DNA. If we could bake bread at 20,000,000 degrees Kelvin, nuclear fusion would be not the esoteric domain of physicists but ordinary household knowledge. But we cant do any of these things, and so we have science, to deduce about the gargantuan what we, with our infinitesimal faculties, will never sense. If people fear big numbers, is it any wonder that they fear science as well and turn for solace to the comforting smallness of mysticism?               
                               
 But do people fear big numbers? Certainly they do. Ive met people who dont know the difference between a million and a billion, and dont care. We play a lottery with six ways to win!, overlooking the twenty million ways to lose. We yawn at six billion tons of carbon dioxide released into the atmosphere each year, and speak of sustainable development in the jaws of exponential growth. Such cases, it seems to me, transcend arithmetical ignorance and represent a basic unwillingness to grapple with the immense.                       
                               
 Whence the cowering before big numbers, then? Does it have a biological origin? In 1999, a group led by neuropsychologist Stanislas Dehaene reported evidence in Science that two separate brain systems contribute to mathematical thinking. The group trained Russian-English bilinguals to solve a set of problems, including two-digit addition, base-eight addition, cube roots, and logarithms. Some subjects were trained in Russian, others in English. When the subjects were then asked to solve problems approximatelyto choose the closer of two estimatesthey performed equally well in both languages. But when asked to solve problems exactly, they performed better in the language of their training. Whats more, brain-imaging evidence showed that the subjects parietal lobes, involved in spatial reasoning, were more active during approximation problems; while the left inferior frontal lobes, involved in verbal reasoning, were more active during exact calculation problems. Studies of patients with brain lesions paint the same picture: those with parietal lesions sometimes cant decide whether 9 is closer to 10 or to 5, but remember the multiplication table; whereas those with left-hemispheric lesions sometimes cant decide whether 2+2 is 3 or 4, but know that the answer is closer to 3 than to 9. Dehaene et al. conjecture that humans represent numbers in two ways. For approximate reckoning we use a mental number line, which evolved long ago and which we likely share with other animals. But for exact computation we use numerical symbols, which evolved recently and which, being language-dependent, are unique to humans. This hypothesis neatly explains the experiments findings: the reason subjects performed better in the language of their training for exact computation but not for approximation problems is that the former call upon the verbally-oriented left inferior frontal lobes, and the latter upon the spatially-oriented parietal lobes.
                               
 If Dehaene et al.s hypothesis is correct, then which representation do we use for big numbers? Surely the symbolic onefor nobodys mental number line could be long enough to contain , 5 pentated to the 5, or BB(1000). And here, I suspect, is the problem. When thinking about 3, 4, or 7, were guided by our spatial intuition, honed over millions of years of perceiving 3 gazelles, 4 mates, 7 members of a hostile clan. But when thinking about BB(1000), we have only language, that evolutionary neophyte, to rely upon. The usual neural pathways for representing numbers lead to dead ends. And this, perhaps, is why people are afraid of big numbers.                     
                               
 Could early intervention mitigate our big number phobia? What if second-grade math teachers took an hour-long hiatus from stultifying busywork to ask their students, "How do you name really, really big numbers?" And then told them about exponentials and stacked exponentials, tetration and the Ackermann sequence, maybe even Busy Beavers: a cornucopia of numbers vaster than any theyd ever conceived, and ideas stretching the bounds of their imaginations.                        
                               
 Who can name the bigger number? Whoever has the deeper paradigm. Are you ready? Get set. Go.                              
                               
 References                               
                               
 Petr Beckmann, A History of Pi, Golem Press, 1971.                              
                               
 Allan H. Brady, "The Determination of the Value of Rados Noncomputable Function Sigma(k) for Four-State Turing Machines," Mathematics of Computation, vol. 40, no. 162, April 1983, pp 647- 665.                            
                               
 Gregory J. Chaitin, "The Berry Paradox," Complexity, vol. 1, no. 1, 1995, pp. 26- 30. At http://www.umcs.maine.edu/~chaitin/unm2.html.                             
                               
 A.K. Dewdney, The New Turing Omnibus: 66 Excursions in Computer Science, W.H. Freeman, 1993.                              
                               
 S. Dehaene and E. Spelke and P. Pinel and R. Stanescu and S. Tsivkin, "Sources of Mathematical Thinking: Behavioral and Brain-Imaging Evidence," Science, vol. 284, no. 5416, May 7, 1999, pp. 970- 974.                            
                               
 Douglas Hofstadter, Metamagical Themas: Questing for the Essence of Mind and Pattern, Basic Books, 1985. Chapter 6, "On Number Numbness," pp. 115- 135.                             
                               
 Robert Kanigel, The Man Who Knew Infinity: A Life of the Genius Ramanujan, Washington Square Press, 1991.                             
                               
 Stephen C. Kleene, "Recursive predicates and quantifiers," Transactions of the American Mathematical Society, vol. 53, 1943, pp. 41- 74.                             
                               
 Donald E. Knuth, Selected Papers on Computer Science, CSLI Publications, 1996. Chapter 2, "Mathematics and Computer Science: Coping with Finiteness," pp. 31- 57.                             
                               
 Dexter C. Kozen, Automata and Computability, Springer-Verlag, 1997.                              
                               
 , The Design and Analysis of Algorithms, Springer-Verlag, 1991.                              
                               
 Shen Lin and Tibor Rado, "Computer studies of Turing machine problems," Journal of the Association for Computing Machinery, vol. 12, no. 2, April 1965, pp. 196- 212.                             
                               
 Heiner Marxen, Busy Beaver, at http://www.drb.insel.de/~heiner/BB/.                              
                               
  and Jürgen Buntrock, "Attacking the Busy Beaver 5," Bulletin of the European Association for Theoretical Computer Science, no. 40, February 1990, pp. 247- 251.                             
                               
 Tibor Rado, "On Non-Computable Functions," Bell System Technical Journal, vol. XLI, no. 2, May 1962, pp. 877- 884.                             
                               
 Rudy Rucker, Infinity and the Mind, Princeton University Press, 1995.                              
                               
 Carl Sagan, Billions & Billions, Random House, 1997.                              
                               
 Michael Somos, "Busy Beaver Turing Machine." At http://grail.cba.csuohio.edu/~somos/bb.html.                              
                               
 Alan Turing, "On computable numbers, with an application to the Entscheidungsproblem," Proceedings of the London Mathematical Society, Series 2, vol. 42, pp. 230- 265, 1936. Reprinted in Martin Davis (ed.), The Undecidable, Raven, 1965.                           
                               
 Ilan Vardi, "Archimedes, the Sand Reckoner," at http://www.ihes.fr/~ilan/sand_reckoner.ps.                              
                               
 Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC Press, 1999. Entry on "Large Number" at http://www.treasure-troves.com/math/LargeNumber.html.                             
                               

 * Back to Writings page
 * Back to Scott's homepage
 * Back to Scott's blog
Who Can Name the Bigger Number?
https://www.scottaaronson.com/writings/bignumbers.html
None
2018-12-10T09:44:00-05:00
<div><div><p>
In a previous post, I discussed <a href="http://www.ericherboso.org/2012/12/really-big-numbers.html">Really Big Numbers</a>, moving from many children's example of a big number, a million, up past what most people I meet would think of as a huge number, a googol, and ultimately going through Graham's number, TREE(3), the busy beaver function, infinities and beyond. I wasn't aware of it at the time, but a much better version of that post already existed: <i><a href="http://www.scottaaronson.com/writings/bignumbers.html">Who Can Name the Bigger Number?</a></i>, by Scott Aaronson.</p><p>

In my original post, <a href="https://www.ericherboso.org/2018/12/slow-growing-functions.html">I made a few errors</a> in the section about fast growing functions. Some kind commentors helped correct the most egregious errors, but the ensuing corrections littered that entire section of the post with strikethrough text that I was never really happy with. Now, six years later, I'd like to finally make up for my mistakes.</p>
<h3>
<br/>The Goal</h3>
<p>
I'd like to name some really, really big numbers. I'm not going to talk about the smaller ones, nor the ones that delve into infinities; you can read the previous post for that. Here I just want to point toward some really big finite numbers. The numbers I'm aiming for are counting numbers, like 1, 2, or a billion. They're not infinite in size. These are numbers where, if someone asked you to write a really, really big number, these would be way beyond what the questioner was thinking of, and yet still wouldn't be infinite in extent.</p>

<h3>
Why Functions?</h3>
<p>
We always use functions when writing numbers. It's just that most of the time, it's invisible to us. If we're counting apples, we might make a hatch mark (or tally mark) for the first apple, another hatch for the second ("‖"), and so on. This works fine for up to a dozen apples or so, but it starts to get pretty difficult to understand at a glance. You might fix this by making every fifth hatch cross over the previous four ("卌"), but you quickly run into a problem again if you get too many sets of five hatch marks.</p><p>

It's easier to come up with a better notation, like using numerals. Now we can use "1" or "5", rather than actually write out all those hatch marks. Then we can use a simple function to make our notation easier to follow. The rightmost numeral is the ones place, then next to the left is the tens place, and the next to the left is the hundreds place, and so on. So "123" means (1*100)+(2*10)+(3*1). Of course, I'm being loose with definitions here, as I've written "100" and "10" using the very system I'm trying to define. Feel to replace with tally marks: 2*10 is ‖*卌卌.</p><p>

As you can see, functions are integral parts of any notation. So when I start turning to new notations by using functions to describe them, you shouldn't act as though this is somehow fundamentally different from the notations that you likely already use in everyday life. Using Knuth arrow notation is no less valid for saying a number's name than writing "123". They're both just names that point at a specific number of tally marks.</p>

<h3>
Defining Operations</h3>
<p>
Let's start with addition. Addition is an operation, not a number. But it's easier to talk in terms of operations when you get to really big numbers, so I want to start here. We'll begin with a first approximation of a really big number: 123. In terms of addition, you might say it is 100+23, or maybe 61+62. Or you may want to break it down to its tally marks: 卌卌卌…卌⦀. This is all quite unwieldy, though. I'd prefer to save space when typing all this out. So let's instead use the relatively small example of 9, not 123. You might not think of 9 as a really big number, but we've only just started. The first function, F₁(x,y), involves taking the numeral X and doing whatever operation it is Y times. <i>In this series of functions, I'm always going to use 3 for both x and y to make things as simple as possible.</i> F₁ is addition, so F₁(3,3)=3+3+3=9.</p><p>

Each subsequent function Fₓ is just a repetition of the previous function. Addition is repeated counting, but when you repeat addition, that's just multiplication. So our second operation, multiplication, can be looked at as F₂=3*3*3=27.</p><p>

(As an aside, a similar function to Fₓ(3,2) can be seen at the <a href="http://oeis.org/A054871">On-Line Encyclopedia of Integer Sequences</a>. Their a(n) is equivalent to our Fₓ(3,2), where x=n-1. So their a(2) is our F₁(3,2). You may also notice that F₂(3,2)=F₁(3,3),  so although the OEIS sequence A054871 is out of sync on the inputs, the series nevertheless matches what we're discussing here.)</p><p>

I want to pause here to point out that multiplication grows more quickly than addition. Look at the first few terms of F₁:</p><ul>
<li>F₁(3,1)=3</li>
<li>F₁(3,2)=3+3=6</li>
<li>F₁(3,3)=3+3+3=9</li>
</ul><p>
Then compare to the first few terms of F₂:</p><ul>
<li>F₂(3,1)=3</li>
<li>F₂(3,2)=3*3=9</li>
<li>F₂(3,3)=3*3*3=27</li>
</ul><p>
What's important here isn't that 27&gt;9. What's important is that the latter function is growing more quickly than the previous one.<br/>
We can keep going to F₃, which uses the exponentiation operation. This is as high as most high school math classes go. F₃=3^3^3=19683. The first few terms of F₃ are:</p><ul>
<li>F₃(3,1)=3</li>
<li>F₃(3,2)=3^3=27</li>
<li>F₃(3,3)=3^3^3=19683</li>
</ul><p>
You can see that each subsequent function is growing more and more quickly, such that the only the third term, Fₓ(3,3), is fast approaching really big numbers.</p><p>

Next in the series is F₄, which uses <a href="https://en.wikipedia.org/wiki/Tetration">tetration</a>. F₄=3⇈3⇈3=7,625,597,484,987. Here I am using Knuth arrow notation for the operator symbol, but the idea is the same as all the previous operations. Addition is repeated counting. Multiplication is repeated addition. Exponentiation is repeated multiplication. Tetration is repeated exponentiation. In other words:</p><ul>
<li>Multiplication is repeated addition:<br/>
X*Y = X+X+…+X, where there are Y instances of X in this series.<br/>
In the case of F₂(3,2), 3*3=3+3+3.</li>
<li>Exponentiation is repeated multiplication:<br/>
X^Y = X*X*…*X, where there are Y Xs.<br/>
3^3=3*3*3</li>
<li>Tetration is repeated exponentiation:<br/>
X⇈Y = X^X^…^X, where there are Y Xs.<br/>
3⇈3=3^3^3</li>
</ul><p>
Pentation is next: F₅=3↑↑↑3↑↑↑3. It takes a bit of work to figure out this value in simpler terms.</p><ul>
<li>F₅=3↑↑↑3↑↑↑3<br/>
=3↑↑↑(3↑↑↑3)<br/>
=3↑↑↑(3⇈3⇈3)<br/>
=3↑↑↑(3⇈(3⇈3))<br/>
=3↑↑↑(3⇈(7,625,597,484,987))</li>
</ul>
<p><a href="https://wikimedia.org/api/rest_v1/media/math/render/png/6f3571ab9a1ce368d598df015333e5d2d26a06a8"></a></p>
<p>
Remember that tetration is repeated exponentiation, so the part in the parentheses there (3⇈7,625,597,484,987) is 3 raised to the 3 raised to the 3 raised to the 3…raised to the 3, where there are 7,625,597,484,987 instances of 3 in this power tower. The image to the right shows what I mean by a power tower: it's a^a^…^a. In our example, it's 3^3^…^3, with 7,625,597,484,987 threes. <i>And this is just the part in the parentheses.</i> You still have to take 3↑↑↑(N), where N is the huge power tower of threes. It's truly difficult to accurately describe just how big this number truly is.</p>


<h3>
Fastly Fast</h3>

<p>
So far I've described the first few functions, F₁, F₂, F₃, F₄, and F₅. These are each associated with an operation. I could go on from pentation to hexation, but instead I want to focus on these increasingly fast growing functions. F₅(3,3) is already mindboggingly huge, so it's difficult to get across how huge F₆(3,3) is in comparison. Think about the speed at which we get to huge numbers from F₁ to F₂ to F₃, and then realize that this is nothing compared to where you get when you move to F₄. And again how this is absolutely and completely dwarfed by F₅. This happens yet again at F₆. It's not just much bigger. It's not just bigger than F₅ by the hugeness of F₅. It's not twice as big, or 100 times as big, nor even F₅ times as big. (After all, the word "times" denotes puny multiplication.) It's not F₅^F₅ even. Nor F₅⇈F₅. Nor even F₅↑↑↑F₅. No, F₆=3⇈⇈3⇈⇈3=3⇈⇈(F₅(3,3)). I literally cannot stress how freakishly massive this number is. And yet: it is just F₆.</p>

<p>
This is why I wanted to focus on fast growing functions. Each subsequent function is MUCH bigger than the last, in such a way that the previous number basically approximates to zero. So imagine the size of the numbers as we move along to faster and faster growing functions.</p>

<p>
These functions grow fast because they use recursion. Each subsequent function is doing what the last function did, but does it repeatedly. In our case, Fₓ(3,3) is just taking the previous value and using the next highest operator on it. F₂(3,3)=3*F₁(3,3). F₃(3,3)=3^F₂(3,3). F₄(3,3)=3⇈F₃(3,3). F₅(3,3)=3↑↑↑F₄(3,3). And as we saw two paragraphs ago, F₆(3,3)=3⇈⇈F₅(3,3).</p>

<p>
I chose this recursive series of functions because I wanted to match up with the examples I used in <a href="http://www.ericherboso.org/2012/12/really-big-numbers.html">my previous discussion of really big numbers</a>. But most mathematicians use the fast growing hierarchy to describe this kind of thing. Think of it as a yardstick against which we can compare other fast growing functions.</p>


<h3>
Fast Growing Hierarchy</h3>

<p>
We start with F₀(n)=n+1. This is a new function, unrelated to the multiple input function we've used earlier in this blog post. F₀(n) is the first rung of the fast growing hierarchy. If you want to consider a specific number associated with each rung of the hierarchy, we might choose n=3. So F₀(3)=3+1=4.</p>

<p>
We then use recursion to define each subsequent function in the hierarchy. Fₓ₊₁(n)=Fₓ(Fₓ(…Fₓ(n)…)), where there are n instances of Fₓ.</p>

<p>
So F₁(n)=F₀(F₀(…F₀(n)…)), with n F₀s. This is equivalent to n+1+1+…+1, where there are n 1s. This means F₁(n)=n+n=2n. In our example, F₁(3)=6.</p>

<p>
Next is F₂(n)=F₁(F₁(…F₁(n)…)), with n F₁s. This is just 2*2*…*2*n, with n 2s. So F₂(n)=n2^n. In our example, F₂(3)=3*(2^3)=24.</p>

<p>
At each step in the hierarchy, we roughly increase to the next level of operation each time. F₀ is basically addition; F₁ is multiplication; F₂ is exponentiation. It's not exact, but it's in the same ballpark. This corresponds closely to the function I defined earlier in this blog post. Mathematicians use the fast growing hierarchy to give an estimate of how big other functions are. My F₂(3,3) from earlier is roughly F₂(n) in the FGH. (F₂(3,3)=27, while F₂(3)=24.) (<i>Egads, do I regret using F for both functions, even though it should be clear since one has multiple inputs.</i>)</p>


<h3>
Diagonalization</h3>

<p>
So at this point you probably get the gist of the fast growing hierarchy for F₂, F₃, F₆, etc. Even though they are mind-boggingly large numbers, you may be able to grasp what we mean we talk about F₉, or F₉₉. These functions grow faster and faster as you go along the series of functions, and there's an infinite number of functions in the list. We can talk about Fₓ with the subscript x being a googol, or 3↑↑↑3↑↑↑3. These functions grow <i>fast</i>. But we can do even better.</p>

<p>
Let's define F𝜔(n) as Fn(n). (<i>Forgive the lack of subscripts here; we're about to get complex on what's down there.</i>) Now our input n is going to be used not just as the input in the function, but also as the FGH rank of a function that we already defined above. So, in our example, F𝜔(3)=F₃(3)=F₂(F₂(F₂(3)))=F₂(F₂(24))=F₂(24(2^24))=F₂(24(16777216))=F₂(402653184)= 402653184*(2^402653184)≈10^120000000.</p>

<p>
As you can see, F𝜔(n) grows incredibly quickly. More quickly, in fact, than any integer value of Fₓ(n). This means that the sequence of functions I've been talking about previously in this blog post can't even get close to the fast growing F𝜔(n), even though there are infinite integer values you could plug in for Fₓ. An example of a famous function that grows at this level would be the <a href="https://en.wikipedia.org/wiki/Ackermann_function">Ackermann function</a>.</p>

<p>
But we can keep going. Consider F𝜔₊₁(n), which is defined exactly as we defined the FGH earlier. F𝜔₊₁(n)=F𝜔(F𝜔(…F𝜔(n)…)), where there are n F𝜔s. This grows faster than F𝜔(n) in a way that is exceedingly difficult to describe. Remember that each function in this sequence grows so much faster than the previous function so as to make it approximate zero for a given input. An example of a famous function that grows at this level would be Graham's function, of which <a href="https://en.wikipedia.org/wiki/Graham%27s_number">Graham's number</a> is oft cited as a particularly large number. In particular, F𝜔₊₁(64)&gt;G₆₄.</p>

<p>
There's no reason to stop now. We can do F𝜔₊₂(n) or F𝜔₊₆(n) or, in general, F𝜔₊ₐ(n), where a can be any natural number, as high as you might please. You can use a=googol or a=3↑↑↑3↑↑↑3 or even a=F𝜔(3↑↑↑3↑↑↑3). But none of these would be as large as if we introduced a new definition: F𝜔*₂(n)=F𝜔₊n(n). This is defined in exactly the same way that we originally defined F𝜔(n), where the input not only goes into the function, but also into the FGH rank of the function itself. F𝜔*₂(n) grows even faster than any F𝜔₊ₐ(n), regardless of what value you enter in as a.</p>

<p>
I'm sure you see by now where this is going. We have F𝜔*₂₊₁(n) next, and so on and so forth, until we get F𝜔*₂₊ₐ(n), with an arbitrarily large a. Then we diagonalize again to get F𝜔*₃(n), and then the family of F𝜔*₃₊ₐ(n). This can on indefinitely, until we get to F𝜔*ₑ₊ₐ(n), where e can be arbitrarily large. A further diagonalization can then be used to create F𝜔*𝜔(n)=F𝜔²(n), which grows faster than F𝜔*ₑ₊ₐ(n) for any combination of e and a.</p>

<p>
Yet F𝜔²(n) isn't a stopping point for us. Beyond F𝜔²₊₁(n) lies F𝜔²₊ₐ(n), beyond which is F𝜔²₊𝜔(n), beyond which is the F𝜔²₊𝜔₊ₐ(n) family, and so on, and so forth, past 𝜔²₊𝜔*₂(n), beyond 𝜔²₊𝜔*ₑ₊ₐ(n), all the way to F𝜔<span>³</span>(n). At each step, the functions grow so fast that they completely and utterly dwarf the function before it, and yet we've counted up several times to infinity in this sequence, an infinite number of times, and then did this three times in order to get to F𝜔<span>³</span>(n). <i>These functions grow fast</i>.</p>

<p>
Still, there's more to consider. F𝜔<span>³</span>(n) is followed by F𝜔<span>⁴</span>(n), all the way up to F𝜔<span>ⁿ</span>(n), beyond which lies yet another digonalization to get to F𝜔<span><span>^</span></span>𝜔(n). From here, you can just redo all the above: F𝜔<span><span>^</span></span>𝜔₊ₐ(n) to F𝜔<span><span>^</span></span>𝜔₊𝜔₊ₐ(n) to F𝜔<span><span>^</span></span>𝜔₊₂𝜔₊ₐ(n) to F𝜔<span><span>^</span></span>𝜔₊ₑ𝜔₊ₐ(n) until we have to rediagonalize to F𝜔⇈𝜔(n), which we set equal to Fₑ₀(n) just for the purpose of making it easier to read. There are two famous examples of functions that grow at this level of the FGH: the function G(n) = "the length of the <a href="https://en.wikipedia.org/wiki/Goodstein%27s_theorem">Goodstein sequence</a> starting from n" and the function H(n) = "the maximum length of any <a href="http://math.andrej.com/2008/02/02/the-hydra-game/">Kirby-Paris hydra game</a> starting from a hydra with n heads" are both at the FGH rank of Fₑ₀(n).</p>

<div><p>
You can keep going, obviously. Tetration isn't the end for 𝜔. We can do Fₑ₀₊₁(n), then the whole family of Fₑ₀₊ₐ(n), followed by Fₑ₁(n). And we can keep going, to Fₑ₂(n) and beyond, increasing the exponent arbitrarily large, followed by Fₑ𝜔(n). And this ride just doesn't stop, because you go through the whole infinite sequence of infinite sequences of infinite sequences of infinite sequences of infinite sequences yet again, increasing the subscript of e to the absurd point of ε₀. And then we can repeat that, and repeat again, and again, infinitely many times, creating a subscript tower where ε has a subscript of ε to the subscript of ε to the subscript of ε to the suscript of… -- infinitely many times. At this point the notation gets too unwieldy yet again, so we move on to using another greek letter: 𝛇, where it starts all over again. And we can do this infinite recursion infinitely yet again, until we have a subscript tower of 𝛇s, after which we can call the next function in the series η.</p><p>

Each Greek letter represents an absolutely humongous jump, from 𝜔 to ε to 𝛇 to η. But as you can see it gets increasingly complicated to talk about these FGH functions. Enter the Veblen Hierarchy.</p>

<h3>
Veblen Hierarchy</h3>
<p>
The Veblen Hierarchy starts with 𝜙₀(a)=𝜔<sup>a</sup>, then increases with each subscript to a new greek letter from before. So:</p><ul>
<li>𝜙₀(a)=𝜔<sup>a</sup></li>
<li>𝜙₁(a)= ε<sup>a</sup></li>
<li>𝜙₂(a)= 𝛇<sup>a</sup></li>
<li>𝜙₃(a)= η<sup>a</sup></li>
</ul>
<p>
This FGH grows <i>much</i> faster than the previous one, because it skips over all the infinite recursions to the final tetration of each greek letter, which it defines as the next greek letter in the series. The Veblen Hierarchy grows <i>fast</i>.</p>

<p>
The subscript can get bigger and bigger, reaching 𝜙ₑ(a), where e is arbitrarily large. You can follow this by making 𝜔 the next subscript in the series, then follow the same recursive expansion as before until you get to 𝜔⇈𝜔, which we'd define as ε. And go through the greek letters, one by one, until you've gone through an infinite number of them, after which we can use 𝜙 as the subscript for 𝜙. Then do this again and again, nesting additional 𝜙 as the subscript for each 𝜙, until you have an infinite subscript tower of 𝜙, after which you have to substitute a new notation: Γ₀.</p>

<p>
Here we finally reach a new limit. Γ₀ is as far as you can go by using recursion and diagonalization. It's the point at which we've recursed as much as we can recurse, and diagonalized as much as we can diagonalize. </p>

<p>
But we can go further.</p>

<p>
We can already see Γ₀ as 𝜙(a,0)=a. Let's extend Veblen function notation by defining 𝜙(1,0,0)=γ₀. Adding this extra variable let's us go beyond all the recursion and diagonalization we could do previously. Now we have all of that, and can just add 1.</p>

<p>
Let's explore this sequence:</p>
<div>
<ul>
<li>γ₀=𝜙(1,0,0) Start here.</li>
<li>γ₁=𝜙(1,0,1) Increment the last digit repeatedly.</li>
<li>γ<sub>𝜔</sub>=𝜙(1,0,𝜔) Eventually you reach 𝜔.</li>
</ul>
<p>
After this, the next ordinal is 𝜙(1,1,0). As you can see, we have a new variable to work with. We can keep incrementing the right digit until we get to 𝜔 again, after which we reach 𝜙(1,2,0). And we can do this again and again, until we reach 𝜙(1,𝜔,0). Then the next ordinal would be 𝜙(2,0,0). And we can keep going, more and more until we get to 𝜙(𝜔,𝜔,𝜔). At this point, we're stuck again.</p>
</div>
</div>

<p>
That is, until we add an additional variable.</p>

<p>
So now we have 𝜙(1,0,0,0) as the next ordinal. And we can max this out again until we need to add yet another variable, and then yet another variable, and so on, until we have infinite variables. This is called the Small Veblen Ordinal.</p>

<p><span><span><span><span>ψ<span></span></span><span>(</span><span><span><span><span>Ω</span><span></span></span><span><span><span><span><span><span><span>Ω</span><span></span></span><span><span>ω</span><span></span></span></span></span></span></span><span></span></span></span></span><span>)</span><span>=</span><span>φ</span><span>(</span><span>1</span><span>,</span><span><span><span><span><span><span><span><span><span><span>0</span><span>,</span><span>⋯</span><span>,</span><span>0</span></span><span></span></span><span><span><span>⏟</span></span><span></span></span></span></span></span></span><span></span></span><span><span>ω</span><span></span></span></span></span><span>)</span></span><span></span></span></span><span></span></p>

<p>
Among FGH functions, the Small Veblen Ordinal ranks in just the lower attic of <a href="http://cantorsattic.info/Madore%27s_%CF%88_function#Small_Veblen_ordinal">Cantor's Attic</a>. It's not even the fastest growing function on the page it's listed on. We're nowhere near the top, despite all this work. Of course, there isn't a top -- not really. But what I mean is that we're nowhere near the top of what mathematicians talk about when they work with really large ordinals.</p>


<h3>
…and Beyond!</h3>

<p>
You might notice that at no point did I mention TREE(3), which was one of the numbers I brought up in my last blog post. That's because the TREE() function is way beyond what I've written here. You have to keep climbing, adding new ways of getting to faster and faster growing functions before you reach anything like <a href="https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem">TREE</a>(3). And beyond that to the point of absurdity is <a href="https://en.wikipedia.org/wiki/Friedman%27s_SSCG_function">SSCG</a>(3). And these are all still vastly beneath the Church Kleene Ordinal, which (despite being countable) is uncomputable. This is where you finally run into the Busy Beaver function. The distances between each of these functions that I've mentioned in this paragraph are absurdly long. It took this long to explain up to the Small Veblen Ordinal, and yet it would take equally long to get up to the TREE() function. And then just as long to get to SSCG(). And just as long to Busy Beaver.</p>

<p>
I want to be clear: I'm not saying they are equal distances from each other. I'm saying that it would take an equal amount of time to explain them. At each step of my explanation, I've gotten to absurdly faster and faster growing functions, leaping from concept to concept more quickly than I had any right to. And I would explain that much faster if I kept going, using shorthand to handwave away huge jumps in logic. And yet it would still take that long to explain up to these points.</p>



<p>
If you want to keep going, you may be interested in <a href="https://medium.com/@joshkerr/mind-blown-the-fast-growing-hierarchy-for-laymen-aka-enormous-numbers-d9a865c6443b">this readable medium post</a> by Josh Kerr, the absolutely beautifully written <a href="http://www.scottaaronson.com/writings/bignumbers.html">Who Can Name the Bigger Number?</a> by Scott Aaronson, or the wiki at <a href="http://cantorsattic.info/Cantor%27s_Attic">Cantor's Attic</a>. Parts of this post were inspired by <a href="http://www.ericherboso.org/2012/12/really-big-numbers.html">my own previous post</a> on large numbers and a <a href="https://www.reddit.com/r/askscience/comments/a4mcsa/are_there_alternative_notations_for_hyperlarge/ebg6vdb/">reddit post</a> by PersonUsingAComputer. I'd also like to thank professor Edgar Bering and grad students Bo Waggoner and Charlie Cunningham for helping to correct errors in this essay.</p>

</div></div>||||I||||                      EricHerboso.org

                      An ethics-oriented weblog celebrating effective altruism, philosophy, and other beliefs Eric holds. Also: a place to post random thoughts.

                              10 December, 2018

                                    Fastly Fast Growing Functions

                                      In a previous post, I discussed Really Big Numbers, moving from many children's example of a big number, a million, up past what most people I meet would think of as a huge number, a googol, and ultimately going through Graham's number, TREE(3), the busy beaver function, infinities and beyond. I wasn't aware of it at the time, but a much better version of that post already existed: Who Can Name the Bigger Number?, by Scott Aaronson.

                                      In my original post, I made a few errors in the section about fast growing functions. Some kind commentors helped correct the most egregious errors, but the ensuing corrections littered that entire section of the post with strikethrough text that I was never really happy with. Now, six years later, I'd like to finally make up for my mistakes.


                                      The Goal


                                      I'd like to name some really, really big numbers. I'm not going to talk about the smaller ones, nor the ones that delve into infinities; you can read the previous post for that. Here I just want to point toward some really big finite numbers. The numbers I'm aiming for are counting numbers, like 1, 2, or a billion. They're not infinite in size. These are numbers where, if someone asked you to write a really, really big number, these would be way beyond what the questioner was thinking of, and yet still wouldn't be infinite in extent.

                                      Why Functions?


                                      We always use functions when writing numbers. It's just that most of the time, it's invisible to us. If we're counting apples, we might make a hatch mark (or tally mark) for the first apple, another hatch for the second ("‖"), and so on. This works fine for up to a dozen apples or so, but it starts to get pretty difficult to understand at a glance. You might fix this by making every fifth hatch cross over the previous four ("卌"), but you quickly run into a problem again if you get too many sets of five hatch marks.

                                      It's easier to come up with a better notation, like using numerals. Now we can use "1" or "5", rather than actually write out all those hatch marks. Then we can use a simple function to make our notation easier to follow. The rightmost numeral is the ones place, then next to the left is the tens place, and the next to the left is the hundreds place, and so on. So "123" means (1*100)+(2*10)+(3*1). Of course, I'm being loose with definitions here, as I've written "100" and "10" using the very system I'm trying to define. Feel to replace with tally marks: 2*10 is ‖*卌卌.

                                      As you can see, functions are integral parts of any notation. So when I start turning to new notations by using functions to describe them, you shouldn't act as though this is somehow fundamentally different from the notations that you likely already use in everyday life. Using Knuth arrow notation is no less valid for saying a number's name than writing "123". They're both just names that point at a specific number of tally marks.

                                      Defining Operations


                                      Let's start with addition. Addition is an operation, not a number. But it's easier to talk in terms of operations when you get to really big numbers, so I want to start here. We'll begin with a first approximation of a really big number: 123. In terms of addition, you might say it is 100+23, or maybe 61+62. Or you may want to break it down to its tally marks: 卌卌卌…卌⦀. This is all quite unwieldy, though. I'd prefer to save space when typing all this out. So let's instead use the relatively small example of 9, not 123. You might not think of 9 as a really big number, but we've only just started. The first function, F₁(x,y), involves taking the numeral X and doing whatever operation it is Y times. In this series of functions, I'm always going to use 3 for both x and y to make things as simple as possible. F₁ is addition, so F₁(3,3)=3+3+3=9.

                                      Each subsequent function Fₓ is just a repetition of the previous function. Addition is repeated counting, but when you repeat addition, that's just multiplication. So our second operation, multiplication, can be looked at as F₂=3*3*3=27.

                                      (As an aside, a similar function to Fₓ(3,2) can be seen at the On-Line Encyclopedia of Integer Sequences. Their a(n) is equivalent to our Fₓ(3,2), where x=n-1. So their a(2) is our F₁(3,2). You may also notice that F₂(3,2)=F₁(3,3), so although the OEIS sequence A054871 is out of sync on the inputs, the series nevertheless matches what we're discussing here.)

                                      I want to pause here to point out that multiplication grows more quickly than addition. Look at the first few terms of F₁:
                                        * F₁(3,1)=3
                                        * F₁(3,2)=3+3=6
                                        * F₁(3,3)=3+3+3=9
                                      Then compare to the first few terms of F₂:
                                        * F₂(3,1)=3
                                        * F₂(3,2)=3*3=9
                                        * F₂(3,3)=3*3*3=27
                                      What's important here isn't that 27>9. What's important is that the latter function is growing more quickly than the previous one.
                                      We can keep going to F₃, which uses the exponentiation operation. This is as high as most high school math classes go. F₃=3^3^3=19683. The first few terms of F₃ are:
                                        * F₃(3,1)=3
                                        * F₃(3,2)=3^3=27
                                        * F₃(3,3)=3^3^3=19683
                                      You can see that each subsequent function is growing more and more quickly, such that the only the third term, Fₓ(3,3), is fast approaching really big numbers.

                                      Next in the series is F₄, which uses tetration. F₄=3⇈3⇈3=7,625,597,484,987. Here I am using Knuth arrow notation for the operator symbol, but the idea is the same as all the previous operations. Addition is repeated counting. Multiplication is repeated addition. Exponentiation is repeated multiplication. Tetration is repeated exponentiation. In other words:
                                        * Multiplication is repeated addition:
                                          X*Y = X+X+…+X, where there are Y instances of X in this series.
                                          In the case of F₂(3,2), 3*3=3+3+3.
                                        * Exponentiation is repeated multiplication:
                                          X^Y = X*X*…*X, where there are Y Xs.
                                          3^3=3*3*3
                                        * Tetration is repeated exponentiation:
                                          X⇈Y = X^X^…^X, where there are Y Xs.
                                          3⇈3=3^3^3
                                      Pentation is next: F₅=3↑↑↑3↑↑↑3. It takes a bit of work to figure out this value in simpler terms.
                                        * F₅=3↑↑↑3↑↑↑3
                                          =3↑↑↑(3↑↑↑3)
                                          =3↑↑↑(3⇈3⇈3)
                                          =3↑↑↑(3⇈(3⇈3))
                                          =3↑↑↑(3⇈(7,625,597,484,987))
                                        Remember that tetration is repeated exponentiation, so the part in the parentheses there (3⇈7,625,597,484,987) is 3 raised to the 3 raised to the 3 raised to the 3…raised to the 3, where there are 7,625,597,484,987 instances of 3 in this power tower. The image to the right shows what I mean by a power tower: it's a^a^…^a. In our example, it's 3^3^…^3, with 7,625,597,484,987 threes. And this is just the part in the parentheses. You still have to take 3↑↑↑(N), where N is the huge power tower of threes. It's truly difficult to accurately describe just how big this number truly is.


                                      Fastly Fast


                                        So far I've described the first few functions, F₁, F₂, F₃, F₄, and F₅. These are each associated with an operation. I could go on from pentation to hexation, but instead I want to focus on these increasingly fast growing functions. F₅(3,3) is already mindboggingly huge, so it's difficult to get across how huge F₆(3,3) is in comparison. Think about the speed at which we get to huge numbers from F₁ to F₂ to F₃, and then realize that this is nothing compared to where you get when you move to F₄. And again how this is absolutely and completely dwarfed by F₅. This happens yet again at F₆. It's not just much bigger. It's not just bigger than F₅ by the hugeness of F₅. It's not twice as big, or 100 times as big, nor even F₅ times as big. (After all, the word "times" denotes puny multiplication.) It's not F₅^F₅ even. Nor F₅⇈F₅. Nor even F₅↑↑↑F₅. No, F₆=3⇈⇈3⇈⇈3=3⇈⇈(F₅(3,3)). I literally cannot stress how freakishly massive this number is. And yet: it is just F₆.

                                        This is why I wanted to focus on fast growing functions. Each subsequent function is MUCH bigger than the last, in such a way that the previous number basically approximates to zero. So imagine the size of the numbers as we move along to faster and faster growing functions.

                                        These functions grow fast because they use recursion. Each subsequent function is doing what the last function did, but does it repeatedly. In our case, Fₓ(3,3) is just taking the previous value and using the next highest operator on it. F₂(3,3)=3*F₁(3,3). F₃(3,3)=3^F₂(3,3). F₄(3,3)=3⇈F₃(3,3). F₅(3,3)=3↑↑↑F₄(3,3). And as we saw two paragraphs ago, F₆(3,3)=3⇈⇈F₅(3,3).

                                        I chose this recursive series of functions because I wanted to match up with the examples I used in my previous discussion of really big numbers. But most mathematicians use the fast growing hierarchy to describe this kind of thing. Think of it as a yardstick against which we can compare other fast growing functions.


                                      Fast Growing Hierarchy


                                        We start with F₀(n)=n+1. This is a new function, unrelated to the multiple input function we've used earlier in this blog post. F₀(n) is the first rung of the fast growing hierarchy. If you want to consider a specific number associated with each rung of the hierarchy, we might choose n=3. So F₀(3)=3+1=4.

                                        We then use recursion to define each subsequent function in the hierarchy. Fₓ₊₁(n)=Fₓ(Fₓ(…Fₓ(n)…)), where there are n instances of Fₓ.

                                        So F₁(n)=F₀(F₀(…F₀(n)…)), with n F₀s. This is equivalent to n+1+1+…+1, where there are n 1s. This means F₁(n)=n+n=2n. In our example, F₁(3)=6.

                                        Next is F₂(n)=F₁(F₁(…F₁(n)…)), with n F₁s. This is just 2*2*…*2*n, with n 2s. So F₂(n)=n2^n. In our example, F₂(3)=3*(2^3)=24.

                                        At each step in the hierarchy, we roughly increase to the next level of operation each time. F₀ is basically addition; F₁ is multiplication; F₂ is exponentiation. It's not exact, but it's in the same ballpark. This corresponds closely to the function I defined earlier in this blog post. Mathematicians use the fast growing hierarchy to give an estimate of how big other functions are. My F₂(3,3) from earlier is roughly F₂(n) in the FGH. (F₂(3,3)=27, while F₂(3)=24.) (Egads, do I regret using F for both functions, even though it should be clear since one has multiple inputs.)


                                      Diagonalization


                                        So at this point you probably get the gist of the fast growing hierarchy for F₂, F₃, F₆, etc. Even though they are mind-boggingly large numbers, you may be able to grasp what we mean we talk about F₉, or F₉₉. These functions grow faster and faster as you go along the series of functions, and there's an infinite number of functions in the list. We can talk about Fₓ with the subscript x being a googol, or 3↑↑↑3↑↑↑3. These functions grow fast. But we can do even better.

                                        Let's define F𝜔(n) as Fn(n). (Forgive the lack of subscripts here; we're about to get complex on what's down there.) Now our input n is going to be used not just as the input in the function, but also as the FGH rank of a function that we already defined above. So, in our example, F𝜔(3)=F₃(3)=F₂(F₂(F₂(3)))=F₂(F₂(24))=F₂(24(2^24))=F₂(24(16777216))=F₂(402653184)= 402653184*(2^402653184)≈10^120000000.

                                        As you can see, F𝜔(n) grows incredibly quickly. More quickly, in fact, than any integer value of Fₓ(n). This means that the sequence of functions I've been talking about previously in this blog post can't even get close to the fast growing F𝜔(n), even though there are infinite integer values you could plug in for Fₓ. An example of a famous function that grows at this level would be the Ackermann function.

                                        But we can keep going. Consider F𝜔₊₁(n), which is defined exactly as we defined the FGH earlier. F𝜔₊₁(n)=F𝜔(F𝜔(…F𝜔(n)…)), where there are n F𝜔s. This grows faster than F𝜔(n) in a way that is exceedingly difficult to describe. Remember that each function in this sequence grows so much faster than the previous function so as to make it approximate zero for a given input. An example of a famous function that grows at this level would be Graham's function, of which Graham's number is oft cited as a particularly large number. In particular, F𝜔₊₁(64)>G₆₄.

                                        There's no reason to stop now. We can do F𝜔₊₂(n) or F𝜔₊₆(n) or, in general, F𝜔₊ₐ(n), where a can be any natural number, as high as you might please. You can use a=googol or a=3↑↑↑3↑↑↑3 or even a=F𝜔(3↑↑↑3↑↑↑3). But none of these would be as large as if we introduced a new definition: F𝜔*₂(n)=F𝜔₊n(n). This is defined in exactly the same way that we originally defined F𝜔(n), where the input not only goes into the function, but also into the FGH rank of the function itself. F𝜔*₂(n) grows even faster than any F𝜔₊ₐ(n), regardless of what value you enter in as a.

                                        I'm sure you see by now where this is going. We have F𝜔*₂₊₁(n) next, and so on and so forth, until we get F𝜔*₂₊ₐ(n), with an arbitrarily large a. Then we diagonalize again to get F𝜔*₃(n), and then the family of F𝜔*₃₊ₐ(n). This can on indefinitely, until we get to F𝜔*ₑ₊ₐ(n), where e can be arbitrarily large. A further diagonalization can then be used to create F𝜔*𝜔(n)=F𝜔²(n), which grows faster than F𝜔*ₑ₊ₐ(n) for any combination of e and a.

                                        Yet F𝜔²(n) isn't a stopping point for us. Beyond F𝜔²₊₁(n) lies F𝜔²₊ₐ(n), beyond which is F𝜔²₊𝜔(n), beyond which is the F𝜔²₊𝜔₊ₐ(n) family, and so on, and so forth, past 𝜔²₊𝜔*₂(n), beyond 𝜔²₊𝜔*ₑ₊ₐ(n), all the way to F𝜔 ³ (n). At each step, the functions grow so fast that they completely and utterly dwarf the function before it, and yet we've counted up several times to infinity in this sequence, an infinite number of times, and then did this three times in order to get to F𝜔 ³ (n). These functions grow fast.

                                        Still, there's more to consider. F𝜔 ³ (n) is followed by F𝜔 ⁴ (n), all the way up to F𝜔 ⁿ (n), beyond which lies yet another digonalization to get to F𝜔 ^ 𝜔(n). From here, you can just redo all the above: F𝜔 ^ 𝜔₊ₐ(n) to F𝜔 ^ 𝜔₊𝜔₊ₐ(n) to F𝜔 ^ 𝜔₊₂𝜔₊ₐ(n) to F𝜔 ^ 𝜔₊ₑ𝜔₊ₐ(n) until we have to rediagonalize to F𝜔⇈𝜔(n), which we set equal to Fₑ₀(n) just for the purpose of making it easier to read. There are two famous examples of functions that grow at this level of the FGH: the function G(n) = "the length of the Goodstein sequence starting from n" and the function H(n) = "the maximum length of any Kirby-Paris hydra game starting from a hydra with n heads" are both at the FGH rank of Fₑ₀(n).

                                        You can keep going, obviously. Tetration isn't the end for 𝜔. We can do Fₑ₀₊₁(n), then the whole family of Fₑ₀₊ₐ(n), followed by Fₑ₁(n). And we can keep going, to Fₑ₂(n) and beyond, increasing the exponent arbitrarily large, followed by Fₑ𝜔(n). And this ride just doesn't stop, because you go through the whole infinite sequence of infinite sequences of infinite sequences of infinite sequences of infinite sequences yet again, increasing the subscript of e to the absurd point of ε₀. And then we can repeat that, and repeat again, and again, infinitely many times, creating a subscript tower where ε has a subscript of ε to the subscript of ε to the subscript of ε to the suscript of… -- infinitely many times. At this point the notation gets too unwieldy yet again, so we move on to using another greek letter: 𝛇, where it starts all over again. And we can do this infinite recursion infinitely yet again, until we have a subscript tower of 𝛇s, after which we can call the next function in the series η.

                                        Each Greek letter represents an absolutely humongous jump, from 𝜔 to ε to 𝛇 to η. But as you can see it gets increasingly complicated to talk about these FGH functions. Enter the Veblen Hierarchy.


                                        Veblen Hierarchy


                                        The Veblen Hierarchy starts with 𝜙₀(a)=𝜔a, then increases with each subscript to a new greek letter from before. So:

                                          * 𝜙₀(a)=𝜔a
                                          * 𝜙₁(a)= εa
                                          * 𝜙₂(a)= 𝛇a
                                          * 𝜙₃(a)= ηa
                                          This FGH grows much faster than the previous one, because it skips over all the infinite recursions to the final tetration of each greek letter, which it defines as the next greek letter in the series. The Veblen Hierarchy grows fast.

                                          The subscript can get bigger and bigger, reaching 𝜙ₑ(a), where e is arbitrarily large. You can follow this by making 𝜔 the next subscript in the series, then follow the same recursive expansion as before until you get to 𝜔⇈𝜔, which we'd define as ε. And go through the greek letters, one by one, until you've gone through an infinite number of them, after which we can use 𝜙 as the subscript for 𝜙. Then do this again and again, nesting additional 𝜙 as the subscript for each 𝜙, until you have an infinite subscript tower of 𝜙, after which you have to substitute a new notation: Γ₀.

                                          Here we finally reach a new limit. Γ₀ is as far as you can go by using recursion and diagonalization. It's the point at which we've recursed as much as we can recurse, and diagonalized as much as we can diagonalize.

                                          But we can go further.

                                          We can already see Γ₀ as 𝜙(a,0)=a. Let's extend Veblen function notation by defining 𝜙(1,0,0)=γ₀. Adding this extra variable let's us go beyond all the recursion and diagonalization we could do previously. Now we have all of that, and can just add 1.

                                          Let's explore this sequence:
                                            * γ₀=𝜙(1,0,0) Start here.
                                            * γ₁=𝜙(1,0,1) Increment the last digit repeatedly.
                                            * γ𝜔=𝜙(1,0,𝜔) Eventually you reach 𝜔.
                                            After this, the next ordinal is 𝜙(1,1,0). As you can see, we have a new variable to work with. We can keep incrementing the right digit until we get to 𝜔 again, after which we reach 𝜙(1,2,0). And we can do this again and again, until we reach 𝜙(1,𝜔,0). Then the next ordinal would be 𝜙(2,0,0). And we can keep going, more and more until we get to 𝜙(𝜔,𝜔,𝜔). At this point, we're stuck again.

                                        That is, until we add an additional variable.

                                        So now we have 𝜙(1,0,0,0) as the next ordinal. And we can max this out again until we need to add yet another variable, and then yet another variable, and so on, until we have infinite variables. This is called the Small Veblen Ordinal.

                                        ψ ( Ω Ω ω ) = φ ( 1 , 0 , ⋯ , 0 ⏟ ω )

                                        Among FGH functions, the Small Veblen Ordinal ranks in just the lower attic of Cantor's Attic. It's not even the fastest growing function on the page it's listed on. We're nowhere near the top, despite all this work. Of course, there isn't a top -- not really. But what I mean is that we're nowhere near the top of what mathematicians talk about when they work with really large ordinals.


                                      …and Beyond!


                                        You might notice that at no point did I mention TREE(3), which was one of the numbers I brought up in my last blog post. That's because the TREE() function is way beyond what I've written here. You have to keep climbing, adding new ways of getting to faster and faster growing functions before you reach anything like TREE(3). And beyond that to the point of absurdity is SSCG(3). And these are all still vastly beneath the Church Kleene Ordinal, which (despite being countable) is uncomputable. This is where you finally run into the Busy Beaver function. The distances between each of these functions that I've mentioned in this paragraph are absurdly long. It took this long to explain up to the Small Veblen Ordinal, and yet it would take equally long to get up to the TREE() function. And then just as long to get to SSCG(). And just as long to Busy Beaver.

                                        I want to be clear: I'm not saying they are equal distances from each other. I'm saying that it would take an equal amount of time to explain them. At each step of my explanation, I've gotten to absurdly faster and faster growing functions, leaping from concept to concept more quickly than I had any right to. And I would explain that much faster if I kept going, using shorthand to handwave away huge jumps in logic. And yet it would still take that long to explain up to these points.

                                        And I still wouldn't even be out of the lower attic, with the Church Kleene Ordinal.

                                        If you want to keep going, you may be interested in this readable medium post by Josh Kerr, the absolutely beautifully written Who Can Name the Bigger Number? by Scott Aaronson, or the wiki at Cantor's Attic. Parts of this post were inspired by my own previous post on large numbers and a reddit post by PersonUsingAComputer. I'd also like to thank professor Edgar Bering and grad students Bo Waggoner and Charlie Cunningham for helping to correct errors in this essay.
                                        Posted by Eric Herboso at Monday, December 10, 2018
                                        Labels: mathematics , philosophy , science

                                    No comments:

                                      Post a Comment

                            Newer Post Older Post Home
                              Subscribe to: Post Comments (Atom)

                          About Eric

                            Eric Herboso I'm the Executive Director at Effective Giving Quest, where we help gaming companies, streamers, and professionals help others the most through their donations. At heart, I’m a philosophy nerd intent on doing the most good. I'm veg*n, rationalist, skeptic, polyamorous, & asexual. This is a personal blog, where I write about random stuff I’m into: board games, hard sci-fi/ratfic, Nintendo, effective altruism, metaethics, & my personal life. I’m writing mostly for myself, not a general audience. YMMV. View my complete profile

                          Search This Blog

                                
                              

                          Featured Posts

                            Dividing Lines

                            The dividing lines are there, between each instantiation of "I", even if I can never quite get a glimpse of them. If I squint just so, fast-forwarding through the events of a past self, I don't quite reach a boundary so much as reach a gap. After which another "I" instantiates itself. The dividing line is there; I'm sure of it. But it only seems blurrily visible when I don't focus on it. As soon as my eye approaches, it disapparates into the ether.

                            The Double-Crux Game

                            One of the greatest joys I've personally experienced is that feeling you get when you genuinely change your mind. It's especially rewarding when you can feel the dominoes falling as each step in a logical sequence causes you to change your mind on increasingly complex lemmas after a basic premise's truth value switches.

                            Why Many Worlds is Correct

                            I recently read a four year old article by Eliezer Yudkowsky on why Many Worlds survives Occam's razor. The argument was persuasive enough to cause me to change my mind on a stance I've held for nearly two decades.

                            My Favorite Podcasts

                            I subscribe to a lot of podcasts. I use podcasts to keep up with the news, learn more about the world, and expand my mind generally. As such, I've sampled and stopped listening to more podcasts than most people have even heard of.

                          Blog Archive

                                  * ► 2024 (4)
                                      + ► August (1)
                                      + ► February (2)
                                      + ► January (1)
                                  * ► 2023 (5)
                                      + ► December (1)
                                      + ► September (1)
                                      + ► May (1)
                                      + ► March (1)
                                      + ► January (1)
                                  * ► 2022 (19)
                                      + ► December (2)
                                      + ► November (1)
                                      + ► October (1)
                                      + ► September (1)
                                      + ► August (2)
                                      + ► July (1)
                                      + ► May (1)
                                      + ► March (4)
                                      + ► February (3)
                                      + ► January (3)
                                  * ► 2021 (24)
                                      + ► December (5)
                                      + ► November (2)
                                      + ► September (1)
                                      + ► August (2)
                                      + ► July (2)
                                      + ► June (1)
                                      + ► April (3)
                                      + ► March (4)
                                      + ► February (1)
                                      + ► January (3)
                                  * ► 2020 (27)
                                      + ► December (4)
                                      + ► November (2)
                                      + ► October (2)
                                      + ► September (5)
                                      + ► June (6)
                                      + ► May (1)
                                      + ► April (1)
                                      + ► March (2)
                                      + ► February (2)
                                      + ► January (2)
                                  * ► 2019 (24)
                                      + ► December (1)
                                      + ► November (3)
                                      + ► October (3)
                                      + ► August (2)
                                      + ► July (6)
                                      + ► June (1)
                                      + ► May (1)
                                      + ► April (4)
                                      + ► March (1)
                                      + ► February (2)
                                  * ▼ 2018 (11)
                                      + ▼ December (2)
                                          o Fastly Fast Growing Functions
                                          o Slow Growing Functions
                                      + ► November (1)
                                      + ► October (2)
                                      + ► September (2)
                                      + ► June (1)
                                      + ► March (2)
                                      + ► February (1)
                                  * ► 2017 (13)
                                      + ► November (2)
                                      + ► October (2)
                                      + ► July (1)
                                      + ► May (4)
                                      + ► March (1)
                                      + ► February (2)
                                      + ► January (1)
                                  * ► 2016 (10)
                                      + ► November (1)
                                      + ► October (1)
                                      + ► March (2)
                                      + ► February (1)
                                      + ► January (5)
                                  * ► 2015 (7)
                                      + ► December (2)
                                      + ► October (1)
                                      + ► September (1)
                                      + ► August (1)
                                      + ► March (1)
                                      + ► January (1)
                                  * ► 2014 (10)
                                      + ► August (1)
                                      + ► June (3)
                                      + ► May (2)
                                      + ► April (2)
                                      + ► March (1)
                                      + ► February (1)
                                  * ► 2013 (6)
                                      + ► October (1)
                                      + ► August (1)
                                      + ► July (1)
                                      + ► June (1)
                                      + ► March (1)
                                      + ► January (1)
                                  * ► 2012 (79)
                                      + ► December (2)
                                      + ► November (6)
                                      + ► October (10)
                                      + ► September (13)
                                      + ► August (16)
                                      + ► July (13)
                                      + ► June (3)
                                      + ► May (3)
                                      + ► April (8)
                                      + ► March (4)
                                      + ► January (1)
                                  * ► 2010 (5)
                                      + ► November (1)
                                      + ► March (2)
                                      + ► February (2)
                                  * ► 2009 (14)
                                      + ► December (3)
                                      + ► November (2)
                                      + ► October (5)
                                      + ► September (3)
                                      + ► July (1)
                                  * ► 2008 (23)
                                      + ► December (2)
                                      + ► November (1)
                                      + ► October (1)
                                      + ► September (3)
                                      + ► August (4)
                                      + ► June (1)
                                      + ► May (1)
                                      + ► April (3)
                                      + ► February (6)
                                      + ► January (1)
                                  * ► 2007 (27)
                                      + ► December (2)
                                      + ► November (8)
                                      + ► October (10)
                                      + ► September (4)
                                      + ► August (2)
                                      + ► July (1)
                                  * ► 2006 (2)
                                      + ► May (1)
                                      + ► April (1)
                                  * ► 2005 (18)
                                      + ► December (3)
                                      + ► November (1)
                                      + ► October (1)
                                      + ► September (4)
                                      + ► August (1)
                                      + ► July (5)
                                      + ► June (3)
                                  * ► 2004 (16)
                                      + ► October (2)
                                      + ► September (1)
                                      + ► May (4)
                                      + ► April (3)
                                      + ► March (4)
                                      + ► February (1)
                                      + ► January (1)
                                  * ► 2003 (11)
                                      + ► November (1)
                                      + ► October (1)
                                      + ► September (4)
                                      + ► July (1)
                                      + ► June (1)
                                      + ► April (1)
                                      + ► February (1)
                                      + ► January (1)
                                  * ► 2002 (68)
                                      + ► December (11)
                                      + ► November (25)
                                      + ► October (29)
                                      + ► September (1)
                                      + ► June (1)
                                      + ► March (1)
                                  * ► 2001 (3)
                                      + ► September (1)
                                      + ► June (1)
                                      + ► May (1)
                                  * ► 2000 (3)
                                      + ► September (1)
                                      + ► July (2)
                                  * ► 1999 (3)
                                      + ► September (1)
                                      + ► January (2)
                                  * ► 1998 (6)
                                      + ► December (2)
                                      + ► July (1)
                                      + ► May (1)
                                      + ► April (1)
                                      + ► March (1)
                                  * ► 1997 (2)
                                      + ► April (2)
                                  * ► 1996 (3)
                                      + ► December (1)
                                      + ► July (1)
                                      + ► June (1)
                                  * ► 1995 (3)
                                      + ► July (3)
                                  * ► 1994 (2)
                                      + ► June (1)
                                      + ► March (1)
                                  * ► 1984 (1)
                                      + ► July (1)

                          Tagged Posts

                            animal charity evaluators art book review effective altruism family fiction gaming haes life marketing mathematics meta music nonprofit philosophy poetry politics polyamory published-elsewhere REI science skepticism social media vegetarianism Wii Need to Talk

                          @EricHerboso

                            Tweets by @EricHerboso

                          Pinterest

                            Follow Eric's board Philosophy Humor on Pinterest.
                        
                      
                              Eric Herboso

                          Goodreads



                          Eric's Social Links

                              * Effective Altruism Hub
                              * Effective Altruism Forum
                              * Facebook
                              * Twitter
                              * LinkedIn
                              * Wikipedia
                              * Reddit
                              * Twitch
                              * Tagmap
                              * Meetup
                              * DekuDeals Switch Games
                              * Ancestry
                              * EricHerboso@gmail.com

                            Subscribe To

                                    Posts
                                    Comments
                    
                  
                        Creative Commons Attribution. Simple theme. Powered by Blogger.
Fastly Fast Growing Functions
https://www.ericherboso.org/2018/12/fastly-fast-growing-functions.html