Hyperoperation

In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations in this context)¹²³ that starts with a unary operation (the successor function with n = 0). The sequence continues with the binary operations of addition (n = 1), multiplication (n = 2), and exponentiation (n = 3).^{nb 1} After that, the sequence proceeds with further binary operations extending beyond exponentiation, using right-associativity. For the operations beyond exponentiation, the nth member of this sequence is named by Reuben Goodstein after the Greek prefix of n suffixed with -ation (such as tetration (n = 4), pentation (n = 5), hexation (n = 6), etc.)⁷ and can be written using n − 2 arrows in Knuth's up-arrow notation. Each hyperoperation may be understood recursively in terms of the previous one by:

${\displaystyle a[n]b=\underbrace {a[n-1](a[n-1](a[n-1](\cdots a[n-1](a[n-1](a[n-1]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a},\quad n\geq 2}$

It may also be defined according to the recursion rule part of the definition, as in Knuth's up-arrow version of the Ackermann function:

${\displaystyle a[n]b=a[n-1]\left(a[n]\left(b-1\right)\right),\quad n\geq 1}$

This can be used to easily show numbers much larger than those which scientific notation can, such as Skewes's number and googolplexplex (e.g. ${\displaystyle 50[50]50}$ is much larger than Skewes's number and googolplexplex), but there are some numbers which even they cannot easily show, such as Graham's number and TREE(3).¹⁴

This recursion rule is common to many variants of hyperoperations.

The hyperoperation sequence is the sequence of binary operations ${\displaystyle H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}}$ defined recursively as follows: $${\displaystyle H_{n}(a,b)={\begin{cases}b+1&{\text{if }}n=0\\a&{\text{if }}n=1{\text{ and }}b=0\\0&{\text{if }}n=2{\text{ and }}b=0\\1&{\text{if }}n\geq 3{\text{ and }}b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{otherwise}}\end{cases}}.}$$ For n = 0, 1, 2, 3, this definition reproduces the basic arithmetic operations of successor (which is a unary operation), addition, multiplication, and exponentiation, respectively, as $${\displaystyle {\begin{aligned}H_{0}(a,b)&=b+1,\\H_{1}(a,b)&=a+b,\\H_{2}(a,b)&=a\times b,\\H_{3}(a,b)&=a^{b}\end{aligned}}}$$ for all nonnegative integers a and b. The hyperoperations can thus be seen as an answer to the question "what's next?" in the sequence of functions that begins successor, addition, multiplication, exponentiation. Just as integer multiplication is defined as iterated addition and integer exponentiation is defined by iterated multiplication, the next hyperoperation, tetration, is defined by iterated exponentiation; for example, ${\displaystyle H_{4}(a,3)=\operatorname {tetration} (a,3)=a^{a^{a}}}$ is a power tower of three as, and ${\displaystyle H_{4}(a,4)=\operatorname {tetration} (a,4)=a^{a^{a^{a}}}}$. Likewise the fifth hyperoperation pentation, is defined by iterated tetration, so that ${\displaystyle H_{5}(a,3)=\operatorname {tetration} (a,\operatorname {tetration} (a,a))}$.

The parameters of the hyperoperation hierarchy are sometimes referred to by their analogous exponentiation term;¹⁵ so a is the base, b is the exponent (or hyperexponent),¹³ and n is the rank (or grade).⁸ In general, ${\displaystyle H_{n}(a,b)}$ may be read as "the bth n-ation of a", so that ${\displaystyle H_{4}(7,9)}$ is read as "the 9th tetration of 7", and ${\displaystyle H_{123}(456,789)}$ is read as "the 789th 123-ation of 456".

An alternative way of writing hyperoperations is the compact notation ${\displaystyle a[n]b}$ for ${\displaystyle H_{n}(a,b)}$. In this notation, exponentiation is denoted ${\displaystyle a[3]b=a^{b}}$, tetration is denoted ${\displaystyle a[4]b}$ (so that ${\displaystyle a[4]3=a^{a^{a}}}$, pentation is denoted ${\displaystyle a[5]b}$, and so on. Hyperoperations can also be expressed using Knuth's up-arrow notation. In this notation, ${\displaystyle a\uparrow b}$ represents the exponentiation function ${\displaystyle a^{b}}$, ${\displaystyle a\uparrow \uparrow b}$ represents tetration, ${\displaystyle a\uparrow \uparrow \uparrow b}$ or ${\displaystyle a\uparrow ^{3}b}$ represents the pentation ${\displaystyle a[5]b}$, and more generally ${\displaystyle H_{n}(a,b)=a\uparrow ^{n-2}b}$ for ${\displaystyle n\geq 0.}$ Yet another alternative is Conway chained arrow notation. In this notation, one has ${\displaystyle H_{n}(a,b)=a[n]b=a\rightarrow b\rightarrow n-2}$, so that (for example) ${\displaystyle a[5]b=a\rightarrow b\rightarrow 3}$.¹⁶

Below is a list of the first seven (0th to 6th) hyperoperations (0⁰ is defined as 1).

n	Operation, Hn(a, b)	Definition	Names	Domain
0	${\displaystyle b+1}$ or ${\displaystyle a[0]b}$	${\displaystyle \underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}+1}$	Increment, successor, zeration, hyper0	Arbitrary
1	${\displaystyle a+b}$ or ${\displaystyle a[1]b}$	${\displaystyle a+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}}$	Addition, hyper1
2	${\displaystyle a\times {b}}$ or ${\displaystyle a[2]b}$	${\displaystyle \underbrace {a+a+a+\cdots +a+a+a} _{\displaystyle b{\mbox{ copies of }}a}}$	Multiplication, hyper2
3	${\displaystyle a^{b}}$ or ${\displaystyle a[3]b}$	${\displaystyle \underbrace {a\times a\times a\times \;\cdots \;\times a\times a\times a} _{\displaystyle b{\mbox{ copies of }}a}}$	Exponentiation, hyper3	b real, with some multivalued extensions to complex numbers
4	${\displaystyle ^{b}a}$ or ${\displaystyle a[4]b}$	${\displaystyle \underbrace {a^{a^{\cdot ^{\cdot ^{a}}}}} _{\displaystyle b{\mbox{ copies of }}a}}$	Tetration, hyper4	a ≥ 0 or an integer, b an integer ≥ −1 nb 2 (with some proposed extensions)
5	${\displaystyle _{b}a}$ or ${\displaystyle a[5]b}$	${\displaystyle \underbrace {a[4](a[4](a[4](\cdots [4](a[4](a[4]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}$	Pentation, hyper5	a, b integers ≥ −1 nb 2
6	${\displaystyle a[6]b}$	${\displaystyle \underbrace {a[5](a[5](a[5](\cdots [5](a[5](a[5]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}$	Hexation, hyper6

H_n(0, b) =

b + 1, when n = 0

b, when n = 1

0, when n = 2

1, when n = 3 and b = 0 ^{nb 3}

0, when n = 3 and b > 0 ^{nb 3}

1, when n > 3 and b is even (including 0)

0, when n > 3 and b is odd

H_n(1, b) =

b, when n = 2

1, when n ≥ 3

H_n(a, 0) =

0, when n = 2

1, when n = 0, or n ≥ 3

a, when n = 1

H_n(a, 1) =

2, when n = 0

a + 1, when n = 1

a, when n ≥ 2

H_n(a, a) =

H_n+1(a, 2), when n ≥ 1

H_n(a, −1) =^{nb 2}

0, when n = 0, or n ≥ 4

a − 1, when n = 1

−a, when n = 2

⁠1/a⁠ , when n = 3

H_n(2, 2) =

3, when n = 0

4, when n ≥ 1, easily demonstrable recursively.

One of the earliest discussions of hyperoperations was that of Albert Bennett in 1914, who developed some of the theory of commutative hyperoperations (see § Commutative hyperoperations below).⁸ About 12 years later, Wilhelm Ackermann defined the function ${\displaystyle \phi (a,b,n)}$, which somewhat resembles the hyperoperation sequence.¹⁷

In his 1947 paper,⁷ Reuben Goodstein introduced the specific sequence of operations that are now called hyperoperations, and also suggested the Greek names tetration, pentation, etc., for the extended operations beyond exponentiation (because they correspond to the indices 4, 5, etc.). As a three-argument function, e.g., ${\displaystyle G(n,a,b)=H_{n}(a,b)}$, the hyperoperation sequence as a whole is seen to be a version of the original Ackermann function ${\displaystyle \phi (a,b,n)}$ — recursive but not primitive recursive — as modified by Goodstein to incorporate the primitive successor function together with the other three basic operations of arithmetic (addition, multiplication, exponentiation), and to make a more seamless extension of these beyond exponentiation.

The original three-argument Ackermann function ${\displaystyle \phi }$ uses the same recursion rule as does Goodstein's version of it (i.e., the hyperoperation sequence), but differs from it in two ways. First, ${\displaystyle \phi (a,b,n)}$ defines a sequence of operations starting from addition (n = 0) rather than the successor function, then multiplication (n = 1), exponentiation (n = 2), etc. Secondly, the initial conditions for ${\displaystyle \phi }$ result in ${\displaystyle \phi (a,b,3)=G(4,a,b+1)=a[4](b+1)}$, thus differing from the hyperoperations beyond exponentiation.⁹¹⁸¹⁹ The significance of the b + 1 in the previous expression is that ${\displaystyle \phi (a,b,3)}$ = ${\displaystyle a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}}$, where b counts the number of operators (exponentiations), rather than counting the number of operands ("a"s) as does the b in ${\displaystyle a[4]b}$, and so on for the higher-level operations. (See the Ackermann function article for details.)

This is a list of notations that have been used for hyperoperations.

Name	Notation equivalent to ${\displaystyle H_{n}(a,b)}$	Comment
Knuth's up-arrow notation	${\displaystyle a\uparrow ^{n-2}b}$	Used by Knuth20 (for n ≥ 3), and found in several reference books.2122
Hilbert's notation	${\displaystyle \phi _{n}(a,b)}$	Used by David Hilbert.23
Goodstein's notation	${\displaystyle G(n,a,b)}$	Used by Reuben Goodstein.7
Original Ackermann function	${\displaystyle {\begin{matrix}\phi (a,b,n-1)\ {\text{ for }}1\leq n\leq 3\\\phi (a,b-1,n-1)\ {\text{ for }}n\geq 4\end{matrix}}}$	Used by Wilhelm Ackermann (for n ≥ 1)17
Ackermann–Péter function	${\displaystyle A(n,b-3)+3\ {\text{for }}a=2}$	This corresponds to hyperoperations for base 2 (a = 2)
Nambiar's notation	${\displaystyle a\otimes ^{n-1}b}$	Used by Nambiar (for n ≥ 1)24
Superscript notation	${\displaystyle a{}^{(n)}b}$	Used by Robert Munafo.18
Subscript notation (for lower hyperoperations)	${\displaystyle a{}_{(n)}b}$	Used for lower hyperoperations by Robert Munafo.18
Operator notation (for "extended operations")	${\displaystyle aO_{n-1}b}$	Used for lower hyperoperations by John Doner and Alfred Tarski (for n ≥ 1).25
Square bracket notation	${\displaystyle a[n]b}$	Used in many online forums; convenient for ASCII.
Conway chained arrow notation	${\displaystyle a\to b\to (n-2)}$	Used by John Horton Conway (for n ≥ 3)

In 1928, Wilhelm Ackermann defined a 3-argument function ${\displaystyle \phi (a,b,n)}$ which gradually evolved into a 2-argument function known as the Ackermann function. The original Ackermann function ${\displaystyle \phi }$ was less similar to modern hyperoperations, because his initial conditions start with ${\displaystyle \phi (a,0,n)=a}$ for all n > 2. Also he assigned addition to n = 0, multiplication to n = 1 and exponentiation to n = 2, so the initial conditions produce very different operations for tetration and beyond.

n	Operation	Comment
0	${\displaystyle F_{0}(a,b)=a+b}$
1	${\displaystyle F_{1}(a,b)=a\cdot b}$
2	${\displaystyle F_{2}(a,b)=a^{b}}$
3	${\displaystyle F_{3}(a,b)=a[4](b+1)}$	An offset form of tetration. The iteration of this operation is different than the iteration of tetration.
4	${\displaystyle F_{4}(a,b)=(x\mapsto a[4](x+1))^{b}(a)}$	Not to be confused with pentation.

Another initial condition that has been used is ${\displaystyle A(0,b)=2b+1}$ (where the base is constant ${\displaystyle a=2}$), due to Rózsa Péter, which does not form a hyperoperation hierarchy.

In 1984, C. W. Clenshaw and F. W. J. Olver began the discussion of using hyperoperations to prevent computer floating-point overflows.²⁶ Since then, many other authors²⁷²⁸²⁹ have renewed interest in the application of hyperoperations to floating-point representation. (Since H_n(a, b) are all defined for b = -1.) While discussing tetration, Clenshaw et al. assumed the initial condition ${\displaystyle F_{n}(a,0)=0}$, which makes yet another hyperoperation hierarchy. Just like in the previous variant, the fourth operation is very similar to tetration, but offset by one.

n	Operation	Comment
0	${\displaystyle F_{0}(a,b)=b+1}$
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}}$
3	${\displaystyle F_{3}(a,b)=a^{b}}$
4	${\displaystyle F_{4}(a,b)=a[4](b-1)}$	An offset form of tetration. The iteration of this operation is much different than the iteration of tetration.
5	${\displaystyle F_{5}(a,b)=\left(x\mapsto a[4](x-1)\right)^{b}(0)=0{\text{ if }}a>0}$	Not to be confused with pentation.

An alternative for these hyperoperations is obtained by evaluation from left to right.¹¹ Since

${\displaystyle {\begin{aligned}a+b&=(a+(b-1))+1\\a\cdot b&=(a\cdot (b-1))+a\\a^{b}&=\left(a^{(b-1)}\right)\cdot a\end{aligned}}}$

define (with ° or subscript)

${\displaystyle a_{(n)}b=\left(a_{(n)}(b-1)\right)_{(n-1)}a}$

with

${\displaystyle {\begin{aligned}a_{(1)}b&=a+b\\a_{(2)}0&=0\\a_{(n)}1&=a&{\text{for }}n>2\\\end{aligned}}}$

This was extended to ordinal numbers by Doner and Tarski.³⁰ They have index 0 rather than index 1 for addition. They extend the formulas to also handle each ordinal with no immediate predecessor by replacing b − 1 in the above with the supremum over all ordinals less than b, and they treat n similarly. We use Greek letters to indicate that these are ordinal numbers not simply counting numbers.

${\displaystyle {\begin{aligned}\alpha O_{0}\beta &=\alpha +\beta \\\alpha O_{\nu }\beta &=\sup \limits _{\delta <\beta ,~\mu <\nu }(\alpha O_{\nu }\delta )O_{\mu }\alpha \,.\end{aligned}}}$

With these definitions ⁠${\displaystyle O_{0}}$⁠ is addition, ⁠${\displaystyle O_{1}}$⁠ is multiplication, and ⁠${\displaystyle O_{2}}$⁠ is exponentiation. However, ⁠${\displaystyle O_{3}}$⁠ fails to form the "power tower" apparent with the corresponding (non-lower) hyperoperation.^{31nb 4} Instead,

${\displaystyle \alpha O_{3}(1+\beta )=\alpha ^{\left(\alpha ^{\beta }\right)}.}$

n	Operation	Comment
0	${\displaystyle F_{0}(a,b)=a+1}$	Increment, successor, zeration
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b}$
3	${\displaystyle F_{3}(a,b)=a^{b}}$
4	${\displaystyle F_{4}(a,b)=a^{\left(a^{(b-1)}\right)}}$	Not to be confused with tetration.
5	${\displaystyle F_{5}(a,b)=\left(x\mapsto x^{x^{(a-1)}}\right)^{b-1}(a)}$	Not to be confused with pentation. Similar to tetration.

Commutative hyperoperations were considered by Albert Bennett as early as 1914,⁸ which is possibly the earliest remark about any hyperoperation sequence. Commutative hyperoperations are defined by the recursion rule

${\displaystyle F_{n+1}(a,b)=\exp(F_{n}(\ln(a),\ln(b)))}$

which is symmetric in a and b, meaning all hyperoperations are commutative. This sequence does not contain exponentiation, and so does not form a hyperoperation hierarchy.

n	Operation	Comment
0	${\displaystyle F_{0}(a,b)=\ln \left(e^{a}+e^{b}\right)}$	Smooth maximum (LogSumExp)
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}}$	This is due to the properties of the logarithm.
3	${\displaystyle F_{3}(a,b)=a^{\ln(b)}=e^{\ln(a)\ln(b)}}$	In a finite field, this is the Diffie–Hellman key exchange operation.
4	${\displaystyle F_{4}(a,b)=e^{e^{\ln(\ln(a))\ln(\ln(b))}}}$	Not to be confused with tetration.

R. L. Goodstein⁷ used the sequence of hyperoperators to create systems of numeration for the nonnegative integers. The so-called complete hereditary representation of integer n, at level k and base b, can be expressed as follows using only the first k hyperoperators and using as digits only 0, 1, ..., b − 1, together with the base b itself:

• For 0 ≤ n ≤ b − 1, n is represented simply by the corresponding digit.
• For n > b − 1, the representation of n is found recursively, first representing n in the form

b [k] x_k [k − 1] x_{k − 1} [k - 2] ... [2] x₂ [1] x₁

where x_k, ..., x₁ are the largest integers satisfying (in turn)

b [k] x_k ≤ n

b [k] x_k [k − 1] x_{k − 1} ≤ n

...

b [k] x_k [k − 1] x_{k − 1} [k - 2] ... [2] x₂ [1] x₁ ≤ n

Any x_i exceeding b − 1 is then re-expressed in the same manner, and so on, repeating this procedure until the resulting form contains only the digits 0, 1, ..., b − 1, together with the base b.

Unnecessary parentheses can be avoided by giving higher-level operators higher precedence in the order of evaluation; thus,

level-1 representations have the form b [1] X, with X also of this form;

level-2 representations have the form b [2] X [1] Y, with X,Y also of this form;

level-3 representations have the form b [3] X [2] Y [1] Z, with X,Y,Z also of this form;

level-4 representations have the form b [4] X [3] Y [2] Z [1] W, with X,Y,Z,W also of this form;

and so on.

In this type of base-b hereditary representation, the base itself appears in the expressions, as well as "digits" from the set {0, 1, ..., b − 1}. This compares to ordinary base-2 representation when the latter is written out in terms of the base b; e.g., in ordinary base-2 notation, 6 = (110)₂ = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0, whereas the level-3 base-2 hereditary representation is 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [1] 0). The hereditary representations can be abbreviated by omitting any instances of [1] 0, [2] 1, [3] 1, [4] 1, etc.; for example, the above level-3 base-2 representation of 6 abbreviates to 2 [3] 2 [1] 2.

Examples: The unique base-2 representations of the number 266, at levels 1, 2, 3, 4, and 5 are as follows:

Level 1: 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (with 133 2s)

Level 2: 266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1)

Level 3: 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2

Level 4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2

Level 5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2

The definitions of the hyperoperation sequence can naturally be transposed to term rewriting systems (TRS).

The basic definition of the hyperoperation sequence corresponds with the reduction rules

${\displaystyle {\begin{array}{lll}{\text{(r1)}}&H(0,a,b)&\rightarrow &S(b)\\{\text{(r2)}}&H(S(0),a,0)&\rightarrow &a\\{\text{(r3)}}&H(S(S(0)),a,0)&\rightarrow &0\\{\text{(r4)}}&H(S(S(S(n))),a,0)&\rightarrow &S(0)\\{\text{(r5)}}&H(S(n),a,S(b))&\rightarrow &H(n,a,H(S(n),a,b))\end{array}}}$

To compute ${\displaystyle H_{n}(a,b)}$ one can use a stack, which initially contains the elements ${\displaystyle \langle n,a,b\rangle }$.

Then, repeatedly until no longer possible, three elements are popped and replaced according to the rules^{nb 5}

${\displaystyle {\begin{array}{lllllllll}{\text{(r1)}}&0&,&a&,&b&\rightarrow &(b+1)\\{\text{(r2)}}&1&,&a&,&0&\rightarrow &a\\{\text{(r3)}}&2&,&a&,&0&\rightarrow &0\\{\text{(r4)}}&(n+3)&,&a&,&0&\rightarrow &1\\{\text{(r5)}}&(n+1)&,&a&,&(b+1)&\rightarrow &n&,&a&,&(n+1)&,&a&,&b\end{array}}}$

Schematically, starting from ${\displaystyle \langle n,a,b\rangle }$:

WHILE stackLength <> 1
{
   POP 3 elements;
   PUSH 1 or 5 elements according to the rules r1, r2, r3, r4, r5;
}

Example

Compute ${\displaystyle H_{2}(2,2)\rightarrow _{*}4}$.³²

The reduction sequence is^{nb 5nb 6}

${\displaystyle {\underline {H(S(S(0)),S(S(0)),S(S(0)))}}}$

${\displaystyle \rightarrow _{r5}H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),S(0))}})}$

${\displaystyle \rightarrow _{r5}H(S(0),S(S(0)),H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),0)}}))}$

