You’re probably already blown away by the previous chapters. But the rabbit hole goes even deeper. The functions we will cover in this chapter may look very simple (even if their definitions are esoteric) , but are unbelievably fast-growing.
Goodstein’s theorem states that any Goodstein sequence will eventually terminate by returning to 0. This was only the third example of a theorem that cannot be proven in Peano arithmetic. A Goodstein sequence is formed as follows:
1. Write the base-2 hereditary representation of the starting value (i. e. 19 -> 22^2 + 21 + 1)
2. Replace the 2s with 3s, then decrement by 1
3. Repeat step 2 until the value of the expression
The Goodstein sequence starting at 3 only requires six steps to go back to 0:
21 + 1 = 3
31 = 3
41 – 1 = 3
Since there are no more 4s to change to 5s, we simply decrement until reaching 0:
3 – 1 = 2
2 – 1 = 1
1 – 1 = 0
Goodstein’s function gives the number of terms in the Goodstein sequence starting at the input value. The first few values are 2, 4, 6, but the next number is not 8, but rather f3(3) – 2, or about 6.8950808*10121,210,694. Whoa! Where did that come from?!
Below are the first few terms in the Goodstein sequences.
1: 1, 0
2: 2, 2, 1, 0
3: 3, 3, 3, 2, 1, 0
4: 4, 26, 41, 60, 83, 109, 139, 173, 211, 253, 299, 348, 401, 458, 519, 583, 653, 726, 803, 883, 969, 1058…
5: 5, 27, 255, 467, 775, 1197, 1751, 2454, 3325, 4382, 5643, 7126, 8849, 10830, 13087, 15637, 18499, …
6: 6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775, 1357259, 2011162, 2895965, …
7: 7, 30, 259, 3127, 46657, 823543, 16777215, 37665879, 77777775, 150051213,
8: 8, 80,
The 10,000th term of the 4-sequence is still only 100,192,319, and the millionth term still only has 12 digits, so it seems to have roughly quadratic growth during the increasing phase.
Higher level Goodstein sequences grow much more quickly at first, such as G(19):
19, 7625597484990,
13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073,546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,099,
1,911,012,597,945,477,520,356,404,559,703,964,599,198,081,048,990,094,337,139,512,789,246,520,530,242,615,803,012,059,386,519,739,850,265,586,440,155,794,462,235,359,212,788,673,806,972,288,410,146,915,986,602,087,961,896,757,195,701,839,281,660,338,047,611,225,975,533,626,101,001,482,651,123,413,147,768,252,411,493,094,447,176,965,282,756,285,196,737,514,395,357,542,479,093,219,206,641,883,011,787,169,122,552,421,070,050,709,064,674,382,870,851,449,950,256,586,194,461,543,183,511,379,849,133,691,779,928,127,433,840,431,549,236,855,526,783,596,374,102,105,331,546,031,353,725,325,748,636,909,159,778,690,328,266,459,182,983,815,230,286,936,572,873,691,422,648,131,291,743,762,136,325,730,321,645,282,979,486,862,576,245,362,218,017,673,224,940,567,642,819,360,078,720,713,837,072,355,305,446,356,153,946,401,185,348,493,792,719,514,594,505,508,232,749,221,605,848,912,910,945,189,959,948,686,199,543,147,666,938,013,037,176,163,592,594,479,746,164,220,050,885,079,469,804,487,133,205,133,160,739,134,230,540,198,872,570,038,329,801,246,050,197,013,467,397,175,909,027,389,493,923,817,315,786,996,845,899,794,781,068,042,822,436,093,783,946,335,265,422,815,704,302,832,442,385,515,082,316,490,967,285,712,171,708,123,232,790,481,817,268,327,510,112,746,782,317,410,985,888,683,708,522,000,711,733,492,253,913,322,300,756,147,180,429,007,527,677,793,352,306,200,618,286,012,455,254,243,061,006,894,805,446,584,704,820,650,982,664,319,360,960,388,736,258,510,747,074,340,636,286,976,576,702,699,258,649,953,557,976,318,173,902,550,891,331,223,294,743,930,343,956,161,328,334,072,831,663,498,258,145,226,862,004,307,799,084,688,103,804,187,368,324,800,903,873,596,212,919,633,602,583,120,781,673,673,742,533,322,879,296,907,205,490,595,621,406,888,825,991,244,581,842,379,597,863,476,484,315,673,760,923,625,090,371,511,798,941,424,262,270,220,066,286,486,867,868,710,182,980,872,802,560,693,101,949,280,830,825,044,198,424,796,792,058,908,817,112,327,192,301,455,582,916,746,795,197,430,548,026,404,646,854,002,733,993,860,798,594,465,961,501,752,586,965,811,447,568,510,041,568,687,730,903,712,482,535,343,839,285,397,598,749,458,497,050,038,225,012,489,284,001,826,590,056,251,286,187,629,938,044,407,340,142,347,062,055,785,305,325,034,918,189,589,707,199,305,662,188,512,963,187,501,743,535,960,282,201,038,211,616,048,545,121,039,313,312,256,332,260,766,436,236,688,296,850,208,839,496,142,830,484,739,113,991,669,622,649,948,563,685,234,712,873,294,796,680,884,509,405,893,951,104,650,944,137,909,502,276,545,653,133,018,670,633,521,323,028,460,519,434,381,399,810,561,400,652,595,300,731,790,772,711,065,783,494,174,642,684,720,956,134,647,327,748,584,238,274,899,668,755,052,504,394,218,232,191,357,223,054,066,715,373,374,248,543,645,663,782,045,701,654,593,218,154,053,548,393,614,250,664,498,585,403,307,466,468,541,890,148,134,347,714,650,315,037,954,175,778,622,811,776,585,876,941,680,908,203,127
The next terms are 66⁶ + 1, 77⁷, 88⁸ - 1, but then the next term is equal to 7 * 97*9⁷ + 7*9⁶ + 7*9⁵ + 7*9⁴ + 7*9³ + 7*9² + 7*9 + 7 + 7 * 97*9⁷ + 7*9⁶ + 7*9⁵ + 7*9⁴ + 7*9³ + 7*9² + 7*9 + 6 + 7 * 97*9⁷ + 7*9⁶ + 7*9⁵ + 7*9⁴ + 7*9³ + 7*9² + 7*9 + 5 + … + 7*98 + 7*97 + 7*96 + 7*95 + 7*94 + 7*93 + 7*92 + 7*9 + 7, or more compactly 7*(937665881 – 1/8), or about 5.59359528409385*1035,942,384. The next term is the same as the lengthy expression above, but with all the 9s replaced with 10s and the final 7 decremented to 6.
This results in 777777777…777777776 with 77777777 7s. The next term is the same again but with the 10s changed to 11s and the final 6 again decremented to 5, which results in about 4.246073865*10156,262,239.
Despite the rapid growth, any such sequence will eventually return to 0. G(19) in particular, takes fw^w(8), a number far larger than Graham’s number or even anything practically expressible in Conway’s chained arrow notation, steps to fall back to 0.
The Goodstein function gives the number of terms in the sequence up to and including the first zero. The output of the Goodstein function can be found by taking the input plus 1, expressing it in base 2 hereditary notation, and then replacing all 2s with ω, then plugging that into a slightly different Hardy hierarchy.
An example of a function that just completely transcends almost everything we’ve covered so far is the TREE function (devised by Harvey Friedman), which arose from graph theory, and is defined as follows:
Suppose we have a sequence of k-labelled trees with the following properties:
1. Each tree has a number of vertices no greater than its index in the sequence, that is, for a sequence (T1, T2, T3, T4, …)
2. No tree is homeomorphically embeddable into a subsequent tree in the sequence. This means that no part of the tree can be “contained” within a later tree in the sequence, that is, have the same nodes in the same order.
According to Kruskal’s tree theorem, such a sequence of trees cannot continue infinitely. The value of TREE(n) is the length of the sequence of n-labelled trees.
The first two values of TREE(n), TREE(1) and TREE(2), are equal to 1 and 3 respectively. But hold on to your hardy hats: the very next value of TREE(n), TREE(3), is famously large, and is far, far greater than Graham’s number, and is in fact near the outer reaches of BEAF!
An internet user claims to have proven that TREE(3) ≡ 3 (mod 8).
The growth rate of the TREE function is believed to be roughly equivalent to fϑ(Ωʷω) in the fast-growing hierarchy, which is slightly more powerful than Bowers’ {X, X(1)2} & X arrays. To find out what exactly that subscript means, see the article on ordinals.
For 1, the optimal sequence in this language has only one member: (). The optimal sequence for k=2 has three members: (), [[]], and [].
Bignum Bakeoff was a competition held in December 2001. Its object was to name the largest number possible using 512 characters or less in the programming language C, assuming a fictional computer with infinite resources. 20 entries were submitted to the competition by a total of ten people. The winning entry was submitted by Ralph Loader, and it is one of the largest numbers known.
Three of the programs outputted 1 because they failed to produce the largest number, and another three programs did not terminate. The first two programs by an anonymous Pete did not terminate, but the third was the first to actually produce a large number.
Below is the full decimal expansion of the output of pete-3.c.
23292479355228506120629103772205782521188556601365594768126262808438806540095385289219152367764951472483434579932913443405761122010738810864711712947727372583238365228030815708368105772248573097826643896491485324536255232791227961592036609194479127526553544504755505641588760449935355381277623598581929299236167791999017226178068796899131268137948410262725752057313568787813656536514657337239890061615130555787285358522635888992125632724527232536411274866890787299237298176
Spot the many interesting digit patterns seen in this number.
It turns out that because the a << b (left shift) operator in Pete's third program is left-to-right associative, and there were no parentheses in the program, pete-3.c ends up being a number of only 473 digits. It could have been much larger if there were parentheses, but wait until you see how large pete-4.c is:
pete-4.c ≈ fω*33(100,000)
This number is definitely much larger than Graham's number, since even the fω + 2 function easily beats Graham's number, but here the approximation uses fω*33!
Pete's fifth entry is much larger, being approximately fω¹¹ + 16(1,000), which is comparable to a 13-entry array of 12 1000s followed by some very large integer. And yet it pales in comparison to the next two of Pete's entries (pete-7.c is approximately fω^ω(2 ↑↑ 35)).
However, Pete’s next submission is “only” about E301#386,201,104 in Hyper-E notation. This places it between 10 ↑↑ 386,201,105 and 10 ↑↑ 386,201,106, meaning it vanishes in comparison to the last four entries submitted by Pete.
pete-9.c is actually slightly smaller than pete-8.c, and their decimal expansions end with the same digits.
The entry submitted by Harper is approximately a power tower of 2s 22^100,000,002 terms high, making it greater than googolplex-stack. It is commonly approximated as 10 ↑↑ 1010³⁰¹⁰²⁹⁹⁹ in base 10. I refer to this number as Harper’s number.
The entry submitted by Ioannis can be approximated by 9 {{1}} 117 in terms of expansion. It is the smallest entry in the competition to be greater than Graham's number, and it is exactly equal to booga applied to 9 116 times. The last 8 digits of this number are ...82688009.
Ioannis's number is defined using an Ackermann-like function that mimics the hyperoperators. He then defined d(x) = a(x, x, x) using the previous function, and finally came up with a number using this new function equal to 116 iterations of the d function starting with 9.
The output of loader.c is so large that it cannot be approximated with any other googological notation known. It probably ranks third place for the most well-known numbers larger than Graham's number, with Rayo's number in second place, and TREE(3) in first place.
Loader's number is defined using a function that diagonalizes over the calculus of constructions. It is defined as D5(99), where D5 represents 5 iterations of the D function. D(99) is larger than 2 ↑↑ 30,419, and D(D(99)) is much larger than fԑ₀+ω³(1000000), a tetrational-array range number.
And if even the second D function applied to 99 is overwhelming, just try to imagine the next three! It totally leaves even the second place entry in the dust!
Loader's number is the largest known computable number. It is considered a computable number because it is defined with a computer program, even though the program would require an unfathomable amount of resources to actually run.
Some smaller values of Loader’s D function have been computed. Googology Wiki user Deedlit11 obtained D(8) = 496 (or 31 * 2^^3) and D(9) = 2031616 (or 31 * 2^^4), but encountered errors attempting to compute D(10) (which can be lower-bounded by 31*265536 ~ 6.21093*1019,729 if the pattern continues). In January 2020, Googology Wiki user Tetramur conjectured that all outputs of D(n) are of the form 31*(2^^k), which would imply that the last 21 digits of Loader’s number are …057067335956421410816.
However, another Googology Wiki user going by Wythagoras obtained 2013265921 (15*227 + 1) as the value of D(0), and 2013265921*21006632960 (~ 7.725412 * 10303,026,724) for D(1).
In the next section, we will cover a function that grows faster than any computable function, even Loader's D function!
All the functions we have covered up to this point have an important property. They are all computable, which means that if a computer had infinite resources and time, it could calculate the function. However, in this section we will cover the busy beaver function, which is uncomputable, meaning no computer could calculate it even with infinite resources.
The busy beaver function is a well-known example of an uncomputable function, which is a function that is impossible to program a Turing machine (and by the Church-Turing thesis, any modern computer like the one you’re reading this on). It eventually dominates all computable functions, and its growth rate is believed to be comparable to fα(n) in the fast-growing hierarchy, where α is the Church-Kleene ordinal (denoted ω1CK).
It is trivial to see that ∑(1) is equal to 1. Single-state Turing machines either continue infinitely or halt after the first step. Below are the small values for the busy beaver function and bounds for higher values.
∑(1) = 1
∑(2) = 4
∑(3) = 6
∑(4) = 13
∑(5) = 4,098
∑(6) > 1010^10^10^10^10^10^10^10^10^1.78*10^44,305,191
∑(9) > 10 ↑↑ 28
∑(10) > 3 ↑↑↑ 3
∑(11) > 3 ↑↑↑ 720618962331271 > 3^^^3^^^2
∑(17) > Graham's number
∑(38) > fω²(167) ~ cg(169)
∑(64) >fω²(4,098) ~ cg(4,100) ~ {4100, 4100, 4100, 4100}
∑(85) > fε₀(1907) ~ 1907^^1906 & 1907
It is overwhelmingly likely that something like ∑(10,000) or even ∑(∑(6)) is larger than the largest numbers currently known.
The maximum shifts function, or the frantic frog function, is related to the busy beaver function. It gives the number of state changes for an n-state, 2-color Turing machine before halting.
S(1) = 1
S(2) = 6
S(3) = 21
S(4) = 107
S(5) = 47,176,870
Just when you thought the D function was the most powerful function devised in googology, you’re in for yet another surprise. On January 26, 2007, the Big Number Duel was held at Princeton University, and the participants were Agustin Rayo of MIT and Adam N. Elga of Princeton University.
Elga went first, and wrote a 1 on the board. Rayo responded by filling the board with 1s, to which Elga then responded by replacing many of the 1s with factorials. After that, they began inventing their own large number notations, and finally Rayo wrote on the board:
The smallest positive integer bigger than any finite positive integer named by an expression in the language of first-order set theory in googol symbols or less.
Rayo won the competition, since Elga was unable to come up with a significantly larger number. Rayo's number was long recognized as the largest number ever defined in googology, and is still famous as one of the largest numbers ever defined. However, we will almost certainly never know any of its digits or even just how large it is.
Normally, this kind of definition would lead to the Berry paradox, where the definition of a number contradicts itself (as in "the largest number that can be defined in . However, in FOST, we cannot define definability, so the Berry paradox is impossible in FOST.
Rayo’s function is uncomputable, meaning that much like the busy beaver function, no computer can calculate Rayo(n).
Some lower bounds of Rayo's function for smaller values have been devised. Rayo(n) is known to be equal to 0 for all values of n from 0 to 9, and 1 for n=10 up to n=29. However, beginning with n=30, no exact values are known. Googology Wiki user Ytosk has proven that Rayo(88) is at least 4 and that Rayo(34 + 20n) is greater than n. In April 2020, research began on how to represent 65,536 and all further tetrations of 2 in FOST. It has since been proven that Rayo(260 + 20n) is at least 2^^n, meaning Rayo(360) is at least 2^65536 and Rayo(380) is at least 2^^6. And, finally, it can be shown that Rayo(7339) is greater than S(2^65536 - 1) where S is the maximum shifts function mentioned earlier.
The information in the above paragraph can all be found on the Rayo's number article on the Googology Wiki.
Rayo's function diagonalizes over first-order set theory. In 2014, a supposedly larger number named BIG FOOT was defined, using first-order oodle theory (which was meant to diagonalize over n-th order set theory), and a corresponding FOOT function. BIG FOOT was equal to FOOT(FOOT(FOOT(FOOT(FOOT(FOOT(FOOT(FOOT(FOOT(FOOT(10^100)))))))))). However, BIG FOOT turned out to be ill-defined, as first-order oodle theory turned out to be inconsistent. Other unsuccessful attempts to beat Rayo's number include Little Bigeddon and Sasquatch, however, one larger number has been defined: Large Number Garden Number, which is defined as f^10(10 ↑↑↑↑↑↑↑↑↑↑ 10) where f is the function defined in First Order Theory beyond Higher Order Set Theory.
In our quest to define ever larger numbers, we will never get any closer to infinity than when we first learned to count "1, 2, 3, ...".