Conway chained arrow notation, created by mathematician John Horton Conway

John Horton Conway

John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...

, is a means of expressing certain extremely large numbers

Large numbers

This article is about large numbers in the sense of numbers that are significantly larger than those ordinarily used in everyday life, for instance in simple counting or in monetary transactions...

. It is simply a finite sequence of positive integers separated by rightward arrows, e.g. 2 → 3 → 4 → 5 → 6.

As with most combinatorial symbologies, the definition is recursive

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

. In this case the notation eventually resolves to being the leftmost number raised to some (usually enormous) integer power.

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 .

Any chain represents an integer, according to the four rules below. Two chains are said to be equivalent if they represent the same integer.

If p and q are positive integers, and X is a subchain, then:

1. The chain represents the number p.
2. represents the exponential
   Exponentiation
   Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
   
    expression .
3. is equivalent to .
4. is equivalent to
   (with p copies of X, p − 1 copies of q, and p − 1 pairs of parentheses; applies for q > 0).

Note that the last rule can be restated recursively to avoid the ellipses

Ellipsis

Ellipsis is a series of marks that usually indicate an intentional omission of a word, sentence or whole section from the original text being quoted. An ellipsis can also be used to indicate an unfinished thought or, at the end of a sentence, a trailing off into silence...

:

4a.

4b.

Properties

1. A chain of length 3 corresponds to Knuth's up-arrow notation
   Knuth's up-arrow notation
   In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976. It is closely related to the Ackermann function and especially to the hyperoperation sequence. The idea is based on the fact that multiplication can be viewed as iterated...
   
    and hyper operators:
   
   1. a chain X → Y is of the form X → p; hence:
   2. a chain starting with a is a power of a
   3. a chain 1 → Y is equal to 1
   4. a chain X → 1 → Y is equal to X
   5. a chain 2 → 2 → Y is equal to 4
   6. a chain X → 2 → 2 is equal to X → (X) (chain X with its value concatenated to it)
   
   

   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
   Associativity
   In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
   
   ), or at least can be evaluated step by step in a prescribed order, e.g. 2³⁴ from right to left, that is not so with Conway's arrow.
   
   For example:
   • 
   • 
   • 
   
   
   The fourth 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 third rule to shorten the chain. After, to paraphrase Knuth
   Donald Knuth
   Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
   
   , "much detail", the chain is reduced to two elements and the second rule terminates the recursion.
   

   Examples

   Examples get quite complicated quickly, here are small examples:
   
   n

   = n (by rule 1)

   
   
   p→q

   = p^q (by rule 2)

   Thus 3→4 = 3⁴ = 81

   
   
   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 4) and then, working from the inner parentheses outwards,

   = 4→(4→4→1)→1 (remove redundant parentheses [rrp])

   = 4→(4→4)→1 (3)

   = 4→(256)→1 (2)

   = 4→256→1 (rrp)

   = 4→256 (3)

   = 4²⁵⁶ (2)

   = 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 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 exactly ≈ 1.34078079299 × 10¹⁵⁴

   
   
   With Knuth's arrows:
   
   2→2→4

   = 2→(2)→3 (by 4)

   = 2→2→3 (rrp)

   = 2→2→2 (4, rrp)

   = 2→2→1 (4, rrp)

   = 2→2 (3)

   = 4 (2) (In fact any chain beginning with two 2s stands for 4.)

   
   
   2→4→3

   = 2→(2→(2→(2)→2)→2)→2 (by 4) The four copies of X (which is 2 here) are in bold to distinguish them from the three copies of q (which is also 2)

   = 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 (4)

   = 2→(2→(2→(2→2→1)→1)→1)→2 (rrp)

   = 2→(2→(2→(2→2)))→2 (3 repeatedly)

   = 2→(2→(2→(4)))→2 (2)

   = 2→(2→(16))→2 (2)

   = 2→65536→2 (2,rrp)

   = 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1 (4) with 65535 sets of parentheses

   = 2→(2→(2→(...2→(2→(2))...)))) (3 repeatedly)

   = 2→(2→(2→(...2→(4))...)))) (2)

   = 2→(2→(2→(...16...)))) (2)

   = (a tower with 2¹⁶ = 65536 stories) = ⁶⁵⁵³⁶2 (See Tetration

   Tetration

   In mathematics, tetration is an iterated exponential and is the next hyper operator after exponentiation. The word tetration was coined by English mathematician Reuben Louis Goodstein from tetra- and iteration. Tetration is used for the notation of very large numbers...

   
   )

   
   
   With Knuth's arrows: .
   
   2→3→2→2

   = 2→3→(2→3)→1 (by 4)

   = 2→3→8 (2 and 3) With Knuth's arrows: 2 ↑⁸ 3 (prop1)

   = 2→(2→2→7)→7 (1)

   = 2→4→7 (two initial 2's give 4 [prop6]) With Knuth's arrows: 2 ↑⁷ 4 (prop1)

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

   = 2→(2→4→6)→6 (prop6)

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

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

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

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

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

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

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

   = much larger than previous number

   
   
   With Knuth's arrows:
   
   3→2→2→2

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

   = 3→2→9 (2 and 3)

   = 3→3→8 (4)

   
   
   With Knuth's arrows: .
   

   Systematic examples

   The simplest cases with four terms (containing no integers less than 2) are:
   • 

   (also following from the last-mentioned property)

   • 
     
   • 

   
   
   We can see a pattern here. If, for any chain X, we let then (see
   functional powers
   Function composition
   In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
   
   ).
   
   Applying this with , then and
   
   Thus, for example, .
   
   Moving on:
   • 
   
   
   Again we can generalize. When we write we have , that is, . In the case above, and , so
   

   Ackermann function

   The Ackermann function
   Ackermann function
   In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...
   
    may be expressed using Conway chained arrow notation:
   

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

   Graham's number

   Graham's number
   Graham's number
   Graham's number, named after Ronald Graham, is a large number that is an upper bound on the solution to a certain problem in Ramsey theory.The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977,...
   
     itself can not succinctly be expressed in Conway chained arrow notation, but by defining the intermediate function , we have:
   (see functional powers
   Function composition
   In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
   
   ), and
   
   
   Proof: Applying in order the definition, rule 3, and rule 4, we have:
   
   (with 64 's)
   
   (with 64 's)
   
   (with 64 's) (with 65 's) (computing as above).
   
   Since f is strictly increasing,
   which is the given inequality.
   
   With chain arrows it is very easy to specify a much larger number. For example, note that
   which is much greater than Graham's number.
   

   See also

   • Steinhaus–Moser notation
     Steinhaus–Moser notation
     In mathematics, Steinhaus–Moser notation is a means of expressing certain extremely large numbers. It is an extension of Steinhaus’s polygon notation.- Definitions :...
     
     
   • Ackermann function
     Ackermann function
     In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...
     
     
   • Systematically creating ever faster increasing sequences
   
   

   External links

   • Factoids > big numbers
   • Robert Munafo's Large Numbers
   The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.