Large Numbers — Long Notes

The Ever-Growing List of Googologists' Milestones, Nearly Monotonically Arranged and Set Forth in Many Ostensibly Alternative Representations

Universe Size Paradox

The radius of the "visible universe" is about 4.6×10¹⁰ light years, assuming the Lambda-CDM model ("standard cosmological model") with parameters that most closely explain the spatial frequency distribution of the cosmic microwave background radiation. This size is 4.45×10²⁶ meters and 2.75×10⁶¹ in Planck units.

This is a "comoving distance", a cosmological term which roughly describes a distance one would get if it were possible to measure "instantly" without the effects of relativity. The matter that produced the cosmic background radiation, emitted 13.72 billion years ago, has subsequently traveled away from us (while forming into galaxies) and is now about 46 billion light years from us.

There seems to be a paradox: this is over three times as big as the age of the universe would suggest. Moving at the speed of light, such matter could only have gotten as far as 13.72 billion light years in any direction. The paradox is resolved by the fact that much of the time was spent traveling across a smaller universe; and much of the "extra travel distance" added by the universe's expansion has already been covered by the photons during the younger, smaller universe. So the space can be expanding faster than light (relativity does not limit how fast the space can expand, only the speed at which things inside the space can travel).

Here are some pictures and an analogy. We are going to imagine a rubber band that is being stretched at a rate of one centimeter per second. After it has stretched to a length of 4 cm, an ant, here labeled "A", begins walking from one end of the band, trying to reach the other end. The ant walks at exactly 1 cm per second, and the rubber band keeps stretching while it walks. It is a "perfect rubber band", so it can start at "zero length" and it can keep stretching as long as we wish.

In the diagrams, "U" represents us, the "::" represent intermediate points on the rubber band ("galaxies"). We imagine that the rubber band represents a space that is expanding, and it along with Us, the Ant and the galaxies constitute the "universe". The ant is like a photon. Here are the first 4 seconds, from the beginning "*" to the moment the ant starts walking:

0 sec * 0 cm 1 sec U::;A 1 cm 2 sec U-:-:-:-A 2 cm 3 sec U--:--:--:--A 3 cm 4 sec U---:---:---:---A 4 cm

The band is stretching and the ant is walking simultaneously. It's not really "fair" to do one and then the other. I'll try to balance it out by breaking it up into three steps. The rubber band stretches 1/2 cm:

U----:---:----:---A 4.5 cm

the ant crawls 1 cm:

U----:---:----A---a 4.5 cm

then the band stretches another 1/2 cm:

5 sec U----:----:----A----a 5.0 cm

Then we repeat: the rubber band stretches 1/2 cm, the ant moves 1 cm, and the band stretches another 1/2 cm:

U----:-----:-----A----a 5.5 cm U----:-----:-A---:----a 5.5 cm 6 sec U-----:-----:-A---:-----a 6.0 cm

And again, several more times. Notice that the halfway point is crossed just about exactly at the 6.5 cm point, when the "universe" is 6.5 seconds old:

U-----:------:-A---:------a 6.5 cm U-----:----A-:-----:------a 6.5 cm 7 sec U------:----A-:------:------a 7.0 cm U------:-----A-:------:-------a 7.5 cm U------:-A-----:------:-------a 7.5 cm 8 sec U-------:-A-----:-------:-------a 8.0 cm U-------:-A------:-------:--------a 8.5 cm U-----A-:--------:-------:--------a 8.5 cm 9 sec U------A-:--------:--------:--------a 9.0 cm U------A-:---------:--------:---------a 9.5 cm U--A-----:---------:--------:---------a 9.5 cm 10 sec U--A------:---------:---------:---------a 10.0 cm

The ant is now less than 1 cm from us, so it takes less than one second to complete its journey:

UA--------:----------:---------:----------a 10.5 cm 10.8 sec A----------:----------:---------:----------a 10.8 cm

The ant has arrived, with news from a galaxy that was 4 seconds old at the time, but the age of the universe now is 10.8 seconds, and the ant has spent 6.8 seconds traveling. Look at some of the other numbers:

Total age of "universe": 10.8 sec
Age of universe when the ant began to travel: 4.0 sec
Time spent to reach the halfway point: 2.5 sec
Age of universe when ant was halfway between us and its starting point: 6.5 sec
Time spent to make the rest of the trip: 4.3 sec
How long the ant was travelling: 6.8 sec
Age of the news the ant brings ("lookback time"): 6.8 seconds ago
Apparent "distance" of the galaxy ("angular size distance"): 4.0 cm

To scale, the history of this part of the universe looks like this:

0 sec * 0 cm 1 sec U::;A 1 cm 2 sec U-:-:-:-A 2 cm 3 sec U--:--:--:--A 3 cm 4 sec U---:---:---:---A 4 cm 5 sec U----:----:----A----a 5.0 cm 6 sec U-----:-----:-A---:-----a 6.0 cm 7 sec U------:----A-:------:------a 7.0 cm 8 sec U-------:-A-----:-------:-------a 8.0 cm 9 sec U------A-:--------:--------:--------a 9.0 cm 10 sec U--A------:---------:---------:---------a 10.0 cm 10.8 s A----------:----------:---------:----------a 10.8 cm

But this only includes what we see if we look 6.8 Gyr into the past. There are objects that gave off light earlier than that, which are further away. Looking at the figures above, you can see that another ant could have begun walking earlier, when the rubber band was shorter, and it would have reached us a lot earlier. It follows that the rubber band could be larger, with an end growing at faster than 1 cm per second, and an ant walking at the normal 1 cm/sec speec would be able to reach us at time 10.8 provided that it begins its trip earlier.

Here is a similar path for another ant, labeled "B", that decides to leave its galaxy when the "universe" was about 1.5 seconds old. Again, "U" is us, "a" and "b" are the home galaxies of the two ants, and the total size of the larger universe, now including B's galaxy, is shown on the right:

0 sec * 0 cm 1 sec U::;a::;B 2 cm 2 sec U-:-:-:-a-:-:-B-b 4 cm 3 sec U--:--:--:--a--:B-:--:--b 6 cm 4 sec U---:---:---:---B---:---:---:---b 8 cm 5 sec U----:----:----B----a----:----:----:----b 10 cm 6 sec U-----:-----:-B---:-----a-----:-----:-----:-----b 12 cm 7 sec U------:----B-:------:------a------:------:------:------b 14 cm 8 sec U-------:-B-----:-------:-------a-------:-------:-------:-------b 16 cm 9 sec U------B-:--------:--------:--------a--------:--------:--------... 18 cm 10 sec U--B------:---------:---------:---------a---------:---------:--... 20 cm 10.8 s B----------:----------:---------:----------a----------:--------... 21.6 cm

Because the distance between galaxies was less than 1 cm at the beginning of its trip, ant "B" is able to pass 2 galaxies during its first second of travel. It reaches "A" after it has travelled 2.5 seconds, and then they both travel together to reach us. B's travel time ends up being 9.3 seconds (as measured by us) and nearly all of this is the second half of its trip. When we see the light from "B", it makes the universe appear to be twice as large, with an "edge" that is receding from us at twice the speed of light.

And what about an ant from "C" that starts its trip when the universe is only about 0.3 seconds old?

0 sec * 0 cm 1 sec U::;a::;b:C::;::c 4 cm 2 sec U-:-:-:-a-:-:-C-:-:-:-:-:-:-:-:-c 8 cm 3 sec U--:--:--:--a--:C-:--:--b--:--:--:--:--:--:--:--c 12 cm 4 sec U---:---:---:---C---:---:---:---b---:---:---:---:---:---:---:---c 16 cm 5 sec U----:----:----C----a----:----:----:----b----:----:----:----:- ... 20 cm 6 sec U-----:-----:-C---:-----a-----:-----:-----:-----b-----:-----:- ... 24 cm 7 sec U------:----C-:------:------a------:------:------:------b----- ... 28 cm 8 sec U-------:-C-----:-------:-------a-------:-------:-------:----- ... 32 cm 9 sec U------C-:--------:--------:--------a--------:--------:------- ... 36 cm 10 sec U--C------:---------:---------:---------a---------:---------:- ... 40 cm 10.8 s C----------:----------:---------:----------a----------:------- ... 43.2 cm

Now the total size of the "visible universe" is more than twice its "age". The further and further back one looks, the larger the "universe" appears to be. The size of the visible universe is limited not by its age, but only by our ability to detect highly redshifted light!

This simple model is called the "nearly empty universe", and reflects what could happen if there was an arbitrarily large flat Euclidean space-time, with a negligible amount of gravitational effect on the local passage of time. However, the real universe has a lot of matter, and an even greater amount of energy, dark matter and dark energy. The presence of all of this matter and energy create a gravitational field that (as explained by general relativity) affects the passage of time as experienced in different reference frames, which in turn affects the travel-time of photons as measured in local and remote reference frames. The net effect is to prevent us from seeing all the way to the edge of an infinite space (whether flat Euclidean, or negatively curved hyperbolic, assuming an infinite universe even exists). In a critical density model (where the amount of matter and energy are just barely enough to prevent infinite expansion) it turns out that the distance we could "see" would be exactly three times as far as the "age" of the universe. In other words, in a 13.72 billion-year-old universe, we could see objects that are 3×13.72 = 41.16 billion light years away. In fact, the density is not exactly critical, so the current size of the visible universe is a little bigger (due to the action of dark energy causing the rate of universe expansion to be increasing over time), about 46 billion light years.

For a lot more on this, and more accurate diagrams, see Wright's cosmology FAQ [3] as well as the articles by Davis and Lineweaver [1], [2].

References

[1] Tamara M. Davis and Charles H. Lineweaver, Expanding Confusion: Common Misconceptions of Cosmological Horizons and the Superluminal Expansion of the Universe, 2004.

[2] http://space.mit.edu/~kcooksey/teaching/AY5/MisconceptionsabouttheBigBang_ScientificAmerican.pdf Charles H. Lineweaver and Tamara M. Davis, Misconceptions about the Big Bang, Scientific American, February 2005.

[3] http://www.astro.ucla.edu/~wright/cosmology_faq.html Edward L. Wright, Frequently Asked Questions in Cosmology (web page), 2009.

Versions of Ackermann's Function

Much of the following information, including the names like ack-h, originate with John Cowles, "Ackermann's Original Function" and "more on Ackermann", which were email messages sent to Robert S. Boyer, and included as comments in an Nqthm file by Boyer in 1992.[5]

Ackermann, 1928 (as translated by van Heijenoort in the article "On Hilbert's construction of the real numbers" appearing in the 1967 book "From Frege to Gödel: A Source Book in Mathematical Logic"):

