It may also be defined according to the recursion rule part of the definition, as in Knuth's up-arrow version of theAckermann function:
This can be used to easily show numbers much larger than those whichscientific notation can, such asSkewes's number andgoogolplexplex (e.g. is much larger than Skewes's number and googolplexplex), but there are some numbers which even they cannot easily show, such asGraham's number andTREE(3).[14]
This recursion rule is common to many variants of hyperoperations.
Thehyperoperation sequence is thesequence ofbinary operations definedrecursively as follows:Forn = 0, 1, 2, 3, this definition reproduces the basic arithmetic operations ofsuccessor (which is a unary operation),addition,multiplication, andexponentiation, respectively, asfor all nonnegative integersa andb. The hyperoperations can thus be seen as an answer to the question "what's next?" in thesequence 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, is a power tower of threeas, and. Likewise the fifth hyperoperationpentation, is defined by iterated tetration, so that.
The parameters of the hyperoperation hierarchy are sometimes referred to by their analogous exponentiation term;[15] soa is thebase,b is theexponent (orhyperexponent),[13] andn is therank (orgrade).[8] In general, may be read as "thebthn-ation ofa", so that is read as "the 9th tetration of 7", and is read as "the 789th 123-ation of 456".
An alternative way of writing hyperoperations is the compact notation for. In this notation, exponentiation is denoted, tetration is denoted (so that, pentation is denoted, and so on. Hyperoperations can also be expressed usingKnuth's up-arrow notation. In this notation, represents the exponentiation function, represents tetration, or represents the pentation, and more generally for Yet another alternative isConway chained arrow notation. In this notation, one has, so that (for example).[16]
One of the earliest discussions of hyperoperations was that of Albert Bennett in 1914, who developed some of the theory ofcommutative hyperoperations (see§ Commutative hyperoperations below).[8] About 12 years later,Wilhelm Ackermann defined the function, which somewhat resembles the hyperoperation sequence.[17]
In his 1947 paper,[7]Reuben Goodstein introduced the specific sequence of operations that are now calledhyperoperations, and also suggested the Greek namestetration, pentation, etc., for the extended operations beyond exponentiation (because they correspond to the indices 4, 5, etc.). As a three-argument function, e.g.,, the hyperoperation sequence as a whole is seen to be a version of the originalAckermann function —recursive but notprimitive recursive — as modified by Goodstein to incorporate the primitivesuccessor 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-argumentAckermann function 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, defines a sequence of operations starting from addition (n = 0) rather than thesuccessor function, then multiplication (n = 1), exponentiation (n = 2), etc. Secondly, the initial conditions for result in, thus differing from the hyperoperations beyond exponentiation.[9][18][19] The significance of theb + 1 in the previous expression is that =, whereb counts the number ofoperators (exponentiations), rather than counting the number ofoperands ("a"s) as does theb in, and so on for the higher-level operations. (See theAckermann function article for details.)
In 1928,Wilhelm Ackermann defined a 3-argument function which gradually evolved into a 2-argument function known as theAckermann function. Theoriginal Ackermann function was less similar to modern hyperoperations, because his initial conditions start with for alln > 2. Also he assigned addition ton = 0, multiplication ton = 1 and exponentiation ton = 2, so the initial conditions produce very different operations for tetration and beyond.
n
Operation
Comment
0
1
2
3
An offset form oftetration. The iteration of this operation is different than theiteration of tetration.
4
Not to be confused with pentation.
Another initial condition that has been used is (where the base is constant), due toRó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 computerfloating-point overflows.[26]Since then, many other authors[27][28][29] have renewed interest in the application of hyperoperations tofloating-point representation. (SinceHn(a,b) are all defined forb = -1.) While discussingtetration, Clenshawet al. assumed the initial condition, which makes yet another hyperoperation hierarchy. Just like in the previous variant, the fourth operation is very similar totetration, but offset by one.
n
Operation
Comment
0
1
2
3
4
An offset form oftetration. The iteration of this operation is much different than theiteration of tetration.
Commutative hyperoperations were considered by Albert Bennett as early as 1914,[8] which is possibly the earliest remark about any hyperoperation sequence. Commutative hyperoperations are defined by the recursion rule
which is symmetric ina andb, meaning all hyperoperations are commutative. This sequence does not containexponentiation, and so does not form a hyperoperation hierarchy.
R. L. Goodstein[7] used the sequence of hyperoperators to create systems of numeration for the nonnegative integers. The so-calledcomplete hereditary representation of integern, at levelk and baseb, can be expressed as follows using only the firstk hyperoperators and using as digits only 0, 1, ...,b − 1, together with the baseb itself:
For 0 ≤n ≤b − 1,n is represented simply by the corresponding digit.
Forn >b − 1, the representation ofn is found recursively, first representingn in the form
b [k]xk [k − 1]xk − 1 [k - 2] ... [2]x2 [1]x1
wherexk, ...,x1 are the largest integers satisfying (in turn)
b [k]xk ≤n
b [k]xk [k − 1]xk − 1 ≤n
...
b [k]xk [k − 1]xk − 1 [k - 2] ... [2]x2 [1]x1 ≤n
Anyxi exceedingb − 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 baseb.
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, withX also of this form;
level-2 representations have the form b [2] X [1] Y, withX,Y also of this form;
level-3 representations have the form b [3] X [2] Y [1] Z, withX,Y,Z also of this form;
level-4 representations have the form b [4] X [3] Y [2] Z [1] W, withX,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 toordinary base-2 representation when the latter is written out in terms of the baseb; 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 number266, at levels 1, 2, 3, 4, and 5 are as follows:
The computation of according to the rules {r6 - r10, r11} is heavily recursive. The culprit is the order in which iteration is executed:. The first disappears only after the whole sequence is unfolded. For instance, 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 as 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 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 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.
^ Sequences similar to thehyperoperation sequence have historically been referred to by many names, including: theAckermann function[1] (3-argument), theAckermann hierarchy,[4] theGrzegorczyk hierarchy[5][6] (which is more general),Goodstein's version of the Ackermann function,[7]operation of the nth grade,[8]z-fold iterated exponentiation of x with y,[9]arrow operations,[10]reihenalgebra[11] andhyper-n.[1][11][12][2][13]
^abcLetx =a[n](−1). By the recursive formula,a[n]0 =a[n − 1](a[n](−1)) ⇒ 1 =a[n − 1]x. One solution isx = 0, becausea[n − 1]0 = 1 by definition whenn ≥ 4. This solution is unique becausea[n − 1]b > 1 for alla > 1,b > 0 (proof by recursion).
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.JSTOR2007124.
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.ISBN0-521-39115-6.
Cowles, J.; Bailey, T. (30 September 1988)."Several Versions of Ackermann's Function". Dept. of Computer Science, University of Wyoming, Laramie, WY. Retrieved29 August 2021.