Definition, most common

The hyperoperation sequence ${\displaystyle H_{n}(a,b)\colon (\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}}$ 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)=a[n]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}}}$

(Note that for n = 0, the binary operation essentially reduces to a unary operation (successor function) by ignoring the first argument.)

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)&=1+b,\\H_{1}(a,b)&=a+b,\\H_{2}(a,b)&=a\times b,\\H_{3}(a,b)&=a\uparrow {b}=a^{b}.\end{aligned}}}$

The ${\displaystyle H_{n}}$ operations for n ≥ 3 can be written in Knuth's up-arrow notation.

So what will be the next operation after exponentiation? We defined multiplication so that ${\displaystyle H_{2}(a,3)=a[2]3=a\times 3=a+a+a,}$ and defined exponentiation so that ${\displaystyle H_{3}(a,3)=a[3]3=a\uparrow 3=a^{3}=a\times a\times a,}$ so it seems logical to define the next operation, tetration, so that ${\displaystyle H_{4}(a,3)=a[4]3=a\uparrow \uparrow 3=\operatorname {tetration} (a,3)=a^{a^{a}},}$ with a tower of three 'a'. Analogously, the pentation of (a, 3) will be tetration(a, tetration(a, a)), with three "a" in it.

${\displaystyle {\begin{aligned}H_{4}(a,b)&=a\uparrow \uparrow {b},\\H_{5}(a,b)&=a\uparrow \uparrow \uparrow {b},\\\ldots &\\H_{n}(a,b)&=a\uparrow ^{n-2}b{\text{ for }}n\geq 3,\\\ldots &\\\end{aligned}}}$

Knuth's notation could be extended to negative indices ≥ −2 in such a way as to agree with the entire hyperoperation sequence, except for the lag in the indexing:

${\displaystyle H_{n}(a,b)=a\uparrow ^{n-2}b{\text{ for }}n\geq 0.}$

The hyperoperations can thus be seen as an answer to the question "what's next" in the sequence: successor, addition, multiplication, exponentiation, and so on. Noting that

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

the relationship between basic arithmetic operations is illustrated, allowing the higher operations to be defined naturally as above. The parameters of the hyperoperation hierarchy are sometimes referred to by their analogous exponentiation term; ^[15] so a is the base, b is the exponent (or hyperexponent),^[12] and n is the rank (or grade),^[6] and moreover, ${\displaystyle H_{n}(a,b)}$ is read as "the bth n-ation of a", e.g. ${\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".

In common terms, the hyperoperations are ways of compounding numbers that increase in growth based on the iteration of the previous hyperoperation. The concepts of successor, addition, multiplication and exponentiation are all hyperoperations; the successor operation (producing x + 1 from x) is the most primitive, the addition operator specifies the number of times 1 is to be added to itself to produce a final value, multiplication specifies the number of times a number is to be added to itself, and exponentiation refers to the number of times a number is to be multiplied by itself.

Definition, using iteration

Define iteration of a function f of two variables as

${\displaystyle f^{x}(a,b)={\begin{cases}f(a,b)&{\text{if }}x=1\\f(a,f^{x-1}(a,b))&{\text{if }}x>1\end{cases}}}$

The hyperoperation sequence can be defined in terms of iteration, as follows. For all integers ${\displaystyle x,n,a,b\geq 0,}$ define

${\displaystyle {\begin{array}{lcl}H_{0}(a,b)&=&b+1\\H_{1}(a,0)&=&a\\H_{2}(a,0)&=&0\\H_{n+3}(a,0)&=&1\\H_{n+1}(a,b+1)&=&H_{n}^{b+1}(a,H_{n+1}(a,0))\\H_{n}^{x+2}(a,b)&=&H_{n}(a,H_{n}^{x+1}(a,b))\end{array}}}$

As iteration is associative, the last line can be replaced by

${\displaystyle {\begin{array}{lcl}H_{n}^{x+2}(a,b)&=&H_{n}^{x+1}(a,H_{n}(a,b))\end{array}}}$

TRS based on definition sub 1.1

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 2]}

${\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}$.^[16]

The reduction sequence is^{[nb 2][17]}

${\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}$

TRS based on definition sub 1.2

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 2]}

${\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 acoording 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 below.^{[nb 3][nb 4]}
• 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^[18] 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.^[19] 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.

Variant starting from a

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.

Variant starting from 0

In 1984, C. W. Clenshaw and F. W. J. Olver began the discussion of using hyperoperations to prevent computer floating-point overflows.^[29] Since then, many other authors ^[30][31][32] 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.

Lower hyperoperations

An alternative for these hyperoperations is obtained by evaluation from left to right.^[9] 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+1)}b=\left(a_{(n+1)}(b-1)\right)_{(n)}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,^[33] by :

${\displaystyle {\begin{aligned}\alpha O_{0}\beta &=\alpha +\beta \\\alpha O_{\gamma }\beta &=\sup \limits _{\eta <\beta ,\xi <\gamma }(\alpha O_{\gamma }\eta )O_{\xi }\alpha \end{aligned}}}$

It follows from Definition 1(i), Corollary 2(ii), and Theorem 9, that, for a ≥ 2 and b ≥ 1, that

${\displaystyle aO_{n}b=a_{(n+1)}b}$

But this suffers a kind of collapse, failing to form the "power tower" traditionally expected of hyperoperators:^{[34][nb 6]}

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

If α ≥ 2 and γ ≥ 2,^{[28][Corollary 33(i)][nb 6]}

${\displaystyle \alpha _{(1+2\gamma +1)}\beta \leq \alpha _{(1+2\gamma )}(1+3\alpha \beta ).}$

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

Commutative hyperoperations were considered by Albert Bennett as early as 1914,^[6] 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
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)}}$
4	${\displaystyle F_{4}(a,b)=e^{e^{\ln(\ln(a))\ln(\ln(b))}}}$	Not to be confused with tetration.