Conway Chained Arrow Notation Article Index for
Conway 		Website Links For
Conway 		 

Information About

Conway Chained Arrow Notation
  CATEGORIES ABOUT CONWAY CHAINED ARROW NOTATION
   
mathematical notation
   
large numbers
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



As with most Combinatorial symbologies, the definition is recursive. 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 n+1.


A chain ''Y'' not contained inside a larger chain in one of the forms X o Y, Y o Z, or X o Y o 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:
# X o p o (q + 1) is equivalent to X o ( X o ( \dots (X o ( X ) o q)\dots ) o q ) o q
(with ''p'' copies of ''X'', ''p'' -1 copies of ''q'', and ''p'' -1 pairs of parentheses).
# X o 1 is equivalent to ''X''.
# p o q is equivalent to the Exponential expression p^q.

Some observations for longer chains:


p o q o r = \mbox{hyper}(p,r+2,q) = p \!\!\! & \underbrace{ \uparrow \dots \uparrow } & \!\!\! q = p\uparrow^r q.\
& \!\!\! r \mbox{ arrows} \!\!\!
\end{matrix}
  • A chain of length 4 or more has a value that is, generally, too large to comprehend.



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. 2^{3^4} from right to left, that is not so with Conway's arrow.

For example:
  • 2 ightarrow3 ightarrow2 = 2\uparrow\uparrow3 = 2^{2^2} = 16

  • 2 ightarrow\left(3 ightarrow2 ight) = 2^{3^2} = 512

  • \left(2 ightarrow3 ight) ightarrow2 = \left(2^3 ight)^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.

Properties:
  • a chain ''X→Y'' is of the form ''X→p''; hence:

  • ---a chain starting with ''a'' is a power of ''a''

  • --a chain 1→''Y'' is equal to 1

  • a chain ''X→1→Y'' is equal to ''X''

  • a chain 2→2→''Y'' is equal to 4

  • a chain ''X''→2→2 is equal to ''X''→(''X'') (chain ''X'' with its value concatenated to it)


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

  • a o b o 2 o 2 = a o b o 2 o (1 + 1) = a o b o (a o b) o 1 = a o b o a^b (also following from the last-mentioned property)

  • a o b o 3 o 2 = a o b o 3 o (1 + 1) = a o b o (a o b o (a o b) o 1) o 1 = a o b o (a o b o a^b)


Any more complicated and it gets large:

  • a o b o 2 o 3 = a o b o 2 o (2 + 1) = a o b o (a o b) o 2 = a o b o a^b o 2

  • a o b o 4 o 2 = a o b o (a o b o (a o b o a^b))


If, for any chain ''X'', we write
X o p = f(p) then X o p o 2 = f^p(1)\! (see
Functional Powers ).

Similarly when we write X o p o q = f_q(p) we have X o p o q+1 = f_q^p(1)\!, that is, f_{q+1}(p) = f_q^p(1)\!.

Applying this with a new ''X'' equal to X o p, we see that e.g. X o p o 3 o 2 = f_{f_{f(p)}(p)}(p)\!

For example, 10 o 10 o 3 o 2 = 10 \uparrow ^{10 \uparrow ^{10^{10}} 10} 10 \!, because for X = (10) we have f_q(10)=10 \uparrow ^{q} 10, and we have to take the third power of this function as function of ''q'', at ''q'' = 1.


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 = 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; 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 {Link without Title} )
:= 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 \uparrow \uparrow 3 = 4 \uparrow 4 \uparrow 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 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 (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^{2^{\dots^2}} (a tower with 216 = 65536 stories)
which is unimaginably large. With Knuth's arrows: 2 \uparrow \uparrow \uparrow 4 = 2 \uparrow \uparrow 2\uparrow \uparrow 2 \uparrow \uparrow 2=2 \uparrow \uparrow 2 \uparrow \uparrow 2 \uparrow 2=2\uparrow \uparrow 2 \uparrow \uparrow 4=2 \uparrow \uparrow 2 \uparrow 2 \uparrow 2 \uparrow 2 = 2 \uparrow \uparrow 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 (two initial 2's give 4 {Link without Title} )
:= 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)
:= ''still much larger than previous number''

With Knuth's arrows: 2 \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow 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 \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3 \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3 \uparrow \uparrow \uparrow \uparrow \uparrow 3 \uparrow \uparrow \uparrow \uparrow 3 \uparrow \uparrow \uparrow 3 \uparrow \uparrow 7.6e12.


GRAHAM'S NUMBER


Graham's Number G \! itself can not succinctly be expressed in Conway chained arrow notation, but by defining the intermediate function f(n) = 3 ightarrow 3 ightarrow n \!, we have:
G = f^{64}(4)\, (see Functional Powers ), and
3 ightarrow 3 ightarrow 64 ightarrow 2 < G < 3 ightarrow 3 ightarrow 65 ightarrow 2\,

Proof: Applying in order the definition, rule 2, and rule 1, we have:

f^{64}(1)\,
:= 3 ightarrow 3 ightarrow (3 ightarrow 3 ightarrow (\dots (3 ightarrow 3 ightarrow (3 ightarrow 3 ightarrow 1))\dots ))\, (with 64 3 ightarrow 3's)
:= 3 ightarrow 3 ightarrow (3 ightarrow 3 ightarrow (\dots (3 ightarrow 3 ightarrow (3 ightarrow 3) ightarrow 1) \dots ) ightarrow 1) ightarrow 1\,
:= 3 ightarrow 3 ightarrow 64 ightarrow 2;\,

f^{64}(4) = G;\,

f^{64}(27)\,
:= 3 ightarrow 3 ightarrow (3 ightarrow 3 ightarrow (\dots (3 ightarrow 3 ightarrow (3 ightarrow 3 ightarrow 27))\dots ))\, (with 64 3 ightarrow 3's)
:= 3 ightarrow 3 ightarrow (3 ightarrow 3 ightarrow (\dots (3 ightarrow 3 ightarrow (3 ightarrow 3 ightarrow (3 ightarrow 3)))\dots ))\, (with 65 3 ightarrow 3's)
:= 3 ightarrow 3 ightarrow 65 ightarrow 2\, (computing as above).

Since ''f'' is strictly increasing,
:f^{64}(1) < f^{64}(4) < f^{64}(27)\,
which is the given inequality. Note that
: 3 ightarrow 3 ightarrow 3 ightarrow 3 = 3 ightarrow 3 ightarrow (3 ightarrow 3 ightarrow 27 ightarrow 2) ightarrow 2\,
which is much greater than Graham's number.


ACKERMANN FUNCTION


The Ackermann Function may be expressed using Conway chained arrow notation:

A


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



EXTERNAL LINKS