${\displaystyle \rightarrow _{r3}H(S(0),S(S(0)),{\underline {H(S(0),S(S(0)),0)}})}$

${\displaystyle \rightarrow _{r2}{\underline {H(S(0),S(S(0)),S(S(0)))}}}$

${\displaystyle \rightarrow _{r5}H(0,S(S(0)),{\underline {H(S(0),S(S(0)),S(0))}})}$

${\displaystyle \rightarrow _{r5}H(0,S(S(0)),H(0,S(S(0)),{\underline {H(S(0),S(S(0)),0)}}))}$

${\displaystyle \rightarrow _{r2}H(0,S(S(0)),{\underline {H(0,S(S(0)),S(S(0)))}})}$

${\displaystyle \rightarrow _{r1}{\underline {H(0,S(S(0)),S(S(S(0))))}}}$

${\displaystyle \rightarrow _{r1}S(S(S(S(0))))}$

When implemented using a stack, on input ${\displaystyle \langle 2,2,2\rangle }$

the stack configurations	represent the equations
${\displaystyle {\underline {2,2,2}}}$	${\displaystyle H_{2}(2,2)}$
${\displaystyle \rightarrow _{r5}1,2,{\underline {2,2,1}}}$	${\displaystyle =H_{1}(2,H_{2}(2,1))}$
${\displaystyle \rightarrow _{r5}1,2,1,2,{\underline {2,2,0}}}$	${\displaystyle =H_{1}(2,H_{1}(2,H_{2}(2,0)))}$
${\displaystyle \rightarrow _{r3}1,2,{\underline {1,2,0}}}$	${\displaystyle =H_{1}(2,H_{1}(2,0))}$
${\displaystyle \rightarrow _{r2}{\underline {1,2,2}}}$	${\displaystyle =H_{1}(2,2)}$
${\displaystyle \rightarrow _{r5}0,2,{\underline {1,2,1}}}$	${\displaystyle =H_{0}(2,H_{1}(2,1))}$
${\displaystyle \rightarrow _{r5}0,2,0,2,{\underline {1,2,0}}}$	${\displaystyle =H_{0}(2,H_{0}(2,H_{1}(2,0)))}$
${\displaystyle \rightarrow _{r2}0,2,{\underline {0,2,2}}}$	${\displaystyle =H_{0}(2,H_{0}(2,2))}$
${\displaystyle \rightarrow _{r1}{\underline {0,2,3}}}$	${\displaystyle =H_{0}(2,3)}$
${\displaystyle \rightarrow _{r1}4}$	${\displaystyle =4}$

