Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Home > Conway chained arrow notation
Conway chained arrow notation is a means of expressing certain extremely large numbers, created by mathematician John Conway. It is simply a finite sequence of positive integers separated by rightward arrows, e.g. 2→3→4→5→6.The notation is in particular relevant for chains of four or more elements. A two-element chain simply represents a power, while three-element chains correspond to Knuth's up-arrow notation and hyper operators:
- .
The Ackermann function satisfies for:
- A(m, n) = (2 → (n+3) → (m − 2)) − 3 for m>2
hence
- 2 → n → m = A(m+2,n-3) + 3 for n>2
(n=1 and n=2 would correspond with A(m,-2)=-1 and A(m,-1)=1, which could logically be added).
1 Interpretation
One must be careful to treat an arrow chain as a whole. 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. from right to left, that is not so with Conway's arrow.
For example:
- 2→3→2 = 2^^3 = 2^2^2 = 16
- 2→(3→2) = 2^3^2 = 512
- (2→3)→2 = (2^3)^2 = 64
Note that in the second case no paentheses are needed in the power notation, since right-to-left evaluation is implied, while the Conway chain needs them because otherwise the meaning is as in the first case.
2 Definition and some remarks
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, p-1 copies of q, and p-1 pairs of parentheses).
- (2) A chain ending in 1 is unchanged by dropping that 1: X→1 = X
- (3) 2-element chains represent exponentiation: p→q = pq
The last two rules do not conflict, since p→1 = pš = p
A chain of length one is equal to the number itself.
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.
Note that X→p→q is (eventually) of the form X→p.
Therefore:
- a chain starting with a is a power of a
- a chain starting with 1 is equal to 1
- a chain starting with 2→2 is (eventually) of the form 2→2→p' and therefore equal to 4 (see below)
The simplest cases with four arrows are:
- a→b→2→2 = a→b→a^b
- a→b→3→2 = a→b→(a→b→a^b)
If, for any chain X, we define
f(n) = X→n then X→p→2 = f p(1) (see
functional powers).
3 Examples
It is impossible to give a fully worked-out interesting example since at least 4 elements are required. However 1-, 2- and 3-length chains, which are subsumed in other notations, are expanded here as illustrated examples.
n
- any single integer n is just the value n, ie 7 = 7. This does not conflict with the rules since using rule 2 (backwards) then rule 3 we have 7 = 7→1 = 71 = 7.
p→q
- = pq (by rule 3)
- Thus 3→4 = 34 = 81
- Also 123456→1 = 1234561 = 123456 (by both rules 2 and 3)
1→(any arrowed expression)
- = 1 since the entire expression eventually reduces to 1number = 1
(Indeed, any chain containing a 1 can be truncated just before that 1; ie X→1→Y=X for any (embedded) chains X,Y.)
4→3→2
- = 4→(4→(4)→1)→1 (by 1) and then, working from the inner parentheses outwards,
- = 4→(4→4→1)→1 (remove redundant parentheses [rrp])
- = 4→(4→4)→1 (2)
- = 4→(256)→1 (3)
- = 4→256→1 (rrp)
- = 4→256 (2)
- = 1.34078079299e+154 approximately (3)
4→3→2 alternatively analysed
- = 4→(4→(4)→1)→1 (by 1) and then, removing trailing "→1",
- = 4→(4→(4)→1) (2)
- = 4→(4→(4)) (2)
- = 4→(256) (rrp, 3)
- = 1.34078079299e+154 approximately (rrp, 3)
With Knuth's arrows: 4^^3=4^4^4=4^256
2→2→4
- = 2→(2)→3 (by 1)
- = 2→2→3 (rrp)
- = 2→2→2 (1, rrp)
- = 2→2→1 (1, rrp)
- = 2→2 (2)
- = 4 (3) (In fact any chain beginning with two 2s stands for 4.)
2→4→3
- = 2→(2→(2→(2)→2)→2)→2 (by 1) The four copies of X (which is 2 here) are in bold to distinguish them from the 2 which is q)
- = 2→(2→(2→2→2)→2)→2 (rrp)
- = 2→(2→(4)→2)→2 (previous example)
- = 2→(2→4→2)→2 (rrp) (expression expanded in next equation shown in bold on both lines)
- = 2→(2→(2→(2→(2)→1)→1)→1)→2 (1)
- = 2→(2→(2→(2→2→1)→1)→1)→2 (rrp)
- = 2→(2→(2→(2→2)))→2 (2 repeatedly)
- = 2→(2→(2→(4)))→2 (3)
- = 2→(2→(16))→2 (3)
- = 2→65536→2 (3,rrp)
- = 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1 (1) with 65535 sets of parentheses
- = 2→(2→(2→(...2→(2→(2))...)))) (2 repeatedly)
- = 2→(2→(2→(...2→(4))...)))) (3)
- = 2→(2→(2→(...16...)))) (3)
- = 2→(very large power of 2) (3 repeatedly)
- = very very big number
With Knuth's arrows: 2^^^4=2^^2^^2^^2=2^^2^^2^2=2^^2^^4=2^^2^2^2^2=2^^65536
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)
- = 2→(2→(2→4→5)→5)→6 (supra)
- = 2→(2→(2→(2→4→4)→4)→5)→6 (supra)
- = 2→(2→(2→(2→(2→4→3)→3)→4)→5)→6 (supra)
- = 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6
- = mind bogglingly larger than previous number
With Knuth's arrows: 2^^^^^^2^^^^^2^^^^2^^^2^^65536.
3→2→2→2
- = 3→2→(3→2)→1 (1)
- = 3→2→9 (2 and 3)
- = 3→3→8 (1)
- = huge
With Knuth's arrows: 3^^^^^^^3^^^^^^3^^^^^3^^^^3^^^3^^7.6e12.
Read more »