Fandom

Googology Wiki

Chained arrow notation

10,529pages on
this wiki
Add New Page
Talk25 Share

Chained arrow notation is a generalization of up-arrow notation devised by J. H. Conway and R. K. Guy.[1][2]

Nathan Ho and Wojowu showed that chained arrow notation terminates — that is, its output exists for all input sequences.[3]

By Bird's Proof, chained arrow notation is roughly comparable to 4-entry arrays in Jonathan Bowers' linear array notation, but is far exceeded by arrays with 5 entries or more.

Definition Edit

  1. \(a \rightarrow b = a^{b}\)
  2. \(a \rightarrow b \rightarrow c = a\underbrace{\uparrow\ldots\uparrow}_cb\) (in which up-arrow notation is used)
  3. \(a \rightarrow\ldots\rightarrow b \rightarrow 1 = a \rightarrow\ldots\rightarrow b\) — When last entry is 1, it will be ignored.
  4. \(a \rightarrow\ldots\rightarrow b \rightarrow 1 \rightarrow c = a \rightarrow\ldots\rightarrow b\)
  5. \(a \rightarrow\ldots\rightarrow b \rightarrow (c + 1) \rightarrow (d + 1) = a \rightarrow\ldots\rightarrow b \rightarrow (a \rightarrow\ldots\rightarrow b \rightarrow c \rightarrow (d + 1) ) \rightarrow d\)

Examples Edit

Here are some small examples of chained arrow notation in action:

\(3 \rightarrow 3 \rightarrow 2 = 3\uparrow\uparrow3 = 7,625,597,484,987\)

\(3 \rightarrow 3 \rightarrow 2 \rightarrow 2\)
\(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2) \rightarrow 1\)
\(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2)\)
\(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3)\)
\(= 3 \rightarrow 3 \rightarrow (3^{3})\)
\(= 3 \rightarrow 3 \rightarrow 27\)
\(= 3 \underbrace{\uparrow\ldots\uparrow}_{27} 3 \)

CG function Edit

Using chained arrow notation, Conway and Guy created a new function similar to the Ackermann numbers that defines \(cg(n) = \underbrace{n \rightarrow n \rightarrow \ldots \rightarrow n \rightarrow n}_n\). Although it is equal to the Ackermann numbers for n from 1 to 3, \(cg(4) = 4\rightarrow 4\rightarrow 4\rightarrow 4 > \lbrace 4,4,3,2 \rbrace\), using Bird's Proof. Therefore, cg(4) is much, much larger than the famous Graham's number (in fact, the same can be said for the much smaller Conway's Tetratri).

The growth rate of this function is about \(f_{\omega^2}(n)\) in the fast-growing hierarchy. This is comparable to 4 entry linear arrays in BEAF or Bird's array notation. In Notation Array Notation, the CG function can be written as (n{3,n}n).

Peter Hurford's extensions Edit

Peter Hurford extends chained arrow notation by adding the following rule:[4]

\(a \rightarrow_c b = \underbrace{a \rightarrow_{c-1} a \rightarrow_{c-1}\ldots\rightarrow_{c-1} a \rightarrow_{c-1}a}_{b \rightarrow_{c-1}'s}\)

All normal rules remains unchanged. Thus, they apply ignoring subscripts. Notice that expressions like \(3 \rightarrow_{2} 3 \rightarrow 3\) are illegal; entire expressions must have single type of right-arrows. Also, Hurford shows that \(f(n) = n \rightarrow_n n\) is about \(f_{\omega^3}(n)\) in the fast-growing hierarchy.[5] If we allow to mix different types of arrows in the single expression, we get \(f(n) \approx f_{\omega^\omega}(n)\).

Furthermore, he defines C(n) function as follows:

\(C(a) = a \rightarrow_a a\)
\(C(a,1) = a \rightarrow_{C(a)} a\)
\(C(a,b) = a \rightarrow_{C(a,b-1)} a\)
\(C(a,1,1) = C(a,C(a,a))\)
\(C(a,b,1) = C(a,C(a,b-1,1))\)
\(C(a,1,c) = C(a,C(a,a,c-1),c-1)\)
\(C(a,b,c) = C(a,C(a,b-1,c),c-1)\)

The function \(f(n) = C(n,n,n)\) grows about as fast as \(f_{\omega^3 + \omega}(n)\) in the fast-growing hierarchy.

Sources Edit

  1. The Book of Numbers, by J. H. Conway and R. K. Guy
  2. Chained Arrow Notation
  3. http://snappizz.com/termination
  4. Hurford, Peter. Large Numbers, Part 2: Graham and Conway. Archived from the original on 2013-06-25. Retrieved 2015-03-28.
  5. Hurford, Peter. Large Numbers, Part 3: Functions and Ordinals. Archived from the original on 2013-06-25. Retrieved 2015-03-28.

See also Edit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.