Hyperoperation

In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations that starts with a unary operation. The sequence continues with the binary operations of addition, multiplication, and exponentiation.
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, pentation, hexation 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:
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, but there are some numbers which even they cannot easily show, such as Graham's number and TREE.
This recursion rule is common to many variants of hyperoperations.

Definition

Definition, most common

The hyperoperation sequence is the sequence of binary operations, defined recursively as follows:
For n = 0, 1, 2, 3, this definition reproduces the basic arithmetic operations of successor, addition, multiplication, and exponentiation, respectively, as
The 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 and defined exponentiation so that so it seems logical to define the next operation, tetration, so that with a tower of three 'a'. Analogously, the pentation of will be tetration, 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:
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
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; so a is the base, b is the exponent, and n is the rank, and moreover, is read as "the bth n-ation of a", e.g. is read as "the 9th tetration of 7", and 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 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 of two variables as
The hyperoperation sequence can be defined in terms of iteration, as follows. For all integers define
As iteration is associative, the last line can be replaced by

Computation

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

TRS based on definition sub 1.1

The basic definition of the hyperoperation sequence corresponds with the reduction rules
To compute one can use a stack, which initially contains the elements.
Then, repeatedly until no longer possible, three elements are popped and replaced according to the rules
Schematically, starting from :
WHILE stackLength <> 1
Example
Compute.
The reduction sequence is
When implemented using a stack, on input

TRS based on definition sub 1.2

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 can be implemented using a stack.
Initially the stack contains the four elements.
Then, until termination, four elements are popped and replaced according to the rules
Schematically, starting from :
WHILE stackLength <> 1
Example
Compute.
On input the successive stack configurations are
The corresponding equalities are
When reduction rule r11 is replaced by rule r12, the stack is transformed according to
The successive stack configurations will then be
The corresponding equalities are
Remarks

is a special case. See [|below].
The computation of according to the rules 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 is 65534.
The computation according to the rules is more efficient in that respect. The implementation of iteration as mimics the repeated execution of a procedure H. The depth of recursion,, matches the loop nesting. formalized this correspondence. The computation of according to the rules 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. 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.
Examples

Below is a list of the first seven hyperoperations.

n	Operation, H_n	Definition	Names	Domain
0	or		Increment, successor, zeration, hyper0	Arbitrary
1	or		Addition, hyper1	Arbitrary
2	or		Multiplication, hyper2	Arbitrary
3	or		Exponentiation, hyper3	b real, with some multivalued extensions to complex numbers
4	or		Tetration, hyper4	a ≥ 0 or an integer, b an integer ≥ −1
5	or		Pentation, hyper5	a, b integers ≥ −1
6			Hexation, hyper6	a, b integers ≥ −1

Special cases

H_n =
H_n =
H_n =
H_n =
H_n =
H_n =
H_n =

History

One of the earliest discussions of hyperoperations was that of Albert Bennett in 1914, who developed some of the theory of commutative hyperoperations. About 12 years later, Wilhelm Ackermann defined the function, 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. As a three-argument function, e.g.,, 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, and to make a more seamless extension of these beyond exponentiation.
The original three-argument Ackermann function uses the same recursion rule as does Goodstein's version of it, but differs from it in two ways. First, defines a sequence of operations starting from addition rather than the successor function, then multiplication, exponentiation, etc. Secondly, the initial conditions for result in, thus differing from the hyperoperations beyond exponentiation. The significance of the b + 1 in the previous expression is that =, where b counts the number of operators, rather than counting the number of operands as does the b in, and so on for the higher-level operations.

Notations

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

Name	Notation equivalent to	Comment
Knuth's up-arrow notation		Used by Knuth, and found in several reference books.
Hilbert's notation		Used by David Hilbert.
Goodstein's notation		Used by Reuben Goodstein.
Original Ackermann function		Used by Wilhelm Ackermann
Ackermann–Péter function		This corresponds to hyperoperations for base 2
Nambiar's notation		Used by Nambiar
Superscript notation		Used by Robert Munafo.
Subscript notation		Used for lower hyperoperations by Robert Munafo.
Operator notation		Used for lower hyperoperations by John Doner and Alfred Tarski.
Square bracket notation		Used in many online forums; convenient for ASCII.
Conway chained arrow notation		Used by John Horton Conway