- 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, 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\).[2]
Examples
Examples of \(2 \uparrow^{n} 3\) series with colors for \(n = 1,2,3,4,5\)
- \(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\)
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
- 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...