ack(x,y,z) = { y+z for x = 0 { { 0 for x = 1, z = 0 { { 1 for x = 2, z = 0 { { y for x > 2, z = 0 { { ack(x-1, y, ack(x,y,z-1)) for x,z > 0

Analysis:

ack(0,y,z) = y+z ack(1,y,0) = 0 ack(1,y,1) = ack(0,y,ack(1,y,0)) = y+ack(1,y,0) = y = y×1 ack(1,y,2) = ack(0,y,ack(1,y,1)) = y+ack(1,y,1) = y+y = y×2 ack(1,y,n+1) = ack(0,y,ack(1,y,n)) = y+ack(1,y,n) so by induction, ack(1,y,z) = y×z ack(2,y,0) = 1 ack(2,y,1) = ack(1,y,ack(2,y,0)) = y×ack(2,y,0) = y = y¹ ack(2,y,2) = ack(1,y,ack(2,y,1)) = y×ack(2,y,1) = y×y = y² ack(2,y,n+1) = ack(1,y,ack(2,y,n)) = y×ack(2,y,n) so by induction, ack(2,y,z) = y^z ack(3,y,0) = y ack(3,y,1) = ack(2,y,ack(3,y,0)) = y^ack(3,y,0) = y^y = y^④2 ack(3,y,2) = ack(2,y,ack(3,y,1)) = y^ack(3,y,1) = y^(y^④2) = y^④3 ack(3,y,n+1) = ack(2,y,ack(3,y,n)) = y^ack(3,y,n) so by induction, ack(3,y,z) = hy(y,4,z+1) = y^④(z+1)

The Robert Ritchie version is from Robert L. Ritchie, "Classes of Recursive Functions Based On Ackermann's Function" published in the Pacific Journal of Mathematics (v.15 #3) in 1965. It is defined to match the Grzegorczyk hierarchy which is a useful introduction to the fast-growing hierarchy.

ack-rr(i,x,y) = { x + 1 for i = 0 { { x + y for i = 1 { { x y for i = 2 { { 1 for i > 2, y = 0 { { ack-rr(i-1, x, ack-rr(i,x,y-1)) for i > 2, y > 0

The Edelsbrunner/Herbert version is from Edelsbrunner and Herbert, "Algorithms in Combinatorial Geometry", 1987. It is apparently mistranslated from Ackermann's paper:

ack-h(x,y,z) = { y+z for x = 0 { { 0 for x > 0, z = 0 { { y for x > 0, z = 1 { { ack-h(x-1, y, ack-h(x,y,z-1)) for x > 0, z > 1

Analysis (mostly from [4]):

ack-h(0,y,z) = y+z by definition ack-h(1,y,0) = 0 by definition ack-h(1,y,1) = ack-h(0,y,ack-h(1,y,0)) = ack-h(0,y,0) = y ack-h(1,y,2) = ack-h(0,y,ack-h(1,y,1)) = ack-h(0,y,y) = y+y ack-h(1,y,3) = ack-h(0,y,ack-h(1,y,2)) = ack-h(0,y,y) = y+(y+y) by induction, ack-h(1,y,z) = y×z ack-h(2,y,0) = 0 by definition ack-h(2,y,1) = y by definition ack-h(2,y,2) = ack-h(1,y,ack-h(2,y,1)) = ack-h(1,y,y) = y×y ack-h(2,y,3) = ack-h(1,y,ack-h(2,y,2)) = ack-h(1,y,y×y) = y×(y×y) by induction, ack-h(2,y,z) = y^z (except when z=0) ack-h(3,y,0) = 0 by definition ack-h(3,y,1) = y by definition ack-h(3,y,2) = ack-h(2,y,ack-h(3,y,1)) = ack-h(2,y,y) = y^y ack-h(3,y,3) = ack-h(2,y,ack-h(3,y,2)) = ack-h(2,y,y^y) = y^(y^y) by induction, ack-h(3,y,z) = y^④z (except when z=0) ack-h(4,y,0) = 0 by definition ack-h(4,y,1) = y by definition ack-h(4,y,2) = ack-h(3,y,ack-h(4,y,1)) = ack-h(3,y,y) = y^④y ack-h(4,y,3) = ack-h(3,y,ack-h(4,y,2)) = ack-h(3,y,y^④y) = y^④(y^④y) by induction, ack-h(4,y,z) = y^⑤z (except when z=0)

In general, ack-h(n,y,z) = hy(y,n+1,z) = y⁽ⁿ⁺¹⁾z, where ⁽ⁿ⁺¹⁾ is the generalized hyper operator.

Relationship between ack(x,y,z) and ack-h(x,y,z):

ack(0,y,z) = y+z = ack-h(0,y,z) for y>=0, z>=0 ack(1,y,z) = y×z = ack-h(1,y,z) for y>=0, z>=0 ack(2,y,z) = y^z = ack-h(2,y,z) for y>=0, z>0 ack(3,y,z) = ack-h(3,y,z+1) for y>=0, z>0 For x>3, ack(x,y,z) and ack-h(x,y,z) do not compare directly.

Rosza Peter (also called Rosa Politzer) simplified Ackermann's three-argument function to the following two-argument version in 1935:

ack-rp(a,b) = { 2b+1 , for a = 0 { { ack-rp(a-1, 1) , for a > 0, b = 0 { { ack-rp(a-1, ack-rp(a,b-1)) , for a,b > 0

Raphael M. Robinson simplified Peter's version in 1948. This version is significant in being the first to invoke only the successor f(x)=x+1 and predecessor f(x)=x-1 functions (the suffix "ps" is for "Peter simplified"):

ack-ps(a,b) = { b+1 , for a = 0 { { ack-ps(a-1, 1) , for a > 0, b = 0 { { ack-ps(a-1, ack-ps(a,b-1)) , for a,b > 0

Analysis:

ack-p(0,b) = b + 1 ack-p(1,0) = ack-p(0,1) = 2 ack-p(1,b) = ack-p(0, ack-p(1, b-1)) = ack-p(1, b-1) + 1 using induction: ack-p(1,0) = 2 = 0 + 2 ack-p(1,1) = 2 + 1 = 1 + 2 ack-p(2,1) = 3 + 1 = 2 + 2 .'. ack-p(1,b) = b + 2 = 2+(b+3) - 3 ack-p(2,0) = ack-p(1,1) = 3 ack-p(2,b) = ack-p(1, ack-p(2, b-1)) = ack-p(2, b-1) + 2 using induction: ack-p(2,0) = 3 = 0 + 3 ack-p(2,1) = 3 + 2 = 2 + 3 ack-p(2,2) = 5 + 2 = 4 + 3 .'. ack-p(2,b) = 2b + 3 = 2×(b+3) - 3 ack-p(3,0) = ack-p(2,1) = 5 = 2³ - 3 ack-p(3,b) = ack-p(2, ack-p(3, b-1)) = 2×ack-p(3, b-1) + 3 using induction: ack-p(3,0) = 5 = 2^3 - 3 ack-p(3,1) = 2×5 - 3 = 2^4 - 3 ack-p(3,2) = 2×13 - 3 = 2^5 - 3 .'. ack-p(3,b) = 2^(b+3) - 3 = 8×2^b - 3 ack-p(4,0) = ack-p(3,1) = 13 ack-p(4,b) = ack-p(3, ack-p(4, b-1)) = 2^{(ack-p(4, b-1) + 3)} - 3 using induction: ack-p(4,0) = 16 - 3 = 2^④3 - 3 ack-p(4,1) = 2^16 - 3 = 2^④4 - 3 ack-p(4,2) = 2^65536 - 3 = 2^④5 - 3 .'. ack-p(4,b) = 2^④(b+3) - 3 using induction ack-p(0,b) = successor(b+3) - 3 = hy(2,0,b+3) - 3 ack-p(1,b) = 2 + (b+3) - 3 = hy(2,1,b+3) - 3 ack-p(2,b) = 2 × (b+3) - 3 = hy(2,2,b+3) - 3 ack-p(3,b) = 2 ^ (b+3) - 3 = hy(2,3,b+3) - 3 .'. ack-p(a,b) = hy(2,a,b+3) - 3

Recursive calls on 0: ack-p(0,0) = 1; ack-p(1,1) = 3; ack-p(3,3) = 61; ack-p(61,61) = 2⁽⁶¹⁾64 - 3

Buck, 1963:

ack-b(x,y) = { y+1 , for x=0 { { 2 , for x=1, y=0 { { 0 , for x=2, y=0 { { 1 , for x>2, y=0 { { ack-b(x-1,ack-b(x,y-1)) for x,y > 0

This definition gives the rather pretty results:

ack-b(0,y) = 2⁽⁰⁾y = y+1
ack-b(1,y) = 2^①y = y+2
ack-b(2,y) = 2^②y = 2y
ack-b(3,y) = 2^③y = 2^y
ack-b(4,y) = 2^④y
ack-b(x,y) = 2^ⓧy

Recursive calls on 0: ack-b(0,0) = 1; ack-b(1,1) = 3; ack-b(3,3) = 8; ack-b(8,8) = 2⁽⁸⁾8

Meyer and Ritchie, 1967 (note arguments "(x,z-1)" are corrected from the original source which had "(z,z-1)"):

ack-mr(x,z) = { 1 for z=0 { { 2 for x=0, z=1 { { z+2 for x=0, z>1 { { ack-mr(x-1, ack-mr(x,z-1)) for x,z > 0

Analysis:

ack-mr(x,0) = 1 by definition ack-mr(0,1) = 2 by definition ack-mr(1,1) = ack-mr(0, ack-mr(1,0)) = ack-mr(0,1) = 2 ack-mr(2,1) = ack-mr(1, ack-mr(2,0)) = ack-mr(1,1) = 2 by induction, ack-mr(x,1) = 2 ack-mr(0,2) = 2+2 by definition = 4 ack-mr(1,2) = ack-mr(0, ack-mr(1,1)) = ack-mr(0,2) = 4 ack-mr(2,2) = ack-mr(1, ack-mr(2,1)) = ack-mr(1,2) = 4 by induction, ack-mr(x,2) = 4 ack-mr(0,z) = 2+z for z>=2 (by definition) ack-mr(1,0) = 1 by definition ack-mr(1,1) = 2 by (x,1) case above ack-mr(1,2) = 4 by (x,2) case above ack-mr(1,3) = ack-mr(0, ack-mr(1,2)) = ack-mr(0,4) = 6 ack-mr(1,4) = ack-mr(0, ack-mr(1,3)) = ack-mr(0,6) = 8 ack-mr(1,5) = ack-mr(0, ack-mr(1,4)) = ack-mr(0,8) = 10 by induction, ack-mr(1,z) = 2×z ack-mr(2,0) = 1 by definition ack-mr(2,1) = 2 by (x,1) case above ack-mr(2,2) = 4 by (x,2) case above ack-mr(2,3) = ack-mr(1, ack-mr(2,2)) = ack-mr(1,4) = 2×4 = 8 ack-mr(2,4) = ack-mr(1, ack-mr(2,3)) = ack-mr(1,8) = 2×8 = 16 by induction, ack-mr(2,z) = 2^z ack-mr(3,0) = 1 ack-mr(3,1) = 2 by (x,1) case above ack-mr(3,2) = 4 by (x,2) case above ack-mr(3,3) = ack-mr(2, ack-mr(3,2)) = ack-mr(2,4) = 2^4 = 16 ack-mr(3,4) = ack-mr(2, ack-mr(3,3)) = ack-mr(2,16) = 2^16 = 256 by induction, ack-mr(3,z) = 2^④z

So we have ack-mr(n,z) = 2⁽ⁿ⁺¹⁾z where ⁽ⁿ⁺¹⁾ is the generalized hyper operator.

Meyer/Ritchie Reversed: Another version of ack-mr with the role of the arguments reversed:

ack-mrr(x,z) = { 1 for x=0 { { 2 for z=0, x=1 { { x+2 for z=0, x>1 { { ack-mrr(ack-mrr(x-1,z), z-1) for x,z > 0

Analysis: Same as ack-mr above, just reverse all the arguments.

Robert Munafo, 1998: a cleaner form of ack-p with the arguments reversed. (It is "cleaner" because its values more closely resemble the dyadic operators addition, multiplication, exponentiation, and the hyper operator in general.)

ack-p2(a,b) = { intentionally undefined for a=0 or b=0 { { 2a for b = 1 { { 2 for a = 1, b > 1 { { ack-p2(ack-p2(a-1,b), b-1) for a,b > 1

(Except for the argument reversal, this is the same as Harvey M. Friedman's definition of "A(a,b)" in the 2000 paper "The Ackermann Function in Elementary Algebraic Geometry", called "ack-f" in the main article discussion Ackermann's Function).

Analysis:

ack-p2(a,1) = 2a ack-p2(1,b) = 2 ack-p2(a,2) = ack-p2(ack-p2(a-1,2), 1) = 2×ack-p2(a-1,2) and by induction, ack-p2(a,2) = 2^a ack-p2(a,3) = ack-p2(ack-p2(a-1,3), 2) = 2^ack-p2(a-1,3) and by induction, ack-p2(a,3) = 2^④a ack-p2(a,4) = ack-p2(ack-p2(a-1,4), 3) = 2^④ack-p2(a-1,4) and by induction, ack-p2(a,4) = 2^⑤a and by induction, ack-p2(a,b) = hy(2,a+1,b)

Recursive calls on 1: ack-p2(1,1) = 2; ack-p2(2,2) = 4; ack-p2(4,4) = 2^⑤4

Friedman Unary, 2000:

Harvey M. Friedman, after giving the ack-u() definition shown in the main article, which is equivalent to ack-p2() as just mentioned above, defines a unary or single-argument version "A(k)=A(k,k)". We can call this ack-u(k) = ack-p2(k,k) = ack-u(k,k). In terms of the ack-p2(), it is:

ack-u(a) = { intentionally undefined for a=0 { { 2 for a = 1 { { ack-p2(ack-p2(a-1,a),a-1) for a > 1

The first few values are ack-u(1) = 2; ack-u(2) = 4; ack-u(3) = 3³ = 27; ack-u(4) = 4^④4 = 4^{4^4⁴} ≈ 10^{8.0723...×10¹⁵³}; ack-u(5) = 5^⑤5 = 5↑↑5↑↑5↑↑5↑↑5.

Kaitlyn Burnell, 2009: This version was created mainly with the goal of creating fastest growth with the least total number of operators, recursive calls, and conditional tests (each of which counts for "one point"). It most closely resembles ack-mrr but is simpler in that ack-kb(n,0)=n+2 for all n:

ack-kb(x,z) = { x+2 for z=0 { { z for x=0, z>0 { { ack-kb(ack-kb(x-1,z), z-1) for x,z > 0

Analysis:

ack-kb(a,0) = 2+a ack-kb(0,1) = 1 ack-kb(1,1) = ack-kb(ack-kb(0, 1), 0) = ack-kb(1, 0) = 2+1 ack-kb(2,1) = ack-kb(ack-kb(1, 1), 0) = ack-kb(2+1, 0) = 2+2+1 by induction, ack-kb(a,1) = 2×a+1 ack-kb(0,2) = 2 ack-kb(1,2) = ack-kb(ack-kb(0, 2), 1) = ack-kb(2, 1) = 2×2+1 = 5 ack-kb(2,2) = ack-kb(ack-kb(1, 2), 1) = ack-kb(2×2+1, 1) = 2×(2×2+1)+1 = 11 ack-kb(3,2) = ack-kb(ack-kb(2, 2), 1) = ack-kb(2×(2×2+1)+1, 1) = 2×(2×(2×2+1)+1)+1 = 23 by induction, ack-kb(a,2) = 3×2^a-1 ack-kb(0,3) = 3 ack-kb(1,3) = ack-kb(ack-kb(0, 3), 2) = ack-kb(3, 2) = 3×2^3-1 = 23 ack-kb(2,3) = ack-kb(ack-kb(1, 3), 2) = ack-kb(3×2^3-1, 2) = 3×2^(3×2^3-1)-1 = 25165823 ≈ 2^24.58 ≈ 2^④4 ack-kb(3,3) = ack-kb(ack-kb(2, 3), 2) = ack-kb(3×2^(3×2^3-1)-1, 2) = 3×2^(3×2^(3×2^3-1)-1)-1 ≈ 1.1633×10^7575668 ≈ 2^{2^24.58} ≈ 2^④5 Using a three-argument iterated exponential function, Lew Baxter showed that this can be generalized to: ack-kb(x,3) = (3/2) ie3(√8, x, 8/3) - 1 where ie3(a, b, c) is the iterated exponential function: ie3(a, b, c) = a ^ (a ^ ( a ^ ( ... ^ c))) (with b copies of 'a') Using a program like Hypercalc demonstrates the accuracy of the approximation ack-kb(a,3) ≈ 2^④(a+2) for a>3. A similar and even more messy series of examples can show that ack-kb(a,4) grows about as fast as 2^⑤(a+3).

Recursive calls on 0: ack-kb(0,0) = 2; ack-kb(2,2) = 11; ack-kb(11,11) ≈ 2^⑬14

Lew Baxter's Derivation For ack-kb(x,3)

Given the identity (derived above) for ack-kb(x,2) :

ack-kb(x,2) = 3×2^x-1

and the "three-argument iterated exponential" function ie3():

ie3(a, b, c) = a ^ (a ^ ( a ^ ( ... ^ c))) (with b copies of 'a')

reader Lew Baxter gives[7] the closed-form solution:

ack-kb(x,3) = (3/2) ie3(√8, x, 8/3) - 1

We can show this is true using induction. First we need to compute ack-kb(0,3) and ack-kb(1,3) directly. From above:

ack-kb(0, 3) = 3 ack-kb(1, 3) = ack-kb(ack-kb(1-1,3), 3-1) = ack-kb(ack-kb(0,3), 2) = ack-kb(3, 2) = 3×2³ - 1 = 24 - 1 = 23

Then we show that the formula works for ack-kb(1,3):

(3/2) ie3(√8, 1, 8/3) - 1 = (3/2) [√8^(8/3)] - 1 = (3/2)×2^{[(3/2) (8/3)]} - 1 = (3/2)×2^(8/2) - 1 = (3/2)×16 - 1 = 23

Now we can use induction to prove the general case:

IF ack-kb(x, 3) = (3/2) ie3(√8, x, 8/3) - 1 THEN ack-kb(x+1, 3) = ack-kb(ack-kb((x+1)-1, 3), 2) = ack-kb(ack-kb(x, 3), 2) = 3×2^ack-kb(x,3) - 1 = (3/2) × 2^{[ack-kb(x, 3) + 1]} - 1 = (3/2) √8^{[(2/3) (ack-kb(x,3) + 1)]} - 1 = (3/2) √8^{[(2/3) ((3/2) ie3(√8,x,8/3) - 1 + 1)]} - 1 = (3/2) √8^{[(2/3) (3/2) ie3(√8,x,8/3)]} - 1 = (3/2) √8^{ie3(√8,x,8/3)} - 1 = (3/2) × ie3(√8, x+1, 8/3) - 1 .'. ack-kb(x+1,3) = (3/2) ie3(√8, x+1, 8/3) - 1

Since the formula works for ack-kb(x,3) when x=1, and iteratively for all higher x, it works for all x greater than 0.

CompactStar Generalisation to Real Arguments, 2024:

Googologist "CompactStar" defines this Ackermann function extended to real arguments:[8]

For non-negative real numbers x and y: ack-cs(x,y) = { x+y+1 for x<1 { { ack-cs(x-1, y×ack-cs(x-1,1)-y+1) for x>=1, y<1 { { ack-cs(x-1, ack-cs(x,y-1)) for x,y >= 1

They give as examples:

A(0.5, y) = y + 1.5
A(1.5, y) = 1.5y + 2.5
A(2.5, y) = 9×1.5y - 5
A(e, π) ≈ 42.16412690081622
A(π, e) ≈ 3446961975442.875

and refer to A(π, π) as "gagpi" but do not give a value for it.

Attempts to implement ack-cs(x,y) directly in computer code fail for the same reasons as for integer-only Ackermann functions: recursion too deep (exhausting all available stack space, or exhausting memory on systems with "unlimited" stack space), or excessive runtime (if the stack space problem is eliminated e.g. by replacing common repetitive recursion cases with ordinary loops).

However, with a little exploration it is easily seen that for 1<=x<2, ack-cs(x,y) = xy+x+1. Adding this as an additional case to the three in the above definition, the function becomes efficient enough to easily calculate A(π, π) ≈ 3.1308961455...×10¹⁵⁵.

References:

[4] John Cowles and T. Bailey, "Several Versions of Ackermann's Function", formerly at www.cli.com/ftp/pub/nqthm/nqthm-1987/ackermann.msg but now gone.

[5] Robert S. Boyer, Nqthm lemmas relating Ackermann's original function to R. Peter's variation, 1992. At www.cs.utexas.edu/users/boyer/ftp/nqthm/nqthm-1992/examples/basic/peter.events

[6] Kaitlyn Burnell, personal correspondence, 2009. For a while it was published on rpgdl.com as part of an article about fast-growing functions, but that wiki is now gone.

[7] Lew Baxter, personal correspondence, 2012.

[8] "CompactStar" (online persona), Continuous Ackermann function, 2024 or earlier.

(The following was part of my long essay on large numbers, part of this section.)

Details of Conway Chained Arrows

This description began with the one on Susan Stepney's excellent large numbers page.

A. Three-number chains are equivalent to the generalised hyper operator:

a→b→c = hy(a, c+2, b) = a^(c+2)b
= a ↑↑..↑↑ b, with c up-arrows

B. A chain with a final 1 is equivalent to the same chain with the 1 removed:

a→b→...→x→1 = a→b→...→x

C. Conway was silent about the meaning of a two-element chain[9], but a definition is necessary. The most logical approach is to combine the two previous rules and assumes that they work in reverse:

a^b = a↑b = a→b→1 (by rule A)
= a→b (by rule B)
therefore the reverse is true: a→b = a↑b = a^b

D. The last two numbers in a chain can be dropped if the second-to-last is a 1:

a→b→...→x→1→(z+1) = a→b→...→x

E. The last number in the chain can be reduced in size by 1 by taking the second-to-last number and replacing it with the value of the entire chain with its second-to-last number reduced by 1:

a→b→...→x→(y+1)→(z+1)
= a→b→...→x→ (a→b→...→x→y→(z+1)) →z

F. If the last number in the chain is 2, rules D and E combine into:

a→b→...→x→ (y+1) → 2
= a→b→...→x→ (a→b→...→x→y→2) →1
= a→b→...→x→ (a→b→...→x→y→2)
= a→b→...→x→ (a→b→...→x→ (a→b→...→x→(y-1)→2) →1 )
= a→b→...→x→ (a→b→...→x→ (a→b→...→x→(y-1)→2))

and in general,

a→b→...→x→ (y+1) → 2
= a→b→...→x→ (        y times
                 a→b→...→x
                         ) y times

G. A more general expansion of rule E follows:

a→b→...→x→2→ (z+1)
= a→b→...→x→ (a→b→...→x→1→(z+1)) →z
= a→b→...→x→ (a→b→...→x ) →z

a→b→...→x→3→ (z+1)
= a→b→...→x→ (a→b→...→x→2→(z+1)) →z
= a→b→...→x→ (a→b→...→x→ (a→b→...→x) →z) →z

a→b→...→x→4→ (z+1)
= a→b→...→x→ (a→b→...→x→3→(z+1)) →z
= a→b→...→x→ (a→b→...→x→ (a→b→...→x→ (a→b→...→x) →z) →z) →z

and in general,

a→b→...→x→ (y+1) → (z+1)
= a→b→...→x→ ( y times
	a→b→...→x
		) →z y times

The parentheses can only be removed after the chain inside the parentheses has been evaluated into a single number. Remember, the arrows are all taken together at once. You can't group them to evaluate, you can only reduce terms off the end using one of the rules above. a→b→c→d is not equivalent to (a→b→c)→d, a→(b→c→d), a→(b→c)→d, a→b→(c→d) or anything else like that.

The wikipedia article, Conway chained arrow notation, gives this set of rules which is equivalent to the above but probably a bit easier to use:

1. A single-number "chain" is equal to itself.

2. The chain a→b represents the value a^b.

3. If X is any chain (of one or more numbers), the chain X→a→1 is equivalent to X→a.

4a. The chain X→1→b for any value of b, is equivalent to X.

4b. The chain X→a→b for any values of a and b where both are greater than 1, is equivalent to X→(X→(a-1)→b)→(b-1).

4c. By repeating rule 4b we can see that any chain X→a→b with a and b both larger than 1 eventually turns into a chain X→c where "c" is a the value of the recursive construction X→(X→(X→(...(X→1→1)...)))→(b-1))→(b-1) with the number of nested parentheses depending on a.

Regarding 2's at the beginning

Note that 2↑↑↑...↑↑↑2 = 4 regardless of the number of up-arrows. Since any chain starting with 2→2→... will eventually end up as 2→2→c for some large c, it follows that any chain starting with 2→2→... is equal to 4.

Regarding 1's

Any chain starting with 1 eventually ends up as 1→a→b for some a and b, which is 1↑↑↑...↑↑↑a with b arrows. This is just a power of 1, so any chain starting with 1 is equal to 1.

Any chain with a 1 in it someplace else, like a→b→c→1→d→e→f, reduces to a→b→c→1→x for some x, and this then immediately reduces to a→b→c. So if you have anything with a 1 in it, you can remove the 1 and everything after it.

Some Correlations

The rules for Conway chained arrows express them in terms of Knuth's up-arrow notation and recursion; we can also express some of the other functions and numbers discussed above in terms of chained arrows:

Ackermann's function is equivalent to a 3-element chain:

A(m, n) = ( 2→(n+3)→(m-2) ) - 3

The "Graham-Gardner number" is not directly equal to a simple chained-arrow representation, but its definition in terms of the function gn(n) can be re-stated in terms of an interated function fⁱ(n):

f¹(n) = f(n) = 3→3→n = 3↑↑..↑↑3 with n up-arrows
f²(n) = f(f(n)) = 3→3→(3→3→n)
f³(n) = f(f(f(n))) = 3→3→(3→3→(3→3→n))
f⁴(n) = f(f(f(f(n)))), etc.

which gives the "Graham-Gardner number" G equal to f⁶⁴(4) because the construction of Graham-Gardner starts with 3↑↑↑↑3 = 3→3→4, and we increase the number of arrows 63 times.

Now start with f⁶⁴(1), and note that we can reverse rule 4c above (with "3→3" as the value of X), and show that:

f⁶⁴(1) = 3→3→(3→3→(...3→3→(3→3→1))...))    with 64 sets of 3→3
       = 3→3→(3→3→(...3→3→(3→3)→1)...)→1)→1
       = 3→3→64→2

Similarly, we can start with f⁶⁴(27) and show that:

f⁶⁴(27) = 3→3→(3→3→(...3→3→(3→3→27))...))    with 64 sets of 3→3
       = 3→3→(3→3→(...3→3→(3→3→(3→3)))...))
       = 3→3→65→2

Since f⁶⁴(1) < f⁶⁴(4) < f⁶⁴(27), the "Graham-Gardner number" must be between 3→3→64→2 and 3→3→65→2. See here for a somewhat different discussion of the same thing.

(At this point you may wish to return to the higher-level discussion of Conway arrow numbers)

References

[9] John Horton Conway and Richard Guy, The Book of Numbers, Springer-Verlag, New York, 1996. ISBN 038797993X.

Page numbers for specific topics:

p. 60 (Ackermann numbers)

p. 61 (Conway chained-arrow notation)

The Ever-Growing List of Googologists' Milestones, Nearly Monotonically Arranged and Set Forth in Many Ostensibly Alternative Representations

Mega
10↑↑258
10↑↑10↑↑100
10↑↑↑100
10↑↑↑↑100
10↑↑↑↑↑100
10↑⁶100
10↑⁷100

Switch
	hierarchy	Bowers/Bird

Graham's G₆₄



→10&rarr

Conway

Hardy

Bowers/Bird

10→100

H_ω²(324)

{10,100}

10→100→2

H_ω³(100)

{10,100,2}

10→257→2

H_ω³(257)

{10,257,2}

2^{H_Ω²⁵⁷(2)}

10→258→2

H_ω³(258)

{10,258,2}

10→(10→100→2)→2

H_{ω³ 2}(100)

10→100→3

H_ω⁴(100)

{10,100,3}

10→100→4

H_ω⁵(100)

{10,100,4}

10→100→5

H_ω⁶(100)

{10,100,5}

10→100→6

H_ω⁷(100)

{10,100,6}

10→100→7

H_ω⁸(100)

{10,100,7} from Hardy to FGH

Fast-growing

f_ω(10)

3→3→64→2

f_ω+1(64)

{3,65,1,2}

f_{ω 2}(10)

{10,10,10,2}

f_{ω 3}(10)

10→10→10→10→10→10
;10→10→10→9→11

f_ω²(10)

{10,10,10,10}

f_{ω² 2}(10)

f_ω³(10)

{10,10,10,10,10}

f_ω^ω(10)

f_ω^ω+1(10)

f_{ω^{ω 2}}(10)

f_ω^ω²(10)

f_ω^{ω^ω}(10)

f_⁷ω(10)

f_ε₀(10)

f_{ε₀ 2}(10)

f_{ε₀ ω}(10)

f_ε₀²(10)

f_{ε₀↑{ε₀}}(10)

f_ε₁(10)

f_ε₂(10)

f_{ε_ω}(10)

f_{ε_ε₀}(10)

f_ζ₀(10)

f_ζ₂(10)

f_{ζ_ζ₀}(10)

f_η₀(10)

f_φ(7,0)(10)

f_φ(ω,0)(10)

f_φ(ω+1,0)(10)

f_φ(ω+3,0)(10)

f_{φ(ω 2,0)}(10)

f_{φ(ω 3,0)}(10)

f_φ(ω²,0)(10)

f_φ(ω³,0)(10)

f_φ(ω^ω,0)(10)

f_φ(ε₀,0)(10)

f_{φ(φ(ω,0),0)}(10)

f_{φ(φ(φ(ω,0),0),0)}(10)

f_Γ₀(10)

f_φ(1,1,0)(10)

f_φ(1,ω,0)(10)

f_{φ(1,Γ₀,0)}(10)

f_φ(2,0,0)(10)

f_φ(3,0,0)(10)

f_φ(ω,0,0)(10)

f_φ(ω²,0,0)(10)

f_{φ(ε₀,0,0)}(10)

f_{φ(Γ₀,0,0)}(10)

f_φ(1,0,0,0)(10)

f_ϑ(Ω³)(10)

f_ϑ(Ω^ω)(10)

f_ϑ(Ω^ε₀)(10)

f_{ϑ(Ω^ϑ(Ω³))}(10)

f_{ϑ(Ω^{ϑ(Ω^ω)})}(10)

f_ϑ(Ω^Ω)(10)

f_ϑ(Ω^Ω+1)(10)

f_{ϑ(Ω^{Ω 2})}(10)

f_ϑ(Ω^Ω²)(10)

f_ϑ(Ω^Ω³)(10)

f_{ϑ(Ω^{Ω^ω})}(10)

f_{ϑ(Ω^{Ω^Ω})}(10)

f_{ϑ(Ω^{Ω^Ω²})}(10)

f_{ϑ(Ω^{Ω^{Ω^Ω}})}(10)

f_{ϑ(ε_Ω+1)}(10)

f_{ε_{ϑ(ε_Ω+1)+1}}(10)

f_{φ(ω,ϑ(ε_Ω+1)+1)}(10)

f_{φ(ω²,ϑ(ε_Ω+1)+1)}(10)

f_{φ(ω^ω,ϑ(ε_Ω+1)+1)}(10)

f_{φ(ε₀,ϑ(ε_Ω+1)+1)}(10)

f_{φ(ϑ(ε_Ω+1),1)}(10)

f_{Γ_{ϑ(ε_Ω+1)+1}}(10)

f_{φ(1,0,0,ϑ(ε_Ω+1)+1)}(10)

f_{ϑ(Ω^ω,ϑ(ε_Ω+1)+1)}(10)

f_{ϑ(Ω^Ω,ϑ(ε_Ω+1)+1)}(10)

f_{ϑ(ε_Ω+1,1)}(10)

f_{ϑ(ε_Ω+12)}(10)

f_{ϑ(ε_Ω+1Ω)}(10)

f_{ϑ(ε_Ω+1²)}(10)

f_{ϑ(ε_Ω+2)}(10)

f_{ϑ(ε_Ω+ω)}(10)

f_{ϑ(ε_{Ω 2})}(10)

f_{ϑ(ε_{ε_Ω+1})}(10)

f_{ϑ(ζ_Ω+1)}(10)

f_{ϑ(ϑ₁(ω))}(10)

f_{ϑ(ϑ₁(ω³))}(10)

f_{ϑ(ϑ₁(Ω))}(10)

f_{ϑ(ϑ₁(ε_Ω+1))}(10)

f_{ϑ(ϑ₁(Ω₂))}(10)

f_{ϑ(ϑ₁(Ω₂+ϑ₁(Ω₂)))}(10)

f_{ϑ(ϑ₁(Ω₂ 2))}(10)

f_{ϑ(ϑ₁(Ω₂ Ω))}(10)

f_{ϑ(ϑ₁(Ω₂ ε_Ω+1))}(10)

f_{ϑ(ϑ₁(Ω₂²))}(10)

f_{ϑ(ϑ₁(Ω₂³))}(10)

f_{ϑ(ϑ₁(Ω₂^Ω))}(10)

f_{ϑ(ϑ₁(Ω₂^Ω₂}))(10)

f_{ϑ(ϑ₁(Ω₂^Ω₂}+Ω₂))(10)

f_{ϑ(ϑ₁(Ω₂^Ω₂} 2))(10)

f_{ϑ(ϑ₁(Ω₂^Ω₂} ω³))(10)

f_{ϑ(ϑ₁(Ω₂^Ω₂+3}))(10)

f_{ϑ(ϑ₁(Ω₂^{Ω₂ 3}}))(10)

f_{ϑ(ϑ₁(Ω₂^Ω₂²}))(10)

f_{ϑ(ϑ₁(Ω₂^{Ω₂^ω}}))(10)

f_{ϑ(ϑ₁(Ω₂^{Ω₂^Ω}}))(10)

f_{ϑ(ϑ₁(Ω₂^{Ω₂^Ω₂}}))(10)

f_{ϑ(ε_Ω₂+1)}(10)

f_{ϑ(ε_Ω₂+ω)}(10)

f_{ϑ(ε_Ω₂+Ω)}(10)

f_{ϑ(ε_{Ω₂ 2})}(10)

f_{ϑ(ζ_Ω₂+1)}(10)

f_{ϑ(ϑ₂(ω))}(10)

f_ϑ(Ω₃)(10)

f_{ϑ(ε_Ω₃+1)}(10)

f_{ϑ(ε_Ω₇+1)}(10)

f_{ϑ(Ω_ω)}(10)

f_{ϑ(ε_{Ω_ω+1})}(10)

f_{ϑ(ε_{Ω_ω+3+1})}(10)

f_{ϑ(Ω_{ω 3})}(10)

f_{ϑ(Ω_ω³)}(10)

f_{ϑ(Ω_Ω)}(10)

f_{ϑ(Ω_{ε_Ω+1})}(10)

f_{ϑ(Ω_Ω₂)}(10)

f_{ϑ(Ω_Ω₃)}(10)

f_{ϑ(Ω_{Ω_Ω})}(10)

f_{ϑ(Ω_{Ω_Ω₃})}(10)

f_{ψ(ψ_I(0))}(10)

f_ψ(I)(10)

f_ψ(I^ω)(10)

f_ψ(I^I)(10)

f_{ψ(ε_I+1)}(10)

f_{ψ(Ω_I+Ω)}(10)

f_{ψ(Ω_{I+ψ_I(0)})}(10)

f_{ψ(Ω_{I+ψ_{Ω_{I+ψ_I(0)}}(0)})}(10)

f_{ψ(Ω_I2)}(10)

f_{ψ(Ω_I²)}(10)

f_{ψ(Ω_I^ω)}(10)

f_{ψ(Ω_I^Ω)}(10)

f_{ψ(Ω_I^I)}(10)

f_{ψ(Ω_I^Iω)}(10)

f_{ψ(Ω_{I^Iψ_I(0)}})(10)

f_{ψ(Ω_I^{I^ω})}(10)

f_{ψ(Ω_I^{I^I})}(10)

f_{ψ(Ω_{ε_I+1})}(10)

f_{ψ(Ω_{ε_{Ω_I+1+1}})}(10)

f_{ψ(Ω_I2)}(10)

f_{ψ(Ω_{Ω_I2})}(10)

f_{ψ(ψ_I₂(0))}(10)

f_{ψ(ψ_I₃(0))}(10)

f_{ψ(ψ_I₇(0))}(10)

f_{ψ(ψ_{I_ω}(0))}(10)

f_{ψ(ψ_{I_Ω}(0))}(10)

f_{ψ(ψ_{I_I}(0))}(10)

f_{ψ(ψ_{I_I₃}(0))}(10)

f_{ψ(ψ_{I_{I_Ω}}(0))}(10)

f_{ψ(ψv{I(1,0)}(0))(10)

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2024 Dec 07.

s.30

Large Numbers — Long Notes

Contents

Universe Size Paradox

Versions of Ackermann's Function

Details of Conway Chained Arrows

The Ever-Growing List of Googologists' Milestones, Nearly Monotonically Arranged and Set Forth in Many Ostensibly Alternative Representations