- For other arrow notations, see down-arrow notation and chained 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] It is defined by the following rules:
\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}
\(a \uparrow^{n} b\) is a shorthand for \(a \uparrow\uparrow\cdots\uparrow\uparrow b\) with n arrows (where n is a positive integer). So, for example, \(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 so forth. In ASCII, these are written a^b, a^^b, a^^^b, ...
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)\).
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 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\).[2]
Examples
- \(2 \uparrow 3 = 2^3 = 8\)
- \(5 \uparrow 6 = 5^6 = 15625\)
- \(10 \uparrow 100 = 10^{100} =\) googol
- \(3 \uparrow\uparrow 4 = 3 \uparrow 3 \uparrow 3 \uparrow 3 = 3 \uparrow 3 \uparrow 27 = 3^{7625597484987}\)
- \(5 \uparrow\uparrow 3 = 5 \uparrow 5 \uparrow 5 = 5^{5^5}\)
- \(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} = 7625597484987\)
- \(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 = 65536\)
- \(3 \uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow 3 \uparrow\uparrow 3 = 3 \uparrow\uparrow 7625597484987 =\) Tritri
See below nice examples of \(2 \uparrow^{n} 3\) series with colors for \(n = 1,2,3,4,5\):
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
See also
- Down-arrow notation
- Chained arrow notation
- Ackermann number, a special case.
- Bentley's Number
- Hyper operator
- Extended Up-arrow Notation
- Knuth Arrow Theorem
Sources
Bowers' extensions: expansion · multiexpansion · powerexpansion · expandotetration · explosion (multi/power/tetra) · detonation · pentonation
Saibian's extensions: hexonation · heptonation · octonation · ennonation · deconation
Tiaokhiao's extensions: megotion (multi/power/tetra) · megoexpansion (multi/power/tetra) · megoexplosion · megodetonation · gigotion (expand/explod/deto) · terotion · more...