Large Numbers

First page . . . Back to page 3 . . . Forward to page 5 . . . Last page (page 11)

The Hyperfactorial and Superfactorial Operators

These are single-argument functions like the factorial but producing higher values.

N.J.A. Sloane and Simon Plouffe use hyperfactorial to refer to the integer values of the K-function, a function related to the Riemann Zeta function, the Gamma function, and others. It is

H(n) = nⁿ (n-1)^n-1 ... 3³ 2² 1¹

For example, H(3) = 27×4×1 = 108 and H(5) = 86400000. This function does not really grow much faster than the normal factorial function.

In 1995, Pickover defined the superfactorial n$ (think of the dollar sign as a factorial sign with an S for "super" drawn on top of it) as follows:

n$ = n!^{n!^{n!^{^..^{^..^n!}}}}

where there are n! repetitions of n! on the right hand side. Using the hyper4 operator, n$ is equivalent to:

n$ = n! ^④ n!

There are other ways to define a higher version of the factorial, such as this and this, and similar definitions with hyper4 in place of exponentiation.

To get an idea how big the hyperfactorial of a pretty normal number can be, read Wayne Baisley's wonderful article "Quantity Has A Quality All Its Own" (and bring your towel).

More Invented Names

Following the examples set by Edward Kasner's "-plex" suffix, and by Steinhaus and Moser (discussed below, many inventions of silly-sounding number names, and systems for constructing names from prefixes, suffixes, and syllables, began to propagate more rapidly via the internet.

This cultural phenomenon is not unlike the Chuquet-like inventions of the 19^th century, and more recent inventions such as those of Bowers described above. Now however, we look at names that go far beyond the methodical naming of every power of 1000 to far larger quantities that require tetration or much faster-growing functions to express.

Jonathan Bowers, mentioned above, has many names covering this area. For example, in analogy to googol and googolplex he refers to 10^④100 as giggol and 10^④(10^④100) as giggolplex.

A 2000 article by Alistair Cockburn[50] discusses a few prefixes to be used in made-up number names, following the example set by Edward Kasner's "-plex" suffix, giving the prefix "fuga-" for the operation n_④n. In a subsequent discussion[53] on c2.com, Stephan Houben pointed out that iterated exponentiation leads to two higher operators, and suggested the prefix "megafuga-" for n^④n or n^^n.

That discussion, along with Bowers, seem to have started the vast and onging pastime that has by now continued for over a generation. There are many thousand invented names documented on the Googology wiki; some are described in my supplemental notes, here and here.

Higher hyper operators

Of course, the pattern of dyadic operators is easily continued:

operation	representation	absolute definition	inductive definition
hyper5	a^^^b or a↑↑↑b or a^⑤b	a^④(a^④( ... ^④a))	a^④(a^⑤(b-1))
hyper6	a^^^^b or a↑↑↑↑b or a^⑥b	a^⑤(a^⑤( ... ^⑤a))	a^⑤(a^⑥(b-1))

and so on.

Bowers has several named numbers in this area, including trisept, 7^⑦7; tridecal, 10^⑩10; and the halloween-scary-themed boogol, a frighteningly large 10⁽¹⁰⁰⁾10. Such "googolisms" continue, but from this point on we'll discuss only Bowers' symbolic notation and the definitions related thereto, and not his invented names for specific numbers.

The First Triadic Operator: The Generalised "Hyper" Function

Since the dyadic operators all fall into a pattern, it is logical to define a triadic operator that combines them all. A triadic operator is a function that acts on three numbers, just as a dyadic operator acts on two numbers.

This new triadic operator is represented as a function with three arguments, and defined as follows:

hy(a,n,b) = { 1 + b for n = 0 { { a + b for n = 1 { { a * b for n = 2 { { a ^ b for n = 3 { { a ^ hy(a,4,b-1) for n = 4 { { hy(a,n-1,hy(a,n,b-1)) for n > 4 { { a for n > 1, b = 1

the following definition is equivalent:

hy(a,n,b) = { 1 + b for n = 0 { { a for n = 1, b = 0 { { a for n > 1, b = 1 { { hy(a,n-1,hy(a,n,b-1)) for n > 0

and also note that:

hy(a,3,b) = a^b = a^b
hy(a,4,b) = a^^b
hy(a,5,b) = a^^^b
hy(a,6,b) = a^^^^b
etc.

Generalising the Hyper Operator for Non-Integer n

Previously we looked at efforts to extend tetration to non-integer values, which in terms of this new "hy(,,)" function means computing hy(a,4,b) for non-integer values of b. Since there is now a third parameter to the function (the middle parameter n) it is natural to consider non-integer values of that too. For example, hy(a,2.5,b) would be a function "between" multiplication and exponentiation.

Gottfried Helms describes an approach to this interesting problem on Maths StackExchange here but not explaining how to compute it. (He does refer vaguely to a "Schröder-mechanism" and refers the reader to the tetration forum, without a specific link, and was possibly thinking of this discussion which also relates the problem to the Hyperoperation#Commutative hyperoperations of Albert Bennett.)

Folkman's Number

In the same article introducing the much more famous Graham's Number, Martin Gardner described a Ramsey theory problem investigated by Jon Folkman. He developed a proof related to the problem, published posthumously in 1970, from which the upper bound of 2^⑤(2⁹⁰¹) is implied. This number is huge but much smaller than any of the variants of Graham's Number to be discussed later.

Bowers' Array Notation (3-element Subset)

At this point we return to the work of Jonathan Bowers to introduce his array notation. This notation is elegant, powerful, relatively easy to use and covers a greater range than any other discussed on these pages, within the limits of functional formal systems.

We will start by showing a very reduced version of the notation, which uses arrays of only 1, 2, or 3 elements. The rules for converting the notation into a number are:

1. A one-element array [a] is just the number itself. A two-element array [a,b] means a^b.
2. If rule 1 does not apply, and if there are any trailing 1's, remove them: [a,b,1] = [a,b] = a+b; [a,1,1] = [a] = a.
3. If neither previous rule applies, and the 2nd entry is a 1, remove all but the first element: [a,1,n] = [a] = a.
4. (rule 4 is used only for longer arrays).
5. Otherwise replace the array [a,b,n] with [a,[a,b-1,n],n-1], then go back and repeat the rules to expand it further.

With just a little effort you can see that these rules make [a,b,n] equivalent to hy(a,n,b) except for the special case of n=0. Compare the formula of rule 5:

[a,b,n] = [a,[a,b-1,n],n-1]

with the general case of the definition of the hyper function:

hy(a,n,b) = hy(a,n-1,hy(a,n,b-1))

They are the same except the order of the arguments is different. Bowers arranges the arguments in order of increasing "growth potential" — the operator has higher growth potential than b, so it goes last.

So, all 3-element Bowers arrays are equivalent to the normal hyper operators. [3,2,2] = 3^②2 = 3×2 = 6; [3,2,3] = 3^③2 = 3², [4,5,6] = 4^⑥5, etc.

Redefined

The above is how the Bowers array notation was defined when I first learned of it. It treats addition as the first in a series of "hyperoperators", and multiplication as the second.

The use of repeated carats, such as a^^b for tetration and a^^^b for pentation, led to the variant a↑↑b a↑↑↑b, etc. that is called Knuth up-arrow notation and described fully below. This notation was popularized as early as Martin Gardner's 1977 article introducing Graham's number, and came into broad and general usage in the internet era. Counting the carats ^^^ or up-arrows ↑↑↑ is an important part of understanding this notation, and it is less imporatant to think about addition and multiplication being earlier members of a logical series of operations. Thus, and at the request of Chris Bird, Jonathan Bowers redefined his array notation by changing the meaning of [a,b] from a+b to a^b:

1. A one-element array [a] is just the number itself. A two-element array [a,b] means a^b = a↑b.
2. If rule 1 does not apply, and if there are any trailing 1's, remove them: [a,b,1] = [a,b] = a^b; [a,1,1] = [a] = a.
3. If neither previous rule applies, and the 2nd entry is a 1, remove all but the first element: [a,1,n] = [a] = a.
4. (rule 4 is used only for longer arrays).
5. Otherwise replace the array [a,b,n] with [a,[a,b-1,n],n-1], then go back and repeat the rules to expand it further.

We can see now that for a,b,c all greater than 1:

[a,2,2] = [a,[a,1,2],1] = [a,a,1] = [a,a] = a^a = a^^2
[a,3,2] = [a,[a,2,2],1] = [a,a^a,1] = [a,a^a] = a^{a^a} = a^^3
[a,4,2] = [a,[a,3,2],1] = [a,a^^3,1] = [a,a^^3] = a^{a^^3} = a^^4
[a,b,2] = a^^b in general
[a,2,3] = [a,[a,1,3],2] = [a,a,2] = a^^a = a^^^2
[a,3,3] = [a,[a,2,3],2] = [a,a^^a,2] = a^^(a^^a) = a^^^3
[a,b,3] = a^^^b in general
[a,b,n] = a^^^..^b (with n ^s) in general

Thus, by this slightly newer definition [a,b,n] is hy(a,n+2,b). Changing "a+b" to "a^b" in rule 1 simply boosts the hyperoperation by 2. When expressing it in up-arrow notation, the 3^rd number in the 3-element array indicates the number of up-arrows rather than the "hyperoperation index".

hyper operator variant: Knuth's Up-arrow Notation

The use of two or more carets (as in "a^^b" or "a^^^b") resembles a notation defined by Donald Knuth¹⁷ in 1976 ("a↑↑b" and "a↑↑↑b" respectively), and is equivalent to the hyper operator. Carets are commonly seen in old ASCII sources such as mailing lists from the early days of USENET, but Knuth used real arrows: a↑↑b and a↑↑↑b instead of a^^b or a^^^b.

a↑↑b = hy(a,4,b)
a↑↑↑b = hy(a,5,b)
a↑↑↑↑b = hy(a,6,b)
(etc.)

using the hy() function allows for a more compact representation of really large numbers that would otherwise take a lot of arrows. For example, hy(10,20,256) is equivalent to

10↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑256

and hy(256,625,4096) would be very unwieldy. Bigger numbers like hy(256,4294967296,256) can't be written at all.

This up-arrow notation is used in defining the Ackermann numbers

A(n) = n↑↑↑...↑↑↑n (with n up-arrows) = hy(n, n+2, n)

which are related to the Ackermann function described below.

In 2010 Knuth informed me [58] that he has found "the Ackermann-like 'arrow notation' in a 19^th century encyclopedia."

Partial Ordering for Knuth Up-Arrows

One may speculate on the general problem of determining which is the larger of two values a↑↑↑...↑↑↑b and x↑↑↑...↑↑↑y. We can begin to make answer that question for small numbers of up-arrows. In particular (for later discussion) we care about the answer when a, b, x and y are positive integers.

First, note that if a is 1, a↑↑↑...↑↑↑b is just a power of 1, which is always 1. Also, if a and b are 2 then the value of a↑↑↑...↑↑↑b is 4, regardless of the number of arrows.

With a single arrow a↑b is the familar exponentiation operation.

2³ is smaller than 3²
2⁴ is the same as 4²
for any other a and b, if b is greater than a then a^b is greater than b^a.
in general, to compare a^b to c^d we can probably calculate both directly, so long as all four numbers are class 1.

With two arrows, a↑↑b is a "power-tower" of height b. Using Hypercalc it is relatively easy to compile a list of a↑↑b for all the smaller values of a and b, and larger values of a. Here I'll also show the smaller values of c↑d that are not expressible as in the form a↑↑b, to see where they fit in:

1↑↑a = 1, for all a
2↑↑1 = 1
3↑↑1 = 3
2↑↑2 = 2² = 4 = 4↑↑1
5↑↑1 = 5
6↑↑1, 7↑↑1, etc. (a↑↑1 = a, for all a)
2³
3²
2↑↑3 = 2^(2²) = 2⁴ = 4² = 16
5²
3↑↑2 = 3³ = 27
2⁵
6², 7²
2⁶ = 8²
3⁴ = 9²
10², 11²
2⁷
12² through 15² and 3⁵
4↑↑2 = 4⁴ = 2⁸ = 256
17², etc.; 2⁸, etc.; 3⁶, etc.
5↑↑2 = 5⁵ = 3125
56², etc.; 15³, etc.; 2¹², etc.; 3⁸, etc.
6↑↑2 = 6⁶ = 36³ = 216² = 46656
217², etc.
2↑↑4 = 2¹⁶ = 4⁸ = 16⁴ = 256² = 65536
7↑↑2 = 7⁷ = 823543
.. 8↑↑2, 9↑↑2, through 11↑↑2
3↑↑3 = 3↑(3³) = 3²⁷ = 7625597484987
12↑↑2 = 12¹² = 8916100448256
.. 13↑↑2 through 80↑↑2
4↑↑3 = 4↑(4⁴) = 4²⁵⁶ ~ 1.3408×10¹⁵⁴
81↑↑2 = 81⁸¹ ~ 3.8662×10¹⁵⁴
.. 82↑↑2 through 758↑↑2
5↑↑3 = 5↑(5⁵) = 5³¹²⁵ ~ 1.911×10²¹⁸⁴
759↑↑2 = 759⁷⁵⁹ ~ 1.269×10²¹⁸⁶
.. 760↑↑2, etc.
2↑↑5 = 2↑(2↑↑4) = 2⁶⁵⁵³⁶ ~ 2.004×10¹⁹⁷²⁸
5298↑↑2 = 5298⁵²⁹⁸ ~ 2.214×10¹⁹⁷³⁰
.. 5299↑↑2, etc.
6↑↑3 = 6↑(6⁶) = 6⁴⁶⁶⁵⁶ ~ 2.659×10³⁶³⁰⁵
7↑↑3 = 7↑(7⁷) ~ 3.76×10⁶⁹⁵⁹⁷⁴
.. 8↑↑3 through 11↑↑3
3↑↑4 = 3↑(3↑↑3) ~ 1.35×10^{3638334640024}
12↑↑3 = 12↑(12↑↑2) ~ 5.85×10^{9622088391634}
.. 13↑↑3 through 80↑↑3
4↑↑4 = 4↑(4↑↑3) ~ 10^{8.0723×10¹⁵³}
.. 81↑↑3 through 758↑↑3
5↑↑4 = 5↑(5↑↑3) ~ 10^{1.336×10²¹⁸⁴}
.. 759↑↑3, etc.
2↑↑6 = 2↑(2↑↑5) ~ 10^{6.03×10¹⁹⁷²⁷}
6↑↑4 = 6↑(6↑↑3) ~ 10^{2.07×10³⁶³⁰⁵}
.. 7↑↑4 through 11↑↑4
3↑↑5 = 3↑(3↑↑4) ~ 10^{6.46×10^{3638334640023}}
...

A pattern emerges: except when a is 2 or when b is 2, the values of a↑↑b generally follow the rule:

If y is larger than b, x↑↑y is larger than a↑↑b.

However there are exceptions for smaller b or moderately larger a: as 12↑↑2 is larger than 3↑↑3; 81↑↑2 is larger than 4↑↑3, and similar things happen further along in the list.

But even including these smaller b or larger a cases, a more general pattern is seen, namely that increasing b by one always gives a value that is about 10 to the power of whatever we had before: 4↑↑3 ~ 1.3408×10¹⁵⁴, and 4↑↑4 ~ 10^{8.0723×10¹⁵³}. This is related to the "power tower paradox".

It is also generally true that if b is 3 or more, all of the numbers of the form a↑↑b are larger than anything of the form c↑d (with one arrow, and with "reasonably-sized" c and d). The smallest c↑d bigger than 3↑↑3 is 12↑12; in order for c↑d to be bigger than 4↑↑3 you need to go up to 81↑81, and so on.

Now let's make a similar list of a↑↑↑b examples, and showing how the a↑↑b values fit in:

2↑↑↑2 = 2↑↑2 = 2↑2 = 4
2↑↑3, 3↑↑2 through 6↑↑2
2↑↑↑3 = 2↑↑2↑↑2 = 2↑↑4 = 2↑2↑2↑2 = 2↑2↑4 = 2↑16 = 65536 = 2↑↑4
7↑↑2 through 11↑↑2
3↑↑↑2 = 3↑↑3 = 3↑27 = 7625597484987
12↑↑2, etc.; 4↑↑3 through 80↑↑3; and 3↑↑4
4↑↑↑2 = 4↑↑4 = 4↑4↑4↑4 ~ 10^{8.0723×10¹⁵³}
all the rest of the a↑↑b in the list above
5↑↑↑2 = 5↑↑5 = 5↑5↑5↑5↑5 ~ 10^{10^{1.33574×10²¹⁸⁴}}
2↑↑↑4 = 2↑↑(2↑↑(2↑↑2)) = 2↑↑(2↑↑4) = 2↑↑16, a tower of height 16 (or 10↑10↑...6.03×10¹⁹⁷²⁷ with eleven 10's at the beginning, which in Hypercalc is written "11pt6.03×10¹⁹⁷²⁷")
3↑↑↑3 = 3↑↑(3↑↑3), a tower of height 7625597484987
4↑↑↑3 = 4↑↑(4↑↑4), a tower of height 10^{8.0723×10¹⁵³}
5↑↑↑3 = 5↑↑(5↑↑5), a tower of height 10^{10^{1.33574×10²¹⁸⁴}}
6↑↑↑3 = 6↑↑(6↑↑6), a tower of height 3pt2.0692×10³⁶³⁰⁵
7↑↑↑3 = 7↑↑(7↑↑7), a tower of height 4pt3.177×10⁶⁹⁵⁹⁷⁴
8↑↑↑3 = 8↑↑(8↑↑8), a tower of height 5pt5.43×10^15151335
9↑↑↑3 = 9↑↑(9↑↑9), a tower of height 6pt4.09×10^369693099
10↑↑↑3 = 10↑↑(10↑↑10), a tower of height 7pt10^10000000000
.. 8↑↑↑3 through 13↑↑↑3
2↑↑↑5 = 2↑↑(2↑↑↑4), a tower of height 2↑↑16 ~ 11pt6.03×10¹⁹⁷²⁷
14↑↑↑3 = 14↑↑(14↑↑14), a tower of height 12pt1.2735782×10¹⁶
.. 15↑↑↑3 through 7625597484980↑↑↑3 and (perhaps 7625597484981↑↑↑3)
3↑↑↑4 = 3↑↑(3↑↑↑3), a tower of height 3↑↑↑3 ~ 7625597484984pt3638334640023.8
4↑↑↑4 = 4↑↑(4↑↑↑3), a tower of height 4↑↑↑3
.. 5↑↑↑4 through 13↑↑↑4
2↑↑↑6 = 2↑↑(2↑↑↑5), a tower of height 2↑↑↑5
.. 14↑↑↑4 through 7625597484980↑↑↑4 ...

Once again a pattern emerges: except when a is 2, the ordering is determined first by b and then a. It shouldn't be hard to believe that the same thing happens again for a↑↑↑↑b, a↑↑↑↑↑b, and so on for larger numbers of arrows. The exception when a is 2 really continues all the way, for example:

2↑↑↑↑3 = 2↑↑↑(2↑↑↑2) = 2↑↑↑4, a tower of height 16,
but 3↑↑↑↑2 = 3↑↑↑3 = 3↑↑(3↑↑3) = 3↑↑(3↑3↑3) = 3↑↑(3↑27), a tower of height 3²⁷, which is much larger

And so we have the:

General Rule for Partial Ordering of the hyper Operator:

If a, b, c, x, y and z are all "of reasonable size", then with few exceptions, when comparing hy(a,b,c) to hy(x,y,z):
   the one with more up-arrows (b versus y) is larger;
   when b = y (same number of up-arrorws), the one with the larger number on the right (c versus z) is larger;
   when b=y and c=z, the one with the larger number on the left (a versus x) is larger.

Detailed Rules for Partial Ordering of the hyper Operator:

When comparing hy(a,b,c) to hy(x,y,z):
   if a = x = 1, they are equal,
   if a is 1 and x is larger, then hy(x,y,z) is larger
   if x is 1 and a is larger, then hy(a,b,c) is larger
   if a = c = x = z = 2, they are equal,
   if y is larger than b, then hy(x,y,z) is larger
   if b is larger than y, then hy(a,b,c) is larger
   if b and y (the number of up-arrows) is the same, and if a and x are both larger than 2, then hy(a,b,c) is larger if c is larger than z, or hy(x,y,z) is larger if z is larger than c

Bowers Notation for Knuth Up-Arrows

Jonathan Bowers, who began his array notation with a 3-element array equivalent to the generalised hyper function, also introduced a notation that is popular for abbreviating a lot of Knuth up-arrows. For example, the "2↑↑↑↑↑↑↑↑↑↑↑↑3" that begins the process of describing the Graham-Rothschild Number has 12 up-arrows and is equivalent to hy(2,14,3). Bowers abbreviates this "2{12}3"; the sequence of "operators" {1}, {2}, {3} represents ↑, ↑↑, ↑↑↑, and so on. As we saw earlier, 2{12}3 is [2,3,12] using a 3-element array:

a{c}b = {a,b,c}, where c=1,2,3,4,5 etc represents adding, multiplying, exponentiation, tetration, pentation, etc. (After Bird's suggestion, I decided to let a{1}b = a^b instead of a+b to match the modified array notation, so the results are different now).

The number inside the { } can itself be an expression involving operations such as a↑b, or another use of the { } abbreviation for a lot of up-arrows.

Composed Up-Arrow Notation

When it is necessary to repeat the same number and up-arrow(s) multiple times, it is common to appreviate the repetition with a superscript. Take for example:

10↑↑10↑↑10↑↑4↑7↑↑7↑↑3↑27

and the usual convention that everything is right-associative. This can be abbreviated:

(10↑↑)³4↑(7↑↑)²3↑27

For reasons similar to the power tower paradox, any time something with fewer arrows is followed by something with more arrows, the thing with fewer arrows can be ignored, which reduces the example to:

(10↑↑)³(7↑↑)²3↑27

and (again because of the power tower paradox) we can change the 7's to 10's (or vice versa) without making a significant change to the value, so it reduces further to

(10↑↑)⁵3↑27

Usually the parentheses are left out to make it

10↑↑⁵3↑27

One then typically reduces the final part to using base 10, and this time the base cannot be ignored so it becomes

10↑↑⁵10↑12.88227387743 (approximately)

This approach is the best for actual practical use, such as in the OmegaNum library which handles such numbers with ease.

Proof Becomes Difficult

At this point we begin to encounter functions and definitions that are difficult to compare to one another, either because they are not very thoroughly worked out, or because it takes so much work to actually convert one to an equivalent value in the other's language. A popular gimmick is to use successive numbers from 1 to n, as in the hyperfactorials. Try finding a way to compare (n!)↑((n-1)!)↑↑((n-2)!)↑↑↑..., where the numbers go down as the number of arrows goes up, to something more standard like a{b}c

However, in many cases we know how to compare things because someone

has done the work to reconcile a given invented system with a rigidly specified function hierarchy.

Gödel Numbers

The Gödel number of G, Gödel's undecidable sentence, is probably around here somewhere (its value depends highly on what operators, functions, etc. are available to construct primitive-recursive statements in the formalised number theory system that the Gödel technique is applied to).

Length of Goodstein Sequences

For many years I had this topic here, but it has been moved to here, which is a lot closer to where it belongs.

Other Triadic Operators

A common trick that clearly generates faster-growing functions involves defining functions that take more than two arguments. We have seen how the hyper operator, our first triadic operator, easily covers everything all the dyadic operators can handle. This trend continues. Of course, all operators can be referred to as functions, and the dyadic operators are actually functions with two arguments.

The Steinhaus-Moser-Ackermann operators

The Ackermann function and the Steinhaus-Moser notation are both equivalent to a triadic operator that is somewhat more powerful than the hy(a,b,c) function above. The Ackermann function and Steinhaus-Moser are roughly equivalent to each other so we'll discuss them together.

Ackermann's Function

A recursive function first described by W. Ackermann in 1928 to demonstrate a property of computability in the field of mathematics, and also used more recently as an example of pathological recursive functions in computer science. There are many different versions of the function; for a complete description of each go here.

I will use the version that is the simplest to convert to the hyper operators; this is the definition used by Harvey M. Friedman[51]. In the referenced paper, the notation "A_k(n)" and "A(k,n)" are equivalent, and the latter I will write as "ack-f(k,n)" (though I used "ack-rm(k,n)" before 2000). With a and b as the two arguments, Friedman's definition is:

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

which yields to analysis as follows:

ack-f(1,b) = 2b ack-f(a,1) = 2 ack-f(2,b) = ack-f(1, ack-f(2,b-1)) = 2*ack-f(2,b-1) and by induction, ack-f(2,b) = 2^b ack-f(3,b) = ack-f(2, ack-f(3,b-1)) = 2^ack-f(3,b-1) and by induction, ack-f(3,b) = 2^{(#4#)}b ack-f(4,b) = ack-f(3, ack-f(4,b-1)) = 2^^ack-f(4,b-1) and by induction, ack-f(4,b) = 2^{(#5#)}b and by induction, ack-f(a,b) = hy(2,a+1,b)

The example value most commonly cited is ack-f(3,5), 2^④5=2↑↑5 which is 2⁶⁵⁵³⁶ ≈ 2×10¹⁹⁷²⁸, a large class-2 number. Of course, as with Steinhaus-Moser notation it is easy to transcend the classes entirely.

At this point it is tempting to try to avoid the "triadic function requirement" noted above by defining a single-variable function, such as:

a1(n) = ack-f(n,n)

While it seems that a1(n) grows "just as fast" as the ack-f() function, this is not actually true. Each value of the first argument a in ack-f{a,b) corresponds to a different finite ordinal in the fast growing hierarchy, while ack-f(n,n) eventually exceeds all of those. This is similar to how x² eventually exceeds the linear functions kx for any constant k. So a1(n) grows faster than all of the f_k(n) functions for finite k, and instead matches the ω-indexed function f_ω(n).

a1(n) is a convenient way of defining large numbers as a function of one variable, but actually computing those numbers involves the recursive definition of the function. When x>1, we have:

a1(x) = ack-f(x,x) = ack-f(x-1, ack-f(x,x-1))

The problem here is that the arguments of the two ack-f functions on the right are not equal to each other, and therefore we can't substitute from the definition of a1(n) to put the right side in terms of the a1() function. So this means you always need the two-argument version in order to actually get anywhere: the growth rate of the one-argument a1(x) depends on the existence of a two-argument function.

However, as seen above it is possible to reduce the Ackermann function to two arguments. Furthermore, it is the fastest-growing function you can get using two arguments, if the function is defined only in terms of calls to itself and a "successor function" f(x)=x+1.

First page . . . Back to page 3 . . . Forward to page 5 . . . Last page (page 11)

Japanese readers should see: 巨大数論 (from @kyodaisuu on Twitter)

If you like this you might also enjoy my numbers page.

s.30