The definition using iteration leads to a different set of reduction rules

${\displaystyle {\begin{array}{lll}{\text{(r6)}}&H(S(0),0,a,b)&\rightarrow &S(b)\\{\text{(r7)}}&H(S(0),S(0),a,0)&\rightarrow &a\\{\text{(r8)}}&H(S(0),S(S(0)),a,0)&\rightarrow &0\\{\text{(r9)}}&H(S(0),S(S(S(n))),a,0)&\rightarrow &S(0)\\{\text{(r10)}}&H(S(0),S(n),a,S(b))&\rightarrow &H(S(b),n,a,H(S(0),S(n),a,0))\\{\text{(r11)}}&H(S(S(x)),n,a,b)&\rightarrow &H(S(0),n,a,H(S(x),n,a,b))\end{array}}}$

As iteration is associative, instead of rule r11 one can define

${\displaystyle {\begin{array}{lll}{\text{(r12)}}&H(S(S(x)),n,a,b)&\rightarrow &H(S(x),n,a,H(S(0),n,a,b))\end{array}}}$

Like in the previous section the computation of ${\displaystyle H_{n}(a,b)=H_{n}^{1}(a,b)}$ can be implemented using a stack.

Initially the stack contains the four elements ${\displaystyle \langle 1,n,a,b\rangle }$.

Then, until termination, four elements are popped and replaced according to the rules^{nb 5}

${\displaystyle {\begin{array}{lllllllll}{\text{(r6)}}&1&,0&,a&,b&\rightarrow &(b+1)\\{\text{(r7)}}&1&,1&,a&,0&\rightarrow &a\\{\text{(r8)}}&1&,2&,a&,0&\rightarrow &0\\{\text{(r9)}}&1&,(n+3)&,a&,0&\rightarrow &1\\{\text{(r10)}}&1&,(n+1)&,a&,(b+1)&\rightarrow &(b+1)&,n&,a&,1&,(n+1)&,a&,0\\{\text{(r11)}}&(x+2)&,n&,a&,b&\rightarrow &1&,n&,a&,(x+1)&,n&,a&,b\end{array}}}$

Schematically, starting from ${\displaystyle \langle 1,n,a,b\rangle }$:

WHILE stackLength <> 1
{
   POP 4 elements;
   PUSH 1 or 7 elements according to the rules r6, r7, r8, r9, r10, r11;
}

Example

Compute ${\displaystyle H_{3}(0,3)\rightarrow _{*}0}$.

On input ${\displaystyle \langle 1,3,0,3\rangle }$ the successive stack configurations are

${\displaystyle {\begin{aligned}&{\underline {1,3,0,3}}\rightarrow _{r10}3,2,0,{\underline {1,3,0,0}}\rightarrow _{r9}{\underline {3,2,0,1}}\rightarrow _{r11}1,2,0,{\underline {2,2,0,1}}\rightarrow _{r11}1,2,0,1,2,0,{\underline {1,2,0,1}}\\&\rightarrow _{r10}1,2,0,1,2,0,1,1,0,{\underline {1,2,0,0}}\rightarrow _{r8}1,2,0,1,2,0,{\underline {1,1,0,0}}\rightarrow _{r7}1,2,0,{\underline {1,2,0,0}}\rightarrow _{r8}{\underline {1,2,0,0}}\rightarrow _{r8}0.\end{aligned}}}$

