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.) ^{[5]} and can be written as using n − 2 arrows in Knuth's up-arrow notation.
Each hyperoperation may be understood recursively in terms of the previous one by:
This can be used to easily show numbers much larger than those which scientific notation can, such as Skewes' number and googolplexplex (e.g. $50[50]50$ is much larger than Skewes’ 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.
DefinitionEdit
Definition, most commonEdit
The hyperoperation sequence$H_{n}(a,b)\colon (\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}$ is the sequence of binary operations$H_{n}\colon (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}$, defined recursively as follows:
$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}}$
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
So what will be the next operation after exponentiation? We defined multiplication so that $H_{2}(a,3)=a[2]3=a\times 3=a+a+a,$ and defined exponentiation so that $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 $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.
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:
$H_{n}(a,b)=a\uparrow ^{n-2}b{\text{ for }}n\geq 0.$
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; ^{[14]} so a is the base, b is the exponent (or hyperexponent),^{[12]} and n is the rank (or grade),^{[6]} and moreover, $H_{n}(a,b)$ is read as "the bth n-ation of a", e.g. $H_{4}(7,9)$ is read as "the 9th tetration of 7", and $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 iterationEdit
Define iteration of a function f of two variables as
$H_{3}(0,3)=0$ is a special case. See below.^{[nb 3]}^{[nb 4]}
The computation of $H_{n}(a,b)$ according to the rules {r6 - r10, r11} is heavily recursive. The culprit is the order in which iteration is executed: $H^{n}(a,b)=H(a,H^{n-1}(a,b))$. The first $H$ disappears only after the whole sequence is unfolded. For instance, $H_{4}(2,4)$ converges to 65536 in 2863311767 steps, the maximum depth of recursion^{[17]} is 65534.
The computation according to the rules {r6 - r10, r12} is more efficient in that respect. The implementation of iteration $H^{n}(a,b)$ as $H^{n-1}(a,H(a,b))$ mimics the repeated execution of a procedure H.^{[18]} The depth of recursion, (n+1), matches the loop nesting. Meyer & Ritchie (1967) formalized this correspondence. The computation of $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 $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.
ExamplesEdit
Below is a list of the first seven (0th to 6th) hyperoperations (0⁰ is defined as 1).
n
Operation, H_{n}(a, b)
Definition
Names
Domain
0
$1+b$ or $a[0]b$
$1+\underbrace {1+1+1+\cdots +1+1+1} _ b{\mbox{ copies of 1}}}$
$\underbrace {a[5](a[5](a[5](\cdots [5](a[5](a[5]a))\cdots )))} _ b{\mbox{ copies of }}a}$
hyper6, hexation
a, b integers ≥ −1 ^{[nb 5]}
Special casesEdit
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]}^{[nb 4]}
0, when n = 3 and b > 0 ^{[nb 3]}^{[nb 4]}
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) =
a, when n ≥ 2
H_{n}(a, a) =
H_{n+1}(a, 2), when n ≥ 1
H_{n}(a, −1) =^{[nb 5]}
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.
HistoryEdit
One of the earliest discussions of hyperoperations was that of Albert Bennett ^{[6]} in 1914, who developed some of the theory of commutative hyperoperations (see below). About 12 years later, Wilhelm Ackermann defined the function $\phi (a,b,n)$^{[19]} which somewhat resembles the hyperoperation sequence.
In his 1947 paper,^{[5]}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., $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$\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$\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, $\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 $\phi$ result in $\phi (a,b,3)=G(4,a,b+1)=a[4](b+1)$, thus differing from the hyperoperations beyond exponentiation.^{[7]}^{[20]}^{[21]} The significance of the b + 1 in the previous expression is that $\phi (a,b,3)$ = $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 $a[4]b$, and so on for the higher-level operations. (See the Ackermann function article for details.)
NotationsEdit
This is a list of notations that have been used for hyperoperations.
In 1928, Wilhelm Ackermann defined a 3-argument function $\phi (a,b,n)$ which gradually evolved into a 2-argument function known as the Ackermann function. The original Ackermann function $\phi$ was less similar to modern hyperoperations, because his initial conditions start with $\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
$F_{0}(a,b)=a+b$
1
$F_{1}(a,b)=a\cdot b$
2
$F_{2}(a,b)=a^{b}$
3
$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.
Another initial condition that has been used is $A(0,b)=2b+1$ (where the base is constant $a=2$), due to Rózsa Péter, which does not form a hyperoperation hierarchy.
Variant starting from 0Edit
In 1984, C. W. Clenshaw and F. W. J. Olver began the discussion of using hyperoperations to prevent computer floating-point overflows.^{[28]}
Since then, many other authors ^{[29]}^{[30]}^{[31]} 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 $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
$F_{0}(a,b)=b+1$
1
$F_{1}(a,b)=a+b$
2
$F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}$
3
$F_{3}(a,b)=a^{b}$
4
$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
$F_{5}(a,b)=\left(x\mapsto a[4](x-1)\right)^{b}(0)=0{\text{ if }}a>0$
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
$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.
Numeration systems based on the hyperoperation sequenceEdit
R. L. Goodstein^{[5]} 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
where x_{k}, ..., x_{1} 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_{2} [1] x_{1} ≤ 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-bhereditary 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} = 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:
^ Sequences similar to the hyperoperation sequence have historically been referred to by many names, including: the Ackermann function^{[1]} (3-argument), the Ackermann hierarchy,^{[2]} the Grzegorczyk hierarchy^{[3]}^{[4]} (which is more general), Goodstein's version of the Ackermann function,^{[5]}operation of the nth grade,^{[6]}z-fold iterated exponentiation of x with y,^{[7]}arrow operations,^{[8]}reihenalgebra^{[9]} and hyper-n.^{[1]}^{[9]}^{[10]}^{[11]}^{[12]}
^ ^{a}^{b}^{c}^{d}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).
^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. Cornelius & Kirby (1975)
Bennett, Albert A. (Dec 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. (2009-03-16). "Ackermann's function". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology (NIST). Retrieved 2021-08-29.
Campagnola, Manuel Lameiras; Moore, Cristopher; Félix Costa, José (Dec 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. (Apr 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: 144–150. doi:10.1007/BF01932687.
Cowles, J.; Bailey, T. (1988-09-30). "Several Versions of Ackermann's Function". Dept. of Computer Science, University of Wyoming, Laramie, WY. Retrieved 2021-08-29.
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. (Jul 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 April 20, 2009. Retrieved 2009-04-17.
Geisler, Daniel (2003). "What lies beyond exponentiation?". Retrieved 2009-04-17.
Goodstein, Reuben Louis (Dec 1947). "Transfinite Ordinals in Recursive Number Theory". Journal of Symbolic Logic. 12 (4): 123–129. doi:10.2307/2266486. JSTOR 2266486.
Hilbert, David (1926). "Über das Unendliche". Mathematische Annalen. 95: 161–190. doi:10.1007/BF01206605. S2CID 121888793.
Holmes, W. N. (Mar 1997). "Composite Arithmetic: Proposal for a New Standard". Computer. 30 (3): 65–73. doi:10.1109/2.573666. Retrieved 2009-04-21.
Knuth, Donald Ervin (Dec 1976). "Mathematics and Computer Science: Coping with Finiteness". Science. 194 (4271): 1235–1242. Bibcode:1976Sci...194.1235K. doi:10.1126/science.194.4271.1235. PMID17797067. S2CID 1690489. Retrieved 2009-04-21.
Littlewood, J. E. (Jul 1948). "Large Numbers". Mathematical Gazette. 32 (300): 163–171. doi:10.2307/3609933. JSTOR 3609933.
Müller, Markus (1993). "Reihenalgebra" (PDF). Retrieved 2021-11-06.
Munafo, Robert (1999a). "Versions of Ackermann's Function". Large Numbers at MROB. Retrieved 2021-08-28.
Munafo, Robert (1999b). "Inventing New Operators and Functions". Large Numbers at MROB. Retrieved 2021-08-28.
Nambiar, K. K. (1995). "Ackermann Functions and Transfinite Ordinals". Applied Mathematics Letters. 8 (6): 51–53. doi:10.1016/0893-9659(95)00084-4.
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 2009-04-17.
Romerio, G. F. (2008-01-21). "Hyperoperations Terminology". Tetration Forum. Retrieved 2009-04-21.
Rubtsov, C. A.; Romerio, G. F. (December 2005). "Ackermann's Function and New Arithmetical Operation". Retrieved 2009-04-17.
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". CiteSeer. CiteSeerX10.1.1.42.3374. {{cite journal}}: Cite journal requires |journal= (help)
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 2013-08-17. Retrieved 2009-04-17.
Zwillinger, Daniel (2002). CRC standard mathematical tables and formulae, 31st Edition. CRC Press. p. 4. ISBN 1-58488-291-3.