Conway chained arrow notation, created by mathematician John Conway, is a means of expressing certain extremely large numbers. It is simply a finite sequence of positive integers separated by rightward arrows, e.g. 2→3→4→5→6. John Horton Conway (born December 26, 1937, Liverpool, England) is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. ... Jump to: navigation, search Large numbers are numbers that are large compared with the numbers used in everyday life. ... The integers consist of the positive natural numbers (1, 2, 3, …) the negative natural numbers (−1, −2, −3, ...) and the number zero. ...

As with most combinatorial symbologies, the definition is recursive. In this case the notation eventually resolves to being the leftmost number raised to some integer (usually enormous) power. Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria, and is in particular concerned with counting the objects in those collections (enumerative combinatorics) and with deciding whether certain optimal objects exist (extremal combinatorics). ...

Definition and overview

A conway chain (or chain for short) is defined as follows:

• Any positive integer is a chain of length 1.
• A chain of length n, followed by a right-arrow → and a positive integer, together form a chain of length n+1.

A chain Y not contained inside a larger chain in one of the forms X→Y, Y→Z, or X→Y→Z, where X and Z are also chains, is a complete chain.

If p and q are positive integers, and X stands for some chain, then the following rules apply to complete chains:

1. X→p→(q+1) is equivalent to X→(X→(...X→(X)→q...)→q)→q
   (with p copies of X, p-1 copies of q, and p-1 pairs of parentheses).
2. X→1 is equivalent to X.
3. p→q is equivalent to the exponential expression p^q.

Some observations for longer chains: In mathematics, exponentiation is a process generalized from repeated (or iterated) multiplication, in much the same way that multiplication is a process generalized from repeated addition. ...

• A chain of length 3 corresponds to Knuth's up-arrow notation and hyper operators:

• A chain of length 4 or more has a value that is, generally, too large to comprehend (consider graham's number).

In mathematics, Knuths up-arrow notation is a notation for very large integers introduced by Donald Knuth in 1976. ... The hyper operators forming the hypern family are as follows: hypern (a, b) = (See Knuths up-arrow notation and Conway chained arrow notation. ...

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. In mathematics, associativity is a property that a binary operation can have. ...

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 parentheses 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.

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. Donald Knuth Donald Ervin Knuth (born January 10, 1938) is a renowned computer scientist and professor emeritus at Stanford University. ...

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). In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ...

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, e.g. 7 = 7. This does not conflict with the rules, since combining rule 2 (backwards) with rule 3 we have 7 = 7→1 = 7¹ = 7.

p→q

= p^q (by rule 3)

Thus 3→4 = 3⁴ = 81

Also 123456→1 = 123456¹ = 123456 (by both rules 2 and 3)

1→(any arrowed expression)

= 1 since the entire expression eventually reduces to 1^number = 1. (Indeed, any chain containing a 1 can be truncated just before that 1; e.g. 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:

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)

= (a tower with 2¹⁶ = 65536 stories)

which is unimaginably large. With Knuth's arrows: .

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 (two initial 2's give 4 [ttgf])

= 2→(2→(2→2→6)→6)→6 (1)

= 2→(2→4→6)→6 (ttgf)

= 2→(2→(2→(2→2→5)→5)→5)→6 (1)

= 2→(2→(2→4→5)→5)→6 (ttgf)

= 2→(2→(2→(2→(2→2→4)→4)→4)→5)→6 (1)

= 2→(2→(2→(2→4→4)→4)→5)→6 (ttgf)

= 2→(2→(2→(2→(2→(2→2→3)→3)→3)→4) →5)→6 (1)

= 2→(2→(2→(2→(2→4→3)→3)→4)→5)→6 (ttgf)

= 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6 (previous example)

= mind bogglingly larger than previous number

With Knuth's arrows:

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:

Graham's number

Graham's number G itself can not succinctly be expressed in Conway chained arrow notation, but by defining the intermediate function , we have: Grahams number, named after Ronald Graham, is a very large number which is often described as the largest number that has ever been seriously used in a mathematical proof. ...

  (see functional powers), and  

Proof: Applying in order the definition, rule 2, and rule 1, we have: In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ...

(with 64 's)

(with 64 's)

(with 65 's)

(computing as above).

Since f is strictly increasing,

which is the given inequality. Note that

which is much greater than Graham's number.

Ackermann function

The Ackermann function may be expressed using Conway chained arrow notation: In the theory of computation, the Ackermann function or Ackermann-Peter function is a simple example of a recursive function that is not primitive recursive. ...

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).

See also

• Steinhaus-Moser notation
• Ackermann function

In mathematics, Mosers polygon notation is a means of expressing certain extremely large numbers. ... In the theory of computation, the Ackermann function or Ackermann-Peter function is a simple example of a recursive function that is not primitive recursive. ...

External

• Factoids > big numbers
• Robert Munafo's Big Numbers