The corresponding equalities are

${\displaystyle {\begin{aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0))=H_{2}^{3}(0,1)=H_{2}(0,H_{2}^{2}(0,1))=H_{2}(0,H_{2}(0,H_{2}(0,1))\\&=H_{2}(0,H_{2}(0,H_{1}(0,H_{2}(0,0))))=H_{2}(0,H_{2}(0,H_{1}(0,0)))=H_{2}(0,H_{2}(0,0))=H_{2}(0,0)=0.\end{aligned}}}$

When reduction rule r11 is replaced by rule r12, the stack is transformed according to

${\displaystyle {\begin{array}{lllllllll}{\text{(r12)}}&(x+2)&,n&,a&,b&\rightarrow &(x+1)&,n&,a&,1&,n&,a&,b\end{array}}}$

The successive stack configurations will then be

${\displaystyle {\begin{aligned}&{\underline {1,3,0,3}}\rightarrow _{r10}3,2,0,{\underline {1,3,0,0}}\rightarrow _{r9}{\underline {3,2,0,1}}\rightarrow _{r12}2,2,0,{\underline {1,2,0,1}}\rightarrow _{r10}2,2,0,1,1,0,{\underline {1,2,0,0}}\\&\rightarrow _{r8}2,2,0,{\underline {1,1,0,0}}\rightarrow _{r7}{\underline {2,2,0,0}}\rightarrow _{r12}1,2,0,{\underline {1,2,0,0}}\rightarrow _{r8}{\underline {1,2,0,0}}\rightarrow _{r8}0\end{aligned}}}$

The corresponding equalities are

${\displaystyle {\begin{aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0))=H_{2}^{3}(0,1)=H_{2}^{2}(0,H_{2}(0,1))=H_{2}^{2}(0,H_{1}(0,H_{2}(0,0)))\\&=H_{2}^{2}(0,H_{1}(0,0))=H_{2}^{2}(0,0)=H_{2}(0,H_{2}(0,0))=H_{2}(0,0)=0\end{aligned}}}$

Remarks

• ${\displaystyle H_{3}(0,3)=0}$ is a special case, see § Special cases above.^{nb 3}
• The computation of ${\displaystyle H_{n}(a,b)}$ according to the rules {r6 - r10, r11} is heavily recursive. The culprit is the order in which iteration is executed: ${\displaystyle H^{n}(a,b)=H(a,H^{n-1}(a,b))}$. The first ${\displaystyle H}$ disappears only after the whole sequence is unfolded. For instance, ${\displaystyle H_{4}(2,4)}$ converges to 65536 in 2863311767 steps, the maximum depth of recursion^{nb 7} is 65534.
• The computation according to the rules {r6 - r10, r12} is more efficient in that respect. The implementation of iteration ${\displaystyle H^{n}(a,b)}$ as ${\displaystyle H^{n-1}(a,H(a,b))}$ mimics the repeated execution of a procedure H.^{nb 8} The depth of recursion, (n+1), matches the loop nesting. Meyer & Ritchie (1967) formalized this correspondence. The computation of ${\displaystyle H_{4}(2,4)}$ according to the rules {r6-r10, r12} also needs 2863311767 steps to converge on 65536, but the maximum depth of recursion is only 5, as tetration is the 5th operator in the hyperoperation sequence.
• The considerations above concern the recursion depth only. Either way of iterating leads to the same number of reduction steps, involving the same rules (when the rules r11 and r12 are considered "the same"). As the example shows the reduction of ${\displaystyle H_{3}(0,3)}$ converges in 9 steps: 1 X r7, 3 X r8, 1 X r9, 2 X r10, 2 X r11/r12. The modus iterandi only affects the order in which the reduction rules are applied.

See also

See also

• Large numbers
• Fast-growing hierarchy
• Veblen function

Notes

Notes

1. Sequences similar to the hyperoperation sequence have historically been referred to by many names, including: the Ackermann function¹ (3-argument), the Ackermann hierarchy,⁴ the Grzegorczyk hierarchy⁵⁶ (which is more general), Goodstein's version of the Ackermann function,⁷ operation of the nth grade,⁸ z-fold iterated exponentiation of x with y,⁹ arrow operations,¹⁰ reihenalgebra¹¹ and hyper-n.^11112213
2. Let x = a[n](−1). By the recursive formula, a[n]0 = a[n − 1](a[n](−1)) ⇒ 1 = a[n − 1]x. One solution is x = 0, because a[n − 1]0 = 1 by definition when n ≥ 4. This solution is unique because a[n − 1]b > 1 for all a > 1, b > 0 (proof by recursion).
3. For more details, see Powers of zero or Zero to the power of zero.
4. Ordinal addition is not commutative; see ordinal arithmetic for more information
5. This implements the leftmost-innermost (one-step) strategy.
6. In each step the underlined redex is rewritten.
7. The maximum depth of recursion refers to the number of levels of activation of a procedure which exist during the deepest call of the procedure.³³
8. LOOP n TIMES DO H.

References

References

1. Geisler 2003.
2. Robbins 2005.
3. Rubtsov & Romerio 2005.
4. Friedman 2001.
5. Campagnola, Moore & Félix Costa 2002.
6. Wirz 1999.
7. Goodstein 1947.
8. Bennett 1915.
9. Black 2009.
10. Littlewood 1948.
11. Müller 1993.
12. Munafo 1999a.
13. Galidakis 2003.
14. Townsend 2016.
15. Romerio 2008.
16. Conway, John Horton; Guy, Richard (1996), The Book of Numbers, Springer, p. 61, ISBN 9780387979939.
17. Ackermann 1928.
18. Munafo 1999b.
19. Cowles & Bailey 1988.
20. Knuth 1976.
21. Zwillinger 2002.
22. Weisstein 2003.
23. Hilbert 1926.
24. Nambiar 1995.
25. Doner & Tarski 1969.
26. Clenshaw & Olver 1984.
27. Holmes 1997.
28. Zimmermann 1997.
29. Pinkiewicz, Holmes & Jamil 2000.
30. Doner & Tarski 1969, Definition 1.
31. Doner & Tarski 1969, Theorem 3(iii).
32. Bezem, Klop & De Vrijer 2003.
33. Cornelius & Kirby (1975)

Bibliography

Bibliography

• Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007/BF01459088. S2CID 123431274.

• Bennett, Albert A. (December 1915). "Note on an Operation of the Third Grade". Annals of Mathematics. Second Series. 17 (2): 74–75. doi:10.2307/2007124. JSTOR 2007124.

• Bezem, Marc; Klop, Jan Willem; De Vrijer, Roel (2003). "First-order term rewriting systems". Term Rewriting Systems by "Terese". Cambridge University Press. pp. 38–39. ISBN 0-521-39115-6.

• Black, Paul E. (16 March 2009). "Ackermann's function". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology (NIST). Retrieved 29 August 2021.

• Campagnola, Manuel Lameiras; Moore, Cristopher; Félix Costa, José (December 2002). "Transfinite Ordinals in Recursive Number Theory". Journal of Complexity. 18 (4): 977–1000. doi:10.1006/jcom.2002.0655.

• Clenshaw, C.W.; Olver, F.W.J. (April 1984). "Beyond floating point". Journal of the ACM. 31 (2): 319–328. doi:10.1145/62.322429. S2CID 5132225.

• Cornelius, B.J.; Kirby, G.H. (1975). "Depth of recursion and the ackermann function". BIT Numerical Mathematics. 15 (2): 144–150. doi:10.1007/BF01932687. S2CID 120532578.

• Cowles, J.; Bailey, T. (30 September 1988). "Several Versions of Ackermann's Function". Dept. of Computer Science, University of Wyoming, Laramie, WY. Retrieved 29 August 2021.

• Doner, John; Tarski, Alfred (1969). "An extended arithmetic of ordinal numbers". Fundamenta Mathematicae. 65: 95–127. doi:10.4064/fm-65-1-95-127.

• Friedman, Harvey M. (July 2001). "Long Finite Sequences". Journal of Combinatorial Theory. Series A. 95 (1): 102–144. doi:10.1006/jcta.2000.3154.

• Galidakis, I. N. (2003). "Mathematics". Archived from the original on 20 April 2009. Retrieved 17 April 2009.

• Geisler, Daniel (2003). "What lies beyond exponentiation?". Retrieved 17 April 2009.

• Goodstein, Reuben Louis (December 1947). "Transfinite Ordinals in Recursive Number Theory" (PDF). Journal of Symbolic Logic. 12 (4): 123–129. doi:10.2307/2266486. JSTOR 2266486. S2CID 1318943.

• Hilbert, David (1926). "Über das Unendliche". Mathematische Annalen. 95: 161–190. doi:10.1007/BF01206605. S2CID 121888793.

• Holmes, W. N. (March 1997). "Composite Arithmetic: Proposal for a New Standard". Computer. 30 (3): 65–73. doi:10.1109/2.573666. Retrieved 21 April 2009.

• Knuth, Donald Ervin (December 1976). "Mathematics and Computer Science: Coping with Finiteness". Science. 194 (4271): 1235–1242. Bibcode:1976Sci...194.1235K. doi:10.1126/science.194.4271.1235. PMID 17797067. S2CID 1690489. Retrieved 21 April 2009.

• Littlewood, J. E. (July 1948). "Large Numbers". Mathematical Gazette. 32 (300): 163–171. doi:10.2307/3609933. JSTOR 3609933. S2CID 250442130.

• Meyer, Albert R.; Ritchie, Dennis MacAlistair (1967). The complexity of loop programs. ACM '67: Proceedings of the 1967 22nd national conference. doi:10.1145/800196.806014.

• Müller, Markus (1993). "Reihenalgebra" (PDF). Archived from the original (PDF) on 2 December 2013. Retrieved 6 November 2021.

• Munafo, Robert (1999a). "Versions of Ackermann's Function". Large Numbers at MROB. Retrieved 28 August 2021.

• Munafo, Robert (1999b). "Inventing New Operators and Functions". Large Numbers at MROB. Retrieved 28 August 2021.

• Nambiar, K. K. (1995). "Ackermann Functions and Transfinite Ordinals". Applied Mathematics Letters. 8 (6): 51–53. doi:10.1016/0893-9659(95)00084-4.

• Perstein, Millard H. (1 June 1962). "Algorithm 93: General order arithmetic". Communications of the ACM. 5 (6). New York City: Association for Computing Machinery: 344. doi:10.1145/367766.368160. ISSN 0001-0782.

• Pinkiewicz, T.; Holmes, N.; Jamil, T. (2000). "Design of a composite arithmetic unit for rational numbers". Proceedings of the IEEE Southeast Con 2000. 'Preparing for the New Millennium' (Cat. No.00CH37105). Proceedings of the IEEE. pp. 245–252. doi:10.1109/SECON.2000.845571. ISBN 0-7803-6312-4. S2CID 7738926.

• Robbins, A. J. (November 2005). "Home of Tetration". Archived from the original on 13 June 2015. Retrieved 17 April 2009.

• Romerio, G. F. (21 January 2008). "Hyperoperations Terminology". Tetration Forum. Retrieved 21 April 2009.

• Rubtsov, C. A.; Romerio, G. F. (December 2005). "Ackermann's Function and New Arithmetical Operation". Retrieved 17 April 2009.

• Townsend, Adam (12 May 2016). "Names for large numbers". Chalkdust magazine.

• Weisstein, Eric W. (2003). CRC concise encyclopedia of mathematics, 2nd Edition. CRC Press. pp. 127–128. ISBN 1-58488-347-2.

• Wirz, Marc (1999). "Characterizing the Grzegorczyk hierarchy by safe recursion" (PDF). Bern: Institut für Informatik und angewandte Mathematik. CiteSeerX 10.1.1.42.3374. S2CID 117417812.

• Zimmermann, R. (1997). "Computer Arithmetic: Principles, Architectures, and VLSI Design" (PDF). Lecture notes, Integrated Systems Laboratory, ETH Zürich. Archived from the original (PDF) on 17 August 2013. Retrieved 17 April 2009.

• Zwillinger, Daniel (2002). CRC standard mathematical tables and formulae, 31st Edition. CRC Press. p. 4. ISBN 1-58488-291-3.