Content deleted Content added
m tweak |
Reverted 2 edits by ARandomStringTheorist (talk): Nothing was "fixed", you simply removed maintenance tags |
||
| (412 intermediate revisions by more than 100 users not shown) | |||
Line 1:
{{short description|Means of expressing certain extremely large numbers}}{{More citations needed|date=April 2025}}
'''Conway chained arrow notation''', created by mathematician [[John Horton Conway]], is a means of expressing certain extremely [[large numbers]].<ref>John H. Conway & Richard K. Guy, The Book of Numbers, 1996, p.59-62</ref> It is simply a finite sequence of [[positive integers]] separated by rightward arrows, e.g. <math>2\to3\to4\to5\to6</math>.
As with most [[combinatorial]]
==Definition and overview==
A "Conway chain" is defined as follows:
* Any positive integer is a chain of length <math>1</math>.
* A chain of length <math>n</math>, followed by a right-arrow → and a positive integer, together form a chain of length <math>n+1</math>.
Any chain represents an integer, according to the six rules below. Two chains are said to be equivalent if they represent the same integer.
Let <math>a, b, c</math> denote positive integers and let <math>\#</math> denote the unchanged remainder of the chain. Then:
#An empty chain (or a chain of length <math>0</math>) is equal to <math>1</math>.
#The chain <math>a</math> represents the number <math>a</math>.
#The chain <math>a \rightarrow b</math> represents the number <math>a^b</math>.
#The chain <math>a \rightarrow b \rightarrow c</math> represents the number <math>a \uparrow^c b</math> (see [[Knuth's up-arrow notation]])
#The chains <math>\# \rightarrow 1</math> and <math>\# \rightarrow 1 \rightarrow a</math> represent the same number as the chain <math>\#</math>
#Else, the chain <math>\# \rightarrow (a+1) \rightarrow (b+1)</math> represents the same number as the chain <math>\# \rightarrow (\# \rightarrow a \rightarrow (b+1)) \rightarrow b</math>.
==Properties==
Let <math>X, Y</math> denote sub-chains of length 1 or greater.
#A chain evaluates to a perfect power of its first number
#Therefore, <math>1\to Y</math> is equal to <math>1</math>
#<math>X\to1\to Y</math> is equivalent to <math>X</math>
#<math>2\to2\to Y</math> is equal to <math>4</math>
#<math>X\to2\to2</math> is equivalent to <math>X\to (X)</math>
==Interpretation==
One must be careful to treat an arrow chain ''as a whole''. Arrow chains do not describe the iterated application of a binary operator. Whereas chains of other infixed symbols (e.g. 3 + 4 + 5 + 6 + 7) can often be considered in fragments (e.g. (3 + 4) + 5 + (6 + 7)) without a change of meaning (see [[associativity]]), or at least can be evaluated step by step in a prescribed order, e.g. 3<sup>4<sup>5<sup>6<sup>7</sup></sup></sup></sup> from right to left, that is not so with Conway's arrow chains.
For example:
* <math>2\rightarrow3\rightarrow2 = 2\uparrow\uparrow3 = 2^{2^2} = 2^4=16</math>
* <math>2\rightarrow(3\rightarrow2) = 2^{3^2} = 2^9 = 512</math>
* <math>(2 \rightarrow3) \rightarrow2 = (2^3)^2 =8^2=64</math>
The sixth definition rule is the core: A chain of 4 or more elements ending with 2 or higher becomes a chain of the same length with a (usually vastly) increased penultimate element. But its ''ultimate'' element is decremented, eventually permitting the fifth rule to shorten the chain. After, to paraphrase [[Donald Knuth|Knuth]], "much detail", the chain is reduced to three elements and the fourth rule terminates the recursion.
==Examples==
Examples get quite complicated quickly. Here are some small examples:
<math>n</math>
:<math>= n</math> (By rule 2)
<math>p\to q</math>
:<math>= p^q</math> (By rule 3)
:Thus, <math>3\to4 = 3^4 = 81</math>
<math>4\to3\to2</math>
:<math>= 4\uparrow\uparrow 3</math> (By rule 4)
:<math>= 4\uparrow(4\uparrow 4)</math>
:<math>= 4\uparrow256</math>
:<math>= 4^{256}</math>
:<math>= 13, 407, 807, 929, 942, 597, 099, 574, 024, 998, 205, 846, 127, 479, 365, 820, 592, 393, 377, 723, 561, 443, 721, 764, 030, 073,</math> <math>546, 976, 801, 874, 298, 166, 903, 427, 690, 031, 858, 186, 486, 050, 853, 753, 882, 811, 946, 569, 946, 433, 649, 006, 084, 096</math>
:<math>\approx 1.34 * 10 ^ {154}</math>
<math>2 \to 2 \to a</math>
:<math>= 2[\uparrow ^ a]2</math> (By rule 4)
:<math>= 4</math> (see [[Knuth's up-arrow notation|Knuth's up arrow notation]])
<math>2 \to 4 \to 3</math>
:<math>= 2 \uparrow \uparrow \uparrow 4</math> (By rule 4)
:<math>=2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2</math>
:<math>=2\uparrow\uparrow2\uparrow\uparrow4</math>
:<math>=2\uparrow\uparrow2\uparrow2\uparrow2\uparrow2</math>
:<math>=2\uparrow\uparrow2\uparrow2\uparrow4</math>
:<math>=2\uparrow\uparrow2\uparrow16</math>
:<math>=2\uparrow\uparrow 65536</math>
:<math>={^{65536}2}</math>
:<math>\approx \exp_{10}^{65533}(4.29508)</math>
:(see [[tetration]])
<math>2 \to 3 \to 2 \to 2</math>
:<math>=2 \to 3 \to (2 \to 3) \to 1</math> (By rule 6)
:<math>=2 \to 3 \to 8 \to 1</math> (By rule 3)
:<math>=2 \to 3 \to 8</math> (By rule 5)
:<math>=2 \to (2 \to 2 \to 8) \to 7</math> (By rule 6)
:<math>=2 \to 4 \to 7</math> (By rule 6)
:<math>= 2 \uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow 4</math> (By rule 4)
:= ''much larger than previous number''
<math>3 \to 2 \to 2 \to 2</math>
:<math>=3 \to 2 \to (3 \to 2) \to 1</math> (By rule 6)
:<math>= 3 \to 2 \to 9 \to 1</math> (By rule 3)
:<math>= 3 \to 2 \to 9</math> (By rule 5)
:<math>= 3 \to 3 \to 8</math> (By rule 6)
:<math>= 3 \uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow 3</math> (By rule 4)
:= ''much, much larger than previous number''
===Systematic examples===
The simplest cases with four terms (containing no integers less than 2) are:
* <math>a \to b \to 2 \to 2</math><br><math>= a \to b \to 2 \to (1 + 1)</math><br><math>= a \to b \to (a \to b) \to 1</math><br><math>= a \to b \to a^b</math><br><math>= a [a^b + 2] b</math>
: (equivalent to the last-mentioned property) The square brackets denote [[hyperoperation]].
* <math>a \to b \to 3 \to 2</math><br><math>= a \to b \to 3 \to (1 + 1)</math><br><math>= a \to b \to (a \to b \to (a \to b) \to 1) \to 1</math><br><math>= a \to b \to (a \to b \to a^b)</math><br><math>= a [a\to b \to 2 \to 2 + 2] b</math>
* <math>a \to b \to 4 \to 2</math><br><math>= a \to b \to (a \to b \to (a \to b \to a^b))</math><br><math>= a [a \to b \to 3 \to 2 + 2] b</math>
We can see a pattern here. If, for any chain <math>X</math>, we let <math>f(p) = X \to p</math> then <math>X \to p \to 2 = f^p(1)</math> (see [[Function composition|functional powers]]).
Applying this with <math>X = a \to b</math>, then <math>f(p) = a [p + 2]b</math> and <math>a \to b \to p \to 2 = a [a \to b \to (p - 1) \to 2 + 2] b = f^p(1)</math>
Thus, for example, <math>10 \to 6 \to 3\to 2 = 10 [10 [1000002] 6 + 2] 6 </math>.
Moving on:
* <math>a \to b \to 2 \to 3</math><br><math>= a \to b \to 2 \to (2 + 1)</math><br><math>= a \to b \to (a \to b) \to 2</math><br><math>= a \to b \to a^b \to 2</math><br><math>= f^{a^b}(1)</math>
Again we can generalize. When we write <math>g_q(p) = X \to p \to q</math> we have <math>X \to p \to q+1 = g_q^p(1)</math>, that is, <math>g_{q+1}(p) = g_q^p(1)</math>. In the case above, <math>g_2(p) = a \to b \to p \to 2 = f^p(1)</math> and <math>g_3(p) = g_2^p(1)</math>, so <math>a \to b \to 2 \to 3 = g_3(2) = g_2^2(1) = g_2(g_2(1)) = f^{f(1)}(1) = f^{a^b}(1)</math>
==Ackermann function==
The [[Ackermann function]] can be expressed using Conway chained arrow notation:
:<math>A(m,n) = (2 \to (n+3) \to (m-2)) -3</math> for <math>m \geq 3</math> (Since <math>A(m,n) = 2 [m] (n+3) -3</math> in [[hyperoperation]])
hence
:<math>2 \to n \to m = A(m+2,n-3)+3</math> for <math>n > 2</math>
:(<math>n = 1</math> and <math>n = 2</math> would correspond with <math>A(m,-2)=-1</math> and <math>A(m,-1)=1</math>, which could logically be added).
==Graham's number==
[[Graham's number]] cannot be expressed in Conway chained arrow notation, but it is bounded by the following:
<math>3 \rightarrow 3 \rightarrow 64 \rightarrow 2 < G < 3 \rightarrow 3 \rightarrow 65 \rightarrow 2</math>
'''Proof:''' We first define the intermediate function <math>f(n) = 3 \rightarrow 3 \rightarrow n = \begin{matrix}
3\underbrace{\uparrow \uparrow \cdots \uparrow}3 \\
\text{n arrows}
\end{matrix}</math>, which can be used to define Graham's number as <math>G = f^{64}(4)</math>. (The superscript 64 denotes a [[Function composition#Functional powers|functional power]].)
By applying rule 2 and rule 4 backwards, we simplify:
<math>f^{64}(1)</math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1))\cdots ))</math> (with 64 <math>3 \rightarrow 3</math>'s)
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3) \rightarrow 1) \cdots ) \rightarrow 1) \rightarrow 1</math>
:<math>= 3 \rightarrow 3 \rightarrow 64 \rightarrow 2;</math>
<math display="block">
\left.
\begin{matrix}
= &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdot \uparrow}3 \\
&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots \uparrow}3 \\
&\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
&3\underbrace{\uparrow \uparrow \cdots\cdot \uparrow}3 \\
&3\uparrow 3
\end{matrix}
\right\} \text{64 layers}
</math>
<math>f^{64}(4) = G;</math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 4))\cdots ))</math> (with 64 <math>3 \rightarrow 3</math>'s)
<math display="block">
\left.
\begin{matrix}
= &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdot \uparrow}3 \\
&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots \uparrow}3 \\
&\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
&3\underbrace{\uparrow \uparrow \cdots\cdot \uparrow}3 \\
&3\uparrow \uparrow \uparrow \uparrow 3
\end{matrix}
\right\} \text{64 layers}
</math>
<math>f^{64}(27)</math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 27))\cdots ))</math> (with 64 <math>3 \rightarrow 3</math>'s)
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\cdots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (3 \rightarrow 3)))\cdots ))</math> (with 65 <math>3 \rightarrow 3</math>'s)
:<math>= 3 \rightarrow 3 \rightarrow 65 \rightarrow 2</math> (computing as above).
:<math>= f^{65}(1)</math>
<math display="block">
\left.
\begin{matrix}
= &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdot \uparrow}3 \\
&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots \uparrow}3 \\
&\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
&3\underbrace{\uparrow \uparrow \cdots\cdot \uparrow}3 \\
&3\uparrow 3
\end{matrix}
\right\} \text{65 layers}
</math>
Since ''f'' is [[strictly increasing]],
:<math>f^{64}(1) < f^{64}(4) < f^{64}(27)</math>
which is the given inequality.
With chained arrows, it is very easy to specify a number much greater than Graham's number, for example, <math> 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 </math>.
<math> 3 \rightarrow 3 \rightarrow 3 \rightarrow 3</math>
:<math>= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 27 \rightarrow 2) \rightarrow 2\, </math>
:<math>= f^ {3 \rightarrow 3 \rightarrow 27 \rightarrow 2}(1) </math>
:<math>= f^{f^{27}(1)}(1) </math>
<math display="block">
\left.
\begin{matrix}
= &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdot\cdot \uparrow}3 \\
&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdot \uparrow}3 \\
&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots \uparrow}3 \\
&\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
&3\underbrace{\uparrow \uparrow \cdots\cdot \uparrow}3 \\
&3\uparrow 3
\end{matrix}
\right\}
\left.
\begin{matrix}
3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdot \uparrow}3 \\
3\underbrace{\uparrow \uparrow \cdots\cdots\cdots \uparrow}3 \\
\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
3\underbrace{\uparrow \uparrow \cdots\cdot \uparrow}3 \\
3\uparrow 3
\end{matrix}
\right\} \ 27
</math>
which is much greater than Graham's number, because the number <math>3 \rightarrow 3 \rightarrow 27 \rightarrow 2</math> <math>= f^{27}(1)</math> is much greater than <math>65</math>.
== CG function ==
Conway and Guy created a simple, single-argument function that diagonalizes over the entire notation, defined as:
<math>cg(n) = \underbrace{n\rightarrow n\rightarrow n\rightarrow \dots \rightarrow n\rightarrow n\rightarrow n}_{n}</math>
meaning the sequence is:
<math>cg(1) = 1</math>
<math>cg(2) = 2 \to 2 = 2^2 = 4</math>
<math>cg(3) = 3 \to 3 \to 3 = 3\uparrow\uparrow\uparrow3</math>
<math>cg(4) = 4 \to 4 \to 4 \to 4</math>
<math>cg(5) = 5 \to 5 \to 5 \to 5 \to 5</math>
...
This function, as one might expect, grows extraordinarily fast.
== Extension by Peter Hurford ==
Peter Hurford, a web developer and statistician, has defined an extension to this notation:
<math>a \rightarrow_b c = \underbrace{a\rightarrow_{b-1} a\rightarrow_{b-1} a\rightarrow_{b-1} \dots \rightarrow_{b-1} a\rightarrow_{b-1} a\rightarrow_{b-1} a}_{c \text{ arrows}}</math>
<math>a \rightarrow_1 b = a \rightarrow b</math>
All normal rules are unchanged otherwise.
<math>a \rightarrow_2 (a-1)</math> is already equal to the aforementioned <math>cg(a)</math>, and the function <math>f(n) = n \rightarrow_n n</math> is much faster growing than Conway and Guy's <math>cg(n)</math>.
Note that expressions like <math>a \rightarrow_b c \rightarrow_d e</math> are illegal if <math>b</math> and <math>d</math> are different numbers; a chain must have only one type of right-arrow.
However, if we modify this slightly such that:
<math>a \rightarrow_b c \rightarrow_d e = a \rightarrow_b \underbrace{c \rightarrow_{d-1} c \rightarrow_{d-1} c \rightarrow_{d-1} \dots \rightarrow_{d-1} c \rightarrow_{d-1} c \rightarrow_{d-1} c}_{e \text{ arrows}}</math>
then not only does <math>a \rightarrow_b c \rightarrow_d e</math> become legal, but the notation as a whole becomes much stronger.<ref>{{Cite news|url=http://www.greatplay.net/essays/large-numbers-part-ii-graham-and-conway|archive-url=https://archive.today/20130625000516/http://www.greatplay.net/essays/large-numbers-part-ii-graham-and-conway|url-status=dead|archive-date=2013-06-25|title=Large Numbers, Part 2: Graham and Conway - Greatplay.net|date=2013-06-25|work=archive.is|access-date=2018-02-18}}</ref>
==See also==
* [[
* [[Large numbers#Systematically creating ever-faster-increasing sequences|Systematically creating ever faster increasing sequences]]
==
{{Reflist}}
==External links==
* [http://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm Factoids > big numbers]
* [http://
*[https://docs.google.com/viewer?a=v&q=cache:gv7MebfOp6oJ:futuretg.com/FTHumanEvolutionCourse/FTFreeLearningKits/01-MA-Mathematics,%2520Economics%2520and%2520Preparation%2520for%2520University/011-MA11-UN03-10-Number%2520Theory%2520and%2520Cryptography/Additional%2520Resources/J.H.%2520Conway,%2520R.K.%2520Guy%2520-%2520The%2520Book%2520of%2520Numbers.pdf+The+Book+of+Numbers+by+J.+H.+Conway+and+R.+K.+Guy&hl=en&pid=bl&srcid=ADGEEShgWcsuShpVnS-hYtNfbwOq4TEpkeQ7YOZGVEk-omzaiEs4VKdsXFz1Su-Uh1po2QEXnmSivKhRixbQK6puTsf92WYUWuAcxyeOpXvn4JcEs-wsAJ1aF1Bk5I4JU7WCKoOUQCTL&sig=AHIEtbT5_BLlXtiF0i6dMiG6hNP8C58zKw The Book of Numbers by J. H. Conway and R. K. Guy]
{{Hyperoperations}}
{{Large numbers}}
{{DEFAULTSORT:Conway Chained Arrow Notation}}
[[Category:Mathematical notation]]
[[Category:Large numbers]]
[[Category:John Horton Conway]]
| |||