Arrow notation

: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.Donald E. Knuth, Mathematics and Computer Science: Coping with Finiteness, Advances in Our Ability to Compute are Bringing Us Substantially Closer to Ultimate Limitations, Science 194, pp. 1235--1242, 1976.Knuth Up-Arrow Notation from Wolfram Mathworld 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{ arrows}} a \cdots a \underbrace{\uparrow \cdots \uparrow}_{n-1 \textrm{ arrows}} a}_{b \textrm{ copies of } a}\), which is solved from right to left. 
== 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: Fish, Comparison of up-arrow notation with hyper-E notation 1 July 2021
\(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\).http://snappizz.com/termination
== 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 = \underbrace{3 \uparrow 3 \uparrow \cdots \uparrow 3 \uparrow 3}_{7,625,597,484,987 \textrm{ times}}\) = Tritri
*\(10 \uparrow\uparrow\uparrow\uparrow 3 = 10 \uparrow\uparrow\uparrow 10 \uparrow\uparrow\uparrow 10\) = Super K
*\(a \uparrow^{n+1} 2 = a \uparrow^{n} a\)
== For non-integers ==
 definedFish, :ja:ユーザーブログ:Kyodaisuu/テトレーションの連続関数化 2014/06/22 for \(x > 0, n \ge 1, n \in \mathbb{N}\),
\begin{equation}
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}
\end{equation}
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}\)
Fish used this method to approximate the fast-growing hierarchy precisely, with a program published at the site.Fish. Approximation of FGH with arrow notation 2023-12-05. Here are some examples.
* \(f_3(10) \approx 10 \uparrow \uparrow 10.542750880844022\)
* \(f_3(100) \approx 10 \uparrow \uparrow 101.17592742879957\)
* \(f_4(5) \approx 10 \uparrow\uparrow\uparrow 5.718488944632594\)
* \(f_4(10) \approx 10 \uparrow\uparrow\uparrow 11.00425948512775\)
* \(f_4(100) \approx 10 \uparrow\uparrow\uparrow 101.11465471078382\)
* \(f_5(100) \approx 10 \uparrow^4 101.04713294995302\)
* \(f_{10}(10) \approx 10 \uparrow^9 11.000050551171205\)
* \(f_{100}(100) \approx 10 \uparrow^{99} 101\)
== 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
*Mixed arrow notation
*Chained arrow notation
*Irrational arrow notation
*Maksudov's transfinite arrow notation
*Ackermann number, a special case.
*Bentley's Number
*Hyper operator
*Knuth Arrow Theorem
*Katakana!'s extended arrow notation
==Sources==
fr:Notation des puissances itérées
nl:Knuth's pijlomhoognotatie
ja:矢印表記
zh:上箭號表示法
Category:Notations
Category:Functions
Category:Arrow
Category:Hyper operators