Conway's chained arrow notation is a means of expressing certain large numbers. It is simply a finite sequence of positive integers separated by rightward arrows, eg 2→3→4→5→6
Interpretation/Expansion
One must be careful to treat an arrow chain as a whole. Whereas chains of other infixed symbols (eg 3+4+5+6+7) can often be considered in fragments (eg (3+4)+5+(6+7)) without a change of meaning (see associativity), that is not so with Conway's arrow.
As with most combinatorial symbologies, the definition is recursive. Here, p and q are positive integers, and X is a chain (possibly of only one element) substituted textually.
- (1) A chain X→p→(q+1) of more than 2 elements not ending in 1 is the same as X→(X→(...X→(X)→q...)→q)→q (with p copies of X).
- (2) A chain ending in 1 is unchanged by dropping that 1. X→1 = X
- (3) 2-element chains terminate in exponentiation. p→q = pq
The last two rules do not conflict, since p→1 = p¹ = p
The first rule is the core: A chain of 3 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 second rule to shorten the chain. After, to paraphrase Knuth, "much detail," the chain is reduced to two elements and the third rule terminates the recursion.
Knuth's arrow and the hyper operators equate to 3-element chains:
- p→q→r = hyper(p,r+2,q) = p^…^q with r up-arrows.
Example
Conway's arrow doesn't help to express Graham's number G succinctly, but:
3→3→64→2 < G < 3→3→65→2
Applying the first rule above,
3→3→64→2 = 3→3→(3→3→(...3→3→(3→3)→1...)→1)→1 with 128 threes.
Applying the second rule,
3→3→64→2 = 3→3→(3→3→(...3→3→(3→3)...))
If, for convenience, we define
f(n)=3→3→n
then
3→3→64→2 = f64(1) (see
functional powers),
G=f64(4), and
3→3→65→2 = f65(1) = f64(27)
Since f is strictly increasing,
f64(1) < f64(4) < f64(27)
which is the given inequality.
Simpler examples
It is impossible give a fully worked-out interesting example. We need at least 4 elements (1-, 2-, 3-length chains being subsumed in other notations). 1s do nothing interesting, and 3→3→3→3 is much greater than Graham's number. Any chain beginning with two 2s stands for 4. That leaves very little room.
2→3→2→2
- = 2→3→(2→3)→1 (by 1)
- = 2→3→8 (2 and 3)
- = 2→(2→2→7)→7 (1)
- = 2→4→7 (supra)
- = 2→(2→(2→2→6)→6)→6 (1)
- = 2→(2→4→6)→6 (supra)
- = gonna be huge but needs a couple more steps
3→2→2→2
- = 3→2→(3→2)→1 (1)
- = 3→2→9 (2 and 3)
- = 3→3→8 (1)
- = huge