↑ arvau

Wikipedia / Knuth's up-arrow notation

In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976.

In his 1947 paper, R. L. Goodstein introduced the specific sequence of operations that are now called hyperoperations. Goodstein also suggested the Greek names tetration, pentation, etc., for the extended operations beyond exponentiation. The sequence starts with a unary operation (the successor function with n = 0), and continues with the binary operations of addition (n = 1), multiplication (n = 2), exponentiation (n = 3), tetration (n = 4), etc. Various notations is another. For example:

stands for n and the square brackets used in the far right hand side expression is another notation for hyperoperations.

Introduction

The hyperoperations naturally extend the arithmetic operations of addition and multiplication as follows.

Addition by a natural number is defined as iterated incrementation:

Multiplication by a natural number is defined as iterated addition:

For example,

Exponentiation is defined as iterated multiplication, which Knuth denoted by a single up-arrow:

For example,

Tetration is defined as iterated exponentiation, which Knuth denoted by a "double arrow":

For example,

Expressions are evaluated from right to left, as the operators are defined to be right-associative.

According to this definition,

  1. etc.

This already leads to some fairly large numbers, but the hyperoperator sequence does not stop here. Pentation, defined as iterated tetration, is represented by the "triple arrow":

Hexation, defined as iterated pentation, is represented by the "quadruple arrow":

)-arrow operators. Symbolically,

Examples:

Notation

. But many environments such as programming languages and plain-text e-mail do not support superscript for such environments; the up-arrow suggests 'raising to the power of'. If the character set does not contain an up arrow, the caret (^) is used instead.

instead.

.

Writing out up-arrow notation in terms of powers

using the familiar superscript notation gives a power tower.

is a variable (or is too large), the power tower might be written using dots and a note indicating the height of the tower.

could be written with a stack of such power towers, each describing the size of the one above it.

is a variable or is too large, the stack might be written using dots and a note indicating its height.

might be written using several columns of such stacks of power towers, each column describing the number of power towers in the stack to its left:

And more generally:

(although it clearly becomes rather cumbersome).

Using tetration

for tetration allows us to make these diagrams slightly simpler while still employing a geometric representation (we could call these tetration towers).

could be represented as:

Generalizations

Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an n is useful (and also for descriptions with a variable number of arrows), or equivalently, hyperoperatorss.

Some numbers are so large that even that notation is not sufficient. The Conway chained arrow notation can then be used: a chain of three elements is equivalent with the other notations, but a chain of four or more is even more powerful.

Even faster-growing functions can be categorized using an ordinal analysis called the fast-growing hierarchy is comparable to the Ackermann function is already beyond the reach of indexed arrows but can be used to approximate Graham's number is comparable to arbitrarily-long Conway chained arrow notation.

These functions are all computable. Even faster computable functions, such as the Goodstein sequence and the TREE sequence, require the usage of large ordinals and may occur in certain combinatorical and proof-theoretic contexts. There exist functions which grow uncomputably fast, such as the Busy Beaver, which by their very nature will be completely out of reach from any up-arrow, or even any ordinal-based analysis.

Definition

Without reference to hyperoperation the up-arrow operators can be formally defined by

.

This definition uses exponentiation as the base case, and tetration as repeated exponentiation. This is equivalent to the hyperoperation sequence except it omits the three more basic operations of succession, addition and multiplication.

One can alternatively choose multiplication as the base case and iterate from there. Then exponentiation becomes repeated multiplication. The formal definition would be

.

). One could extend the notation to negative indices (n ≥ -2) in such a way as to agree with the entire hyperoperation sequence, except for the lag in the indexing:

The up-arrow operation is a right-associative operation. If ambiguity is not an issue parentheses are sometimes dropped.

Tables of values

Computing 0↑n b

results in

  1. 0, when n = 0

  2. 1, when n = 1 and b = 0

  3. 0, when n = 1 and b > 0

  4. 1, when n > 1 and b is even (including 0)

  5. 0, when n > 1 and b is odd

Computing 2↑n b

in the top row, and fill the left column with values 2. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.The table is the same as that of the Ackermann function, and an addition of 3 to all values.

Computing 3 ↑n b

in the top row, and fill the left column with values 3. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.

Computing 4  ↑n b

in the top row, and fill the left column with values 4. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.

Computing 10 ↑n b

in the top row, and fill the left column with values 10. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.For 2 ≤ b is the lexicographical order with n as the most significant number, so for the numbers of these 8 columns the numerical order is simply line-by-line. The same applies for the numbers in the 97 columns with 3 ≤ b ≤ 99, and if we start from n = 1 even for 3 ≤ b ≤ 9,999,999,999.

See also

Notes

References