11,689
pages

For other arrow notations, see down-arrow notation, mixed arrow notation, chained arrow notation, irrational arrow notation.

Arrow notation or up-arrow notation is a widely used notation for the hyper operators, devised by Donald Knuth in 1976 to represent large numbers.[1][2] Knuth roughly introduced $$a \uparrow b$$ as $$a^b$$ and $$a \underbrace{\uparrow \cdots \uparrow}_{n \textrm{ times}} b$$ as $$\underbrace{a \underbrace{\uparrow \cdots \uparrow}_{n-1 \textrm{ times}} \cdots a \underbrace{\uparrow \cdots \uparrow}_{n-1 \textrm{ times}} a}_{b \textrm{ times}}$$.

## Definition

We explain the precise intention of the original definition by Knuth. For any positive integers $$a$$, $$b$$, and $$n$$, $$a \uparrow^n b$$ is defined by the following recursive way:

\begin{eqnarray*} a \uparrow^n b = \left\{ \begin{array}{ll} a^b & (n = 1) \\ a & (n \geq 1, b = 1) \\ a \uparrow^{n-1} (a \uparrow^n (b-1)) & (n > 1, b > 1) \end{array} \right. \end{eqnarray*}

This notation gives a total computable function \begin{eqnarray*} \uparrow \colon \mathbb{N}_{>0}^3 & \to & \mathbb{N}_{>0} \\ (a,b,n) & \mapsto & a \uparrow^n b, \end{eqnarray*} where $$\mathbb{N}_{>0}$$ denotes the set of positive integers. Readers should be careful that some authors implicitly extend it so that $$a \uparrow^n 0 = 1$$ holds for any positive integers $$a$$ and $$n$$.

It satisfies the following relations, which also characterise the notation, for any positive integers $$a$$, $$b$$, and $$n$$:

\begin{eqnarray*} a \uparrow^1 b &=& a^b \\ a \uparrow^n 1 &=& a \\ a \uparrow^{n + 1} (b + 1) &=& a \uparrow^n (a \uparrow^{n + 1} b) \\ \end{eqnarray*}

Here, $$a \uparrow^{n} b$$ is regarded as a shorthand for $$a \uparrow\uparrow\cdots\uparrow\uparrow b$$ with $$n$$ arrows. So, for example, we have $$a \uparrow^2 b = a \uparrow\uparrow b$$. Arrow notation operators are right-associative; $$a \uparrow b \uparrow c$$ always means $$a \uparrow (b \uparrow c)$$.

Specifically, $$a \uparrow b$$ is exponentiation, $$a \uparrow\uparrow b$$ is tetration, $$a \uparrow\uparrow\uparrow b$$ is pentation, and in general $$a \uparrow^n b$$ is the (n+2)th hyper-operation. In ASCII, these are often written a^b, a^^b, a^^^b, ... or a**b, a***b, a****b as consistent with some programming languages which use a^b or a**b for exponentiation.

## Application to googology

The function $$f(n) = n \uparrow^n n$$ is a fast-growing function that eventually dominates all primitive recursive functions, and can be approximated using the fast-growing hierarchy as $$f_\omega(n)$$. This is the limit of the non-extended hyper operators, and by extension, arrow notation.

Arrow notation can relate to Hyper-E notation through the following rule: [3]

$$a \uparrow^c b = E[a]\underbrace{1\#1\#1\cdots\#b}_c$$

for positive integers a, b, c. For example,

• a↑b = E(a)b
• a↑↑b = E(a)1#b
• a↑↑↑b = E(a)1#1#b

Arrow notation has been generalized to other notations. A few notable ones are chained arrow notation, BEAF, and BAN. It has also been compared exactly with, among others, Notation Array Notation using the function (a{2, number of arrows}b).

Nathan Ho and Wojowu showed that arrow notation terminates — that is, $$a \uparrow^n b$$ exists for all $$a,b,n$$.[4][dead link]

## Examples

• $$2 \uparrow 3 = 2^3 = 8$$
• $$5 \uparrow 6 = 5^6 = 15,625$$
• $$10 \uparrow 100 = 10^{100} =$$ googol
• $$3 \uparrow\uparrow 4 = 3 \uparrow 3 \uparrow 3 \uparrow 3 = 3 \uparrow 3 \uparrow 27 = 3^{7,625,597,484,987} \approx 1.2580143*10^{3638334640024}$$
• $$5 \uparrow\uparrow 3 = 5 \uparrow 5 \uparrow 5 = 5^{5^5} \approx 1.9110126*10^{2184}$$
• $$2 \uparrow\uparrow\uparrow 2 = 2 \uparrow\uparrow 2 = 2 \uparrow 2 = 2^2 = 4$$
• $$2 \uparrow\uparrow\uparrow\uparrow 2 = 2 \uparrow\uparrow\uparrow 2 = 2 \uparrow\uparrow 2 = 2 \uparrow 2 = 2^2 = 4$$
• $$3 \uparrow\uparrow\uparrow 2 = 3 \uparrow\uparrow 3 = 3 \uparrow 3 \uparrow 3 = 3^{3^3} = 3^{27} = 7,625,597,484,987$$
• $$2 \uparrow\uparrow\uparrow 3 = 2 \uparrow\uparrow 2 \uparrow\uparrow 2 = 2 \uparrow\uparrow 4 = 2 \uparrow 2 \uparrow 2 \uparrow 2 = 2 \uparrow 2 \uparrow 4 = 2 \uparrow 16 = 65,536$$
• $$3 \uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow 3 \uparrow\uparrow 3 = 3 \uparrow\uparrow 7,625,597,484,987 =$$ Tritri
• $$a \uparrow^{n+1} 2 = a \uparrow^{n} a$$

## For non-integers

Fish defined[5] for $$x > 0, n \ge 1, n \in \mathbb{N}$$,

$$a \uparrow^n x = \begin{cases} a^x & \text{if } 0 < x \le 1 \text{ or } n=1 \\ a \uparrow^{n-1} (a \uparrow^n (x-1)) & \text{if } 1 < x, 1 < n \end{cases}$$

From this definition,

$$\begin{array}{rl} 10^{100} &= 10 \uparrow 10 \uparrow 2 = 10 \uparrow 10 \uparrow 10 \uparrow \log_{10}(2) \\ &\approx 10 \uparrow 10 \uparrow 10 \uparrow 0.301 = 10 \uparrow \uparrow 2.301 \\ 10^{10^{100}} &= 10 \uparrow 10 \uparrow 10 \uparrow 2 \approx 10 \uparrow 10 \uparrow 10 \uparrow 10 \uparrow 0.301 = 10 \uparrow \uparrow 3.301 \\ 3 \uparrow \uparrow \uparrow 3 &= 3 \uparrow \uparrow 7625597484987 \\ &\approx 10 \uparrow \uparrow 7625597484986.041 \\ &\approx 10 \uparrow \uparrow 10 \uparrow 12.88227 \\ &\approx 10 \uparrow \uparrow 10 \uparrow 10 \uparrow 10 \uparrow 0.04532 \\ &= 10 \uparrow \uparrow 10 \uparrow \uparrow 2.04532 \\ &\approx 10 \uparrow \uparrow 10 \uparrow \uparrow 10 \uparrow \uparrow 0.31076 \\ &= 10 \uparrow \uparrow \uparrow 2.31076 \\ \end{array}$$

## Turing machine code

Input form: to represent $$a \uparrow^{c} b$$, place a 1's, then c+2 ^'s, then b 1's. For example, 111^^^^^111 computes tritri.

Turing machine code

0 * * r 0
0 _ _ l 1
1 1 _ l 2
2 ^ _ l 3
2 1 1 l 4
3 ^ _ l 3
3 1 _ l 2
4 1 1 l 4
4 ^ 1 l 4'
4 _ 1 l halt
4' ^ ^ l 5
4' 1 1 r 0
5 ^ ^ l 5
5 1 1 r 6
6 ^ x r 7
6 1 y r 9
6 | ^ l 12
7 * * r 7
7 _ | r 8
7 | | r 8
8 * * r 8
8 _ ^ l 11
9 * * r 9
9 | | r 10
10 * * r 10
10 _ 1 l 11
11 * * l 11
11 x ^ r 6
11 y 1 r 6
12 * * l 12
12 ^ ^ l 12'
12' ^ ^ l 12'
12' * * l 13
12' 1 x r 14
13 * * l 13
13 ^ ^ r 20
13 _ _ r 20
13 1 x r 14
14 * * r 14
14 ^ ^ r 15
15 ^ ^ r 15
15 x x r 16
15 1 x l 12
16 x x r 16
16 1 x l 12
16 ^ x r 17
17 ^ ^ r 17
17 1 ^ r 18
18 ^ 1 r 17
18 1 1 r 18
18 _ 1 l 19
19 * * l 19
19 x x l 12
20 x 1 r 20
20 ^ ^ r 21
21 ^ ^ r 21
21 x x r 22
22 x x r 22
22 1 _ r 23
22 ^ ^ l 30
23 1 _ r 23
23 ^ ^ l 24
24 _ ^ r 25
25 ^ ^ r 25
25 1 1 l 26
26 ^ 1 r 27
27 1 1 r 27
27 _ _ l 28
28 1 _ l 29
29 * * l 29
29 _ ^ r 25
29 x 1 l 30
30 x 1 l 30
30 ^ ^ r 31
31 * * r 31
31 _ _ l 32
32 1 _ l 1