The Biggest Number in the World, page 14
The smallest kind of infinity, as we saw in the last chapter, is aleph-null, the size of the set of all natural numbers. The mathematics of it, we discovered, is both alien and counterintuitive. Add or take away any finite number from aleph-null and the result is still aleph-null. For example, א0 + 1 = א0 and א0 – 300 = א0. Multiplication and division by finite numbers, similarly, has no effect: א0 times a million is still א0. You can even add aleph-null to itself and the result stubbornly remains aleph-null.
Aleph-null is a transfinite cardinal. Cardinals measure how many members a set contains. In the case of aleph-null, the set in question is that of natural numbers: {0, 1, 2, 3, …}. Although this has a fixed number of members, these members can be rearranged so that the set has different ordinalities, or ‘lengths’. The shortest length of the set of all natural numbers is the smallest transfinite ordinal: omega (ω). The next shortest is ω + 1, then ω + 2, then ω + 3, and on and on. A key feature of all these different transfinite ordinals, which correspond to different ways of ordering the set of all natural numbers, is that they’re countable. This doesn’t mean that you could actually count them all but rather that there’s a one-to-one correspondence between the ordinal and the natural numbers.
Now, before we move on and see how all this applies to our fast-growing hierarchy, we need to know about a few other concepts to do with ordinal numbers. The first of these are the concepts of ‘successor ordinal’ and ‘limit ordinal’. A successor ordinal is exactly what its name suggests: any ordinal that immediately succeeds, or comes after, some other ordinal. The easiest way to think of this is that every successor ordinal is one greater than the ordinal that precedes it. All natural numbers that are greater than zero are successor ordinals. A limit ordinal is a nonzero limit of a sequence of ordinals, all of which are less than it, without itself being a successor. So, every ordinal must be one of the following: zero, a successor ordinal, or a limit ordinal.
You can’t reach a limit ordinal by adding 1, or any other finite number, to any ordinal that is less than it. Following this definition, the smallest limit ordinal is ω. The next smallest ordinal after ω is ω + 1, but this is a successor ordinal. Infinitely many more successor ordinals follow until we reach the next limit ordinal: ω + ω. This is a limit ordinal for the same reason that ω is: namely, it isn’t the result of adding 1, or some other finite number, to any number that it exceeds in size. Corresponding to each limit ordinal is what’s called a fundamental sequence – a sequence of ordinals that approach the limit ordinal (but never reach it) from below. In the case of ω, the fundamental sequence is just the sequence of natural numbers: 0, 1, 2, 3, … Any ordinal built using ω has a fundamental sequence based on this. So, for instance, the fundamental sequence of the limit ordinal ω*2, = ω + ω, is ω, ω + 1, ω + 2, ω + 3, …, while ω2 has the fundamental sequence ω, ω*2, ω*3, and so on. In general, the last ω can be replaced by its fundamental sequence (expanding multiplication and exponents as appropriate), so, for example, ω2 is rewritten as ω*ω.
At last, we’re ready to appreciate the true power of the fast-growing hierarchy, by bringing transfinite ordinals into play. We’ll see how the use of these ordinals to index the functions serves as a springboard for reaching some of the largest computable finite numbers ever conceived. We started off with f0 (n), f1 (n), f2 (n), and so on, gradually working our way up the hierarchy, using natural numbers as indices. Now we’re going to jump to fω (n), the function indexed by the smallest transfinite ordinal, ω. But there’s a problem we have to overcome in doing this. When we were figuring out the value of functions indexed by natural numbers, the first step was to reduce the index by one and write down a recursion relation. For example, f3 (n) = f2 (f2 (… f2 (n))). But we can’t use this approach when the index is ω because ω is a limit ordinal and therefore isn’t the successor of any ordinal.
Instead, what we do is replace ω with the nth member of its fundamental sequence – namely, n itself – so we find that fω (n) is just fn (n). Now, to be clear, we’re not saying that ω = n, despite how it may appear. What we’re doing is expressing fω (n) in terms of (finite) ordinals smaller than ω, so that we can reduce the function to a form that’s useful for doing calculations. Perhaps you’re thinking we may as well write fn (n) instead of fω (n) and get the same result, but that would prevent the next crucial step – the step at which the full potential of a fast-growing hierarchy becomes apparent.
As soon as we go from fω (n) to fω+1 (n) something dramatic happens. Remember, when the ordinal that indexes the function goes up by 1 this feeds the previous function back into itself n times. If using a finite ordinal results in a fixed number of up-arrows, and using ω produces n – 1 up-arrows, then using ω + 1 allows us to feed back into the number of up-arrows n times, which amounts to a fantastic jump in the strength of the recursion.
To understand this, think about the function fω+1 (2), which equals fω (fω (2)) using our recursion rule. Because we defined fω (2) to be the same as f2 (2), we can rewrite fω+1 (2) as fω (f2 (2)), just replacing the innermost ω with 2. (We can’t work out the value of the outer fω until we know what value the inner one will take.) As it turns out, f2 (2) = 8 so now we’re left with fω+1 (2), which equals fω (8). Finally, we can simplify the outermost ω and get f8 (8), which is a number with seven up-arrows. While this shows how fω+1 can be used to feed back into the number of up-arrows, it doesn’t give a clear impression of the function’s awesome capability. This only becomes apparent as n gets larger, and the corresponding number of feedback loops grows. Putting n = 64 gives fω+1 (64), which is approximately Graham’s number. The next step up the fast-growing hierarchy, fω+2 (n), bursts into totally new territory because it plugs all of the mathematical machinery used to reach the level of Graham’s number back into itself. The result is a number we can write roughly as gg…64 – with 64 levels of the g subscript! There’s no hope of trying to grasp, even vaguely, what this means but it obviously represents a game-changing explosion in size.
With each step up the hierarchy – fω+3 (n), fω+4 (n), …, – there’s a further, extraordinarily steep rise in the number of recursive operations acting on what is already, from the previous step, a spectacularly large number. The countably infinite ordinals stretch away into the far distance, each successive one providing the basis for a recursive function that utterly dwarfs the power of the one before it. The omegas alone form a sequence so long that it only ends when we reach omega raised to a power tower of omega omegas. This mighty ordinal, known as epsilon-zero, is so vast that it can’t be described within our conventional system of arithmetic, known as Peano arithmetic. With each step along the eternal road of omegas, the finite number generated by recursion jumps by an amount that defies comprehension. But beyond the loftiest omegan power tower, lie tier upon higher tier of yet greater infinite ordinals – first the epsilons, then the zetas, and on and on, without end – as we saw in the last chapter in our exploration of infinity. These increasingly vast ordinals serve to define more and more powerful degrees of feedback.
Finally, we reach a tremendously large ordinal known as Gamma-zero (Γ0) or, more magnificently, the Feferman–Schütte ordinal, after the American philosopher and logician Solomon Feferman and the German mathematician Kurt Schütte who first defined it. Although Gamma-zero is still countable, and there are countable ordinals beyond it, actually defining it requires the use of uncountable ordinals (ones that can’t be made from rearranging elements of aleph-null but instead require aleph-one or more elements). This process is reminiscent of how the fast-growing hierarchy itself evolves. Just as we have to resort to using infinite ordinals in the fast-growing hierarchy to describe huge finite numbers, so we need to turn to uncountable ordinals to describe truly tremendous countably infinite ordinals. There aren’t any adjectives left to describe adequately the size of the finite numbers to which the Feferman–Schütte ordinal, and others beyond it, give rise by recursion. Nor does any mathematician have a brain big enough or clever enough to truly grasp the immensity of the numbers their recursive techniques can spawn. Nevertheless, these numbers exist, they’re finite in size (and therefore lie on the familiar number line that we learn about as young children), and they could, in principle, be reached by counting up, one by one, from zero.
In our quest to find the biggest number in the world we’ve alternated between looking at specific examples of large numbers and ways of generating and defining them. Among the former, for instance, are the googol, the moser, and Graham’s number. The latter include the hyperoperator sequence, Conway’s chain arrows, and now this astoundingly powerful method of using a sequence of functions indexed by an endlessly increasing succession of transfinite ordinals.
We’ve been talking about a fast-growing hierarchy rather than the fast-growing hierarchy for a good reason – there are different varieties. These varieties may differ both in the choice of initial function f0 and in the choice of fundamental sequences at the limit ordinals. The one thing that all fast-growing hierarchies have in common is that they’re sequences of rapidly increasing functions indexed by ordinals.
One of the first examples of the use of this concept was provided by G. H. Hardy in 1904. The Hardy hierarchy starts off in a very pedestrian way: H0(n) = n, H1(n) = n + 1, H2(n) = n + 2, and so on, following the same pattern for all finite ordinals. Even when it gets to transfinite indices, its pace isn’t exactly blistering: Hω(n) = 2n, Hω+1(n) = 2n + 2, Hω+2(n) = 2(n + 2), …, Hω2 = 4n, …, Hω3 = 8n. Only by the time it reaches Hω^3 does it arrive at the level of tetration. But the Hardy hierarchy is historically important because it was the first time transfinite ordinals had been used to index a recursive function and so is the ancestor of much more rapidly growing families of functions such as the fast-growing hierarchy we described above. In fact, the two hierarchies are closely related. For any ordinal α, fα is the same as Hω^α, so that, for instance, Hω^(ω+1)(64) is comparable to Graham’s number. The Hardy hierarchy eventually catches up with our fast-growing hierarchy – but not until its index reaches ε0.
Googologists, whose pastime is the quest to define ever-larger numbers, prize fast-growing hierarchies because they’re also used, and were first developed more than a century ago, in professional mathematics. Having been tried and tested in academia for many decades, they provide a solid foundation upon which enthusiasts can build more speculative ideas. In mainstream maths, fast-growing hierarchies are known, of course, to generate big numbers very quickly. But their main purpose is to serve as a benchmark for measuring the growth rate of other functions. Googologists, too, use them in this way, as a well-established and respected tool for gauging the strength of different types of functions that also mushroom with incredible speed. Notable among these explosively growing rivals is something called the TREE function.
As the name suggests, a tree in mathematics can have the appearance of a tree that grows in the ground or a family tree, with branches spreading out from a common trunk. Mathematical trees are a special variety of what in maths are known as graphs. Usually we think of graphs as being charts drawn on graph paper, in which one value is plotted against another. But the types of graphs we’re talking about in connection with trees are different: they’re ways of representing data in which dots, called nodes, are connected by line segments, called edges. If it’s possible to start at a node, move to other nodes along edges, and then return to the starting node without repeating any edges or nodes, then the route taken is known as a cycle and the graph is said to be cyclic. If it’s possible to start at any node and travel to another node, without repeating an edge or node along the way, then the route taken is called a path and the graph is said to be connected. A tree is defined as a graph that is connected but has no cycles. Both family trees and biological trees also have this kind of structure. If a unique number or colour is assigned to each node, then the tree is said to be labelled. Furthermore, if we assign one node to be the root, then we have a rooted tree. One useful property of rooted trees is that for any node, we can always trace back a path to the root.
Some mathematical trees that have the same kind of branching structure as a real tree can be fitted inside others of their kind. They’re said to be homeomorphically embeddable, which is a fancy way of saying they’re similar in form or appearance and one of them is like a smaller version of the other. Of course, mathematicians are a bit more precise about the definition. They start with a larger tree and see how much of it can be pruned using a couple of different methods. First, if there’s a node (except for the root node) that has just two edges, either leading into or away from it, that node can be removed and the two edges joined into one. Second, if two nodes are joined by a single edge, the edge can be collapsed and the two nodes compressed into one. The colour of this new node is the colour of whichever node was originally closer to the root. If a smaller tree can be made by applying these two steps in any order to the larger tree, the smaller one is said to be homeomorphically embeddable in the larger. In 1960, the American mathematician and statistician Joseph Kruskal proved an important theorem to do with this kind of tree. Suppose there’s a sequence of them so that the first tree can have only one node, the second up to two nodes, the third up to three, and so on, and that no tree is homeomorphically embeddable in any subsequent tree. What Kruskal found is that such a sequence always has to end at some point. The question is: how long can the sequence be? In response, American mathematician and logician Harvey Friedman, listed in The Guinness Book of Records in 1967 as the world’s youngest professor (an assistant professor at Stanford aged just eighteen), defined the tree function, TREE(n). Friedman then investigated the output of the function for different values of n. The first tree consists of a single node of a certain colour, which can’t be used again. If n = 1, this is the only colour and the sequence immediately stops, so that TREE(1) = 1. If n = 2, there’s one more colour. The second tree can contain up to two nodes, so it contains two nodes both of this colour. The third tree also must contain only this colour, but can only have one node, as otherwise the second tree would be homeomorphically embeddable in the third. Beyond that, no more trees are possible so TREE(2) = 3. The big shock, as Friedman found, comes when we reach TREE(3). In a sudden explosion of complexity and proliferation the number of nodes far surpasses Graham’s number and reaches the small Veblen ordinal, that extraordinarily un-small number we encountered in our travels among the various infinities, in the fast-growing hierarchy.
Humongous though TREE(3) is, it’s definitely finite – as are all the numbers generated by the TREE function for any specific n. Kruskal himself showed that any TREE(n) will ultimately result in a tree that contains a previous tree, so that for every n, TREE(n) will output a finite result. Proving this for any particular TREE, however, is neither easy nor quick. Friedman found a way to calculate how many symbols, such as plus or minus signs, exponents, or other mathematical symbols, it would take to prove that TREE(3) was finite. His answer: 2 ↑↑ 1,000, or a power tower of 2s stacked a thousand high.
The rate at which TREE(n) grows is tremendous, bounded below by the fast-growing hierarchy of the small Veblen ordinal. Even the TREE function, however, is totally outstripped in its growth rate by other functions that arise from graph theory. Friedman, who defined TREE, has also devised what are known as the subcubic graphic (SCG) and the simple subcubic graph (SSCG) functions. Like TREE, these start off modestly enough but then suddenly and sensationally inflate. For example, SSCG(0) = 2 and SSCG(1) = 6. Then there’s a rapid growth to SSCG(2), which is approximately 103.5775×10^28 (and ends with the digits 11352349133049430008). Thereafter, all contact with numbers for which there’s any conventional form of notation is lost. The exact value of SSCG(3) is unknown but it’s been shown to be very much greater than TREE(3) or, for that matter, TREETREE(3)(3).
Despite the fact that TREE, SSCG, and super-fast-growing functions like them produce astonishingly large numbers very quickly, they are nevertheless computable. In other words, it’s possible to write down a finite, step-by-step list of instructions, or algorithm, to calculate their output for any given input. However, there are other functions that can’t be evaluated by a predetermined method, no matter what resources, such as time, memory, or processing speed, are available. They’re said to be uncomputable and among them are functions that eventually outpace and dominate every one of those we’ve looked at so far.
Chapter 11
Does Not Compute!
Beavers are known for their industriousness and for building the largest structures in the animal kingdom. A family of four beavers can put up 1.5 metres of dam wall in a day and end up with a structure that’s typically 5 to 10 metres wide and about 1.8 metres high. The largest beaver dam in the world, discovered in a remote part of northern Alberta, is an incredible 850 metres long and can be seen from space. With such edifices and the hard-working rodents that build them in mind, Hungarian mathematician Tibor Radó named one of the fastest-growing functions ever conceived – the ‘busy beaver’.
To understand what the busy beaver function is all about, and why it’s so impressive, we must delve a bit more into the subject of computability theory. In particular we need to take a closer look at Turing machines and the difference between what’s theoretically computable and what isn’t.
Alan Turing was among a group of mathematicians and logicians, including Alonzo Church, Kurt Gödel, Stephen Kleene, Rózsa Péter (whom we met earlier in connection with a simplified form of the Ackermann function), and Emil Post, who pioneered computability theory in the 1930s. At the heart of computability theory is the study of computable functions – functions that take natural numbers as their input and produce an output that is possible (given sufficient resources) to calculate. In Chapter 8 we talked about the device that Turing invented as a model for computation. A Turing machine, remember, uses an infinitely long tape, divided into squares, which usually start off blank but onto which can be written a 0 or a 1. At a given moment in time, a read-write head is positioned over one of the squares and the machine can perform any of three basic actions: read the symbol on the square under the head; edit the symbol by writing a new symbol or erasing it; or move the tape one square to the left or the right. What it actually does depends on the contents of the present square and the instruction given in the machine’s program.
