In mathematics, the hyperoperation sequence[nb 1] is an infinite sequence of arithmetic operations (called hyperoperations in this context)[1][11][13] 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).
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.)
Each hyperoperation may be understood recursively in terms of the previous one by: 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: 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.
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: 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.
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,
define As iteration is associative, the last line can be replaced by 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 To compute
Then, repeatedly until no longer possible, three elements are popped and replaced according to the rules[nb 2] Schematically, starting from
[16] The reduction sequence is[nb 2][17] When implemented using a stack, on input
The definition using iteration leads to a different set of reduction rules As iteration is associative, instead of rule r11 one can define Like in the previous section the computation of
Then, until termination, four elements are popped and replaced according to the rules[nb 2] Schematically, starting from
[20] 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.).
, the hyperoperation sequence as a whole is seen to be a version of the original Ackermann function
— 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.
uses the same recursion rule as does Goodstein's version of it (i.e., the hyperoperation sequence), but differs from it in two ways.
defines a sequence of operations starting from addition (n = 0) rather than the successor function, then multiplication (n = 1), exponentiation (n = 2), etc.
was less similar to modern hyperoperations, because his initial conditions start with
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.
), 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.
[29] Since then, many other authors [30][31][32] have renewed interest in the application of hyperoperations to floating-point representation.
While discussing tetration, Clenshaw et al. assumed the initial condition
Just like in the previous variant, the fourth operation is very similar to tetration, but offset by one.
[9] Since define (with ° or subscript) with This was extended to ordinal numbers by Doner and Tarski,[33] by : It follows from Definition 1(i), Corollary 2(ii), and Theorem 9, that, for a ≥ 2 and b ≥ 1, that [original research?]
But this suffers a kind of collapse, failing to form the "power tower" traditionally expected of hyperoperators:[34][nb 6] If α ≥ 2 and γ ≥ 2,[28][Corollary 33(i)][nb 6] Commutative hyperoperations were considered by Albert Bennett as early as 1914,[6] which is possibly the earliest remark about any hyperoperation sequence.
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: Unnecessary parentheses can be avoided by giving higher-level operators higher precedence in the order of evaluation; thus, 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}.