Googology Wiki
Googology Wiki
10,892 Pages
Add new page
in:
Functions, Notations, Arrow, Hyper operators

Arrow notation

Edit
Share

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 > 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 so forth. 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.

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 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\).[3]

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

Sources

  1. ↑ 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.
  2. ↑ Knuth Up-Arrow Notation from Wolfram Mathworld
  3. ↑ http://snappizz.com/termination
Retrieved from "https://googology.wikia.org/wiki/Arrow_notation?oldid=313569"
Community content is available under CC-BY-SA unless otherwise noted.

Fan Feed

Explore Wikis