Knuth's up-arrow notation

The hyperoperations naturally extend the arithmetical operations of addition and multiplication as follows. Addition by a natural number is defined as iterated incrementation:

${\displaystyle {\begin{matrix}H_{1}(a,b)=a+b=&a+\underbrace {1+1+\dots +1} \\&b{\mbox{ copies of }}1\end{matrix}}}$

Multiplication by a natural number is defined as iterated addition:

${\displaystyle {\begin{matrix}H_{2}(a,b)=a\times b=&\underbrace {a+a+\dots +a} \\&b{\mbox{ copies of }}a\end{matrix}}}$

For example,

${\displaystyle {\begin{matrix}4\times 3&=&\underbrace {4+4+4} &=&12\\&&3{\mbox{ copies of }}4\end{matrix}}}$

Exponentiation for a natural power ${\displaystyle b}$ is defined as iterated multiplication, which Knuth denoted by a single up-arrow:

${\displaystyle {\begin{matrix}a\uparrow b=H_{3}(a,b)=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ copies of }}a\end{matrix}}}$

For example,

${\displaystyle {\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3{\mbox{ copies of }}4\end{matrix}}}$

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

${\displaystyle {\begin{matrix}a\uparrow \uparrow b=H_{4}(a,b)=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\&b{\mbox{ copies of }}a&&b{\mbox{ copies of }}a\end{matrix}}}$

For example,

${\displaystyle {\begin{matrix}4\uparrow \uparrow 3=&\underbrace {4^{4^{4}}} &=&\underbrace {4\uparrow (4\uparrow 4)} &=&4^{256}&\approx &1.34078079\times 10^{154}&\\&3{\mbox{ copies of }}4&&3{\mbox{ copies of }}4\end{matrix}}}$

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

According to this definition,

${\displaystyle 3\uparrow \uparrow 2=3^{3}=27}$

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}$

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580143\times 10^{3638334640024}}$

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}\approx 3^{1.2580143\times 10^{3638334640024}}}$

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”:

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=H_{5}(a,b)=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

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

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=H_{6}(a,b)=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

and so on. The general rule is that an ${\displaystyle n}$-arrow operator expands into a right-associative series of (${\displaystyle n-1}$)-arrow operators. Symbolically,

${\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } _{n}\ b=\underbrace {a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } _{n-1}\ (a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\ (\dots \ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\ a))} _{b{\text{ copies of }}a}\end{matrix}}}$

Examples:

${\displaystyle 3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}$

${\displaystyle {\begin{matrix}3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow 3\uparrow 3{\mbox{ copies of }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}{\begin{matrix}=&\underbrace {3^{3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}}}} \\&{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}}$

In expressions such as ${\displaystyle a^{b}}$, the notation for exponentiation is usually to write the exponent ${\displaystyle b}$ as a superscript to the base number ${\displaystyle a}$. But many environments — such as programming languages and plain-text e-mail — do not support superscript typesetting. People have adopted the linear notation ${\displaystyle a\uparrow b}$ 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.

The superscript notation ${\displaystyle a^{b}}$ doesn't lend itself well to generalization, which explains why Knuth chose to work from the inline notation ${\displaystyle a\uparrow b}$ instead.

${\displaystyle a\uparrow ^{n}b}$ is a shorter alternative notation for n uparrows. Thus ${\displaystyle a\uparrow ^{4}b=a\uparrow \uparrow \uparrow \uparrow b}$.

Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an n-arrow operator ${\displaystyle \uparrow ^{n}}$ is useful (and also for descriptions with a variable number of arrows), or equivalently, hyper operators.

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.

${\displaystyle {\begin{matrix}a\uparrow ^{n}b&=&a[n+2]b&=&a\to b\to n\\{\mbox{(Knuth)}}&&{\mbox{(hyperoperation)}}&&{\mbox{(Conway)}}\end{matrix}}}$

${\displaystyle 6\uparrow \uparrow 4}$ = ${\displaystyle \underbrace {6^{6^{.^{.^{.^{6}}}}}} _{4}}$, Since ${\displaystyle 6\uparrow \uparrow 4}$ = ${\displaystyle 6^{6^{6^{6}}}}$ = ${\displaystyle 6^{6^{46,656}}}$, Thus the result comes out with ${\displaystyle \underbrace {6^{6^{.^{.^{.^{6}}}}}} _{4}}$

${\displaystyle 10\uparrow (3\times 10\uparrow (3\times 10\uparrow 15)+3)}$ = ${\displaystyle \underbrace {100000...000} _{\underbrace {300000...003} _{\underbrace {300000...000} _{15}}}}$ or ${\displaystyle 10^{3\times 10^{3\times 10^{15}}+3}}$ (Petillion)

Even faster-growing functions can be categorized using an ordinal analysis called the fast-growing hierarchy. The fast-growing hierarchy uses successive function iteration and diagonalization to systematically create faster-growing functions from some base function ${\displaystyle f(x)}$. For the standard fast-growing hierarchy using ${\displaystyle f_{0}(x)=x+1}$, ${\displaystyle f_{3}(x)}$ already exhibits exponential growth, ${\displaystyle f_{4}(x)}$ is comparable to tetrational growth and is upper-bounded by a function involving the first four hyperoperators;. Then, ${\displaystyle f_{\omega }(x)}$ is comparable to the Ackermann function, ${\displaystyle f_{\omega +1}(x)}$ is already beyond the reach of indexed arrows but can be used to approximate Graham's number, and ${\displaystyle f_{\omega ^{2}}(x)}$ 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, may occur in certain combinatorical and proof-theoretic contexts. There exists functions which grow uncomputably fast, such as the Busy Beaver, whose very nature will be completely out of reach from any up-arrow, or even any ordinal-based analysis.

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

${\displaystyle a\uparrow ^{n}b={\begin{cases}a^{b},&{\text{if }}n=1;\\1,&{\text{if }}n>1{\text{ and }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\text{otherwise }}\end{cases}}}$

for all integers ${\displaystyle a,b,n}$ with ${\displaystyle a\geq 0,n\geq 1,b\geq 0}$[nb 1].

This definition uses exponentiation ${\displaystyle (a\uparrow ^{1}b=a\uparrow b=a^{b})}$ as the base case, and tetration ${\displaystyle (a\uparrow ^{2}b=a\uparrow \uparrow b)}$ 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 ${\displaystyle (a\uparrow ^{0}b=a\times b)}$ as the base case and iterate from there. Then exponentiation becomes repeated multiplication. The formal definition would be

${\displaystyle a\uparrow ^{n}b={\begin{cases}a\times b,&{\text{if }}n=0;\\1,&{\text{if }}n>0{\text{ and }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\text{otherwise }}\end{cases}}}$

for all integers ${\displaystyle a,b,n}$ with ${\displaystyle a\geq 0,n\geq 0,b\geq 0}$.

Note, however, that Knuth did not define the "nil-arrow" (${\displaystyle \uparrow ^{0}}$). 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:

${\displaystyle H_{n}(a,b)=a[n]b=a\uparrow ^{n-2}b{\text{ for }}n\geq 0.}$

The up-arrow operation is a right-associative operation, that is, ${\displaystyle a\uparrow b\uparrow c}$ is understood to be ${\displaystyle a\uparrow (b\uparrow c)}$, instead of ${\displaystyle (a\uparrow b)\uparrow c}$. If ambiguity is not an issue parentheses are sometimes dropped.

• Primitive recursion
• Hyperoperation
• Busy beaver
• Cutler's bar notation
• Tetration
• Pentation
• Ackermann function
• Graham's number
• Steinhaus–Moser notation

• Weisstein, Eric W. "Knuth Up-Arrow Notation". MathWorld.
• Robert Munafo, Large Numbers: Higher hyper operators