Conway kedjad pil notation

Conway kedjad pilnotation , skapad av matematikern John Horton Conway , är ett sätt att uttrycka vissa extremt stora tal . Det är helt enkelt en ändlig sekvens av positiva heltal separerade av högerpilar, t.ex. $2\to 3\to 4\to 5\to 6$ .

Som med de flesta kombinatoriska notationer är definitionen rekursiv . I det här fallet löser sig notationen så småningom till att vara talet längst till vänster upp till någon (vanligtvis enorm) heltalspotens.

Definition och översikt

En "Conway-kedja" definieras enligt följande:

• Varje positivt heltal är en kedja med längden $1$ .
• En kedja med längden n följt av en högerpil → och ett positivt heltal bildar tillsammans en kedja med längden $n+1$ .

Varje kedja representerar ett heltal, enligt de sex reglerna nedan. Två kedjor sägs vara ekvivalenta om de representerar samma heltal.

Låt $a,b$ beteckna positiva heltal och låt $\#$ beteckna den oförändrade resten av kedjan. Sedan:

1. En tom kedja (eller en kedja med längden 0) är lika med $1$
2. Kedjan $a$ representerar talet $a$ .
3. Kedjan $a\rightarrow b$ representerar talet $a^{b}$ .
4. Kedjan $\#\rightarrow 1\rightarrow a$ representerar samma nummer som kedjan $\#$
5. Kedjan $\#\rightarrow 1$ representerar samma nummer som kedjan $\#$
6. Annars representerar kedjan $\#\rightarrow (a+1)\rightarrow (b+1)$ samma nummer som kedjan $\#\rightarrow (\#\rightarrow a\rightarrow (b+1))\rightarrow b$ .

Egenskaper

1. En kedja utvärderas till en perfekt kraft av sitt första nummer
2. Därför är $1\to Y$ lika med $1$
3. $X\to 1\to Y$ motsvarar $X$
4. $2\to 2\to Y$ är lika med $4$
5. $X\to 2\to 2$ motsvarar $X\to (X)$ (inte att förväxla med $X\to X$ )

Tolkning

Man måste vara noga med att behandla en pilkedja som en helhet . Pilkedjor beskriver inte den itererade tillämpningen av en binär operator. Medan kedjor av andra infixade symboler (t.ex. 3 + 4 + 5 + 6 + 7) ofta kan betraktas i fragment (t.ex. (3 + 4) + 5 + (6 + 7)) utan att ändra betydelse (se associativitet ) , eller åtminstone kan utvärderas steg för steg i föreskriven ordning, t.ex. 3 ^{4 5 6 7} från höger till vänster, så är det inte med Conways pilkedjor.

Till exempel:

• $2\rightarrow 3\rightarrow 2=2\uparrow \uparrow 3=2^{2^{2}}=16$
• $2\rightarrow \left(3\rightarrow 2\right)=2^{(3^{2})}=2^ {3^{2}}=512$
• $\left(2\rightarrow 3\right)\rightarrow 2=\left(2^{3}\right)^{2}=64$

Den sjätte definitionsregeln är kärnan: En kedja med 4 eller fler element som slutar med 2 eller högre blir en kedja av samma längd med ett (vanligtvis kraftigt) ökat näst sista element. Men dess yttersta element minskas, vilket så småningom tillåter den femte regeln att förkorta kedjan. Efter, för att parafrasera Knuth , "mycket detalj", reduceras kedjan till tre element och den fjärde regeln avslutar rekursionen.

Exempel

Exemplen blir ganska komplicerade snabbt. Här är några små exempel:

$n$

$=n$ (enligt regel 2)

$p\to q$

$=p^{q}$ (enligt regel 3)

Således, $3\to 4=3^{4}=81$

$4\to 3\to 2$

$=4\uparrow \uparrow 3$ (enligt regel 4)

$=4\uparrow (4\uparrow 4)$

$=4\uparrow 256$

$=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,$$\$

$4^{256}}$

$_ 154}}$

$2\to 2\to a$

$=2[\uparrow ^{a}]2$ (enligt regel 4)

$=4$ (se Knuths upp-pil notation )

$2\to 4\to 3$

$=2\uparrow \uparrow \uparrow 4$ (enligt regel 4)

$=2\uparrow \uparrow (2) \uparrow \uparrow (2\uparrow \uparrow 2))$

$=2\uparrow \uparrow (2\uparrow \uparrow 4)$

$=2\uparrow \uparrow (2\uparrow (2\uparrow (2\uparrow 2)))$

${\ displaystyle =2\uparrow \uparrow (2\uparrow (2\uparrow 4))}$

$=2\uparrow \uparrow (2\uparrow 16)$

$=2\uparrow \uparrow (65536)$

$={^{65536}2}$ (se tetration )

$2\to 3\to 2\to 2$

$=2\to 3\to (2\to 3)\to 1$ (enligt regel 6)

$=2 \to 3\to 8\to 1$ (enligt regel 3)

$=2\to 3\to 8$ (genom regel 5)

$=2\to (2\to 2\to 8)\to 7$ (enligt regel 6)

$=2\to 4\to 7$ (genom regel 6)

$=2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 4$ (enligt regel 4)

= mycket större än föregående nummer

$3\to 2\to 2\to 2$

$=3\to 2\to (3\to 2)\to 1$ (enligt regel 6)

$=3 \to 2\to 9\to 1$ (enligt regel 3)

$=3\to 2\to 9$ (genom regel 5)

$=3\ till 3\till 8$ (enligt regel 6)

$=3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3$ (genom regel 4)

= mycket, mycket större än föregående nummer

Systematiska exempel

De enklaste fallen med fyra termer (som inte innehåller heltal mindre än 2) är:

• 
  
  
  
  $a\to b\to 2\to 2$$=a\to b\to 2\to (1+1) )$$=a\to b\to (a\to b)\to 1$$=a\to b\ till a^{b}$$=a[a^{b}+2]b$

(motsvarande den sistnämnda egenskapen)

• 
  
  
  
  $a\to b\to 3\to 2$$=a\to b\to 3\to (1+1) )$$=a\to b\to (a\to b\to (a\to b)\to 1)\ till 1$$=a\to b\to (a\to b\to a^{b})$$=a[a\to b\to 2\to 2+2]b$
• 
  
  $a\to b\to 4\to 2$$=a\to b\to (a\to b\to (a\to b\to a^{b}))$$=a[a\to b\to 3\ till 2+2]b$

Vi kan se ett mönster här. Om vi ​​för någon kedja $X$ låter $f(p)=X\to p$ då $X\to p\to 2=f^{p}(1)$ (se funktionella potenser ).

Genom att tillämpa detta med $X=a\to b$ , sedan $f(p)=a[p+2]b$ och $a\to b\to p\to 2=a[a\to b \to (p-1)\to 2+2]b=f^{p}(1)$

Således, till exempel, $10\to 6\to 3\to 2=10[10[1000002]6+2]6$ .

Gå vidare:

• 
  
  
  
  $a\to b\to 2\to 3$$=a\to b\to 2\to (2+1) )$$=a\to b\to (a\to b)\to 2$$=a\to b\to a^{b}\to 2$$=f^{a^{b}}(1)$

Återigen kan vi generalisera. När vi skriver $g_{q}(p)=X\to p\to q$ har vi ${ \displaystyle X\to p\to q+1=g_{q}^{p}(1)} ,$ det vill säga $g_{q+1 }(p)=g_{q}^{p}(1)$ . I fallet ovan, $g_{2}(p)=a\to b\to p\to 2=f^{p }(1)$ och $g_{3}(p)=g_{2}^{p}(1)$ , så $a\to b\to 2\ till 3=g_{3}(2)=g_{2}^{2}(1)=g_{2}(g_{2}(1))=f^{f(1)}(1)=f ^{a^{b}}(1)$

Ackermann funktion

Ackermann -funktionen kan uttryckas med Conway-kedjad pilnotation:

$A(m,n)=(2\to (n+3)\to (m-2) )-3$ för $m\geq 3$ (Eftersom $A(m,n)=2[m] (n+3)-3$ i hyperoperation )

därav

$2\to n\to m=A(m+2,n-3)+3$ för $n >2$

( $n=1$ och $n=2$ skulle motsvara $A(m,-2)=- 1$ och ${\displaystyle A(m,-1)=1} ,$ som logiskt skulle kunna läggas till).

Grahams nummer

Grahams nummer $G$ i sig kan inte uttryckas kortfattat i Conway-kedjad pilnotation, men det begränsas av följande:

$3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2$

Bevis: Vi definierar först mellanfunktionen ${\displaystyle f(n)=3\högerpil 3\högerpil n={\begin{matrix} 3\underbrace {\uparrow \uparrow \cdots \uparrow } 3\\{\text{n arrows}}\end{matris}}} , som kan användas$ för att definiera Grahams tal som ${\ displaystil G=f^{64}(4)}$ . (Upphöjd skrift 64 betecknar en funktionell makt .)

Genom att tillämpa regel 2 och regel 4 baklänges förenklar vi:

$f^{64}(1)$

${\displaystyle =3\högerpil 3\högerpil (3\högerpil 3\högerpil (\cdots (3) \rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 1))\cdots ))} ($ med 64 $3\rightarrow 3$ s)

$=3\högerpil 3\högerpil (3\högerpil 3\högerpil (\cdots (3\högerpil 3\högerpil (3\högerpil) 3)\högerpil 1)\cdots )\högerpil 1)\högerpil 1$

$=3\högerpil 3\högerpil 64\högerpil 2;$

$$}=&3 \underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\ ;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow 3\end{matris}}\right\}{\text{64 lager }}}$$

$f^{64}(4)=G;$

$=3\högerpil 3\högerpil (3\högerpil 3\högerpil (\cdots (3) \rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 4))\cdots ))$ (med 64 $3\rightarrow 3$ s)

$${\displaystyle \left.{\begin$$

$f^{64}(27)$

${\displaystyle =3\högerpil 3\högerpil (3\högerpil 3\högerpil (\cdots (3) \rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27))\cdots ))} ($ med 64 $3\rightarrow 3$ s)

$=3\högerpil 3\högerpil (3\högerpil 3\högerpil (\cdots (3\högerpil 3\högerpil (3\högerpil) 3\rightarrow (3\rightarrow 3)))\cdots ))$ (med 65 $3\rightarrow 3$ s)

$=3\rightarrow 3\ högerpil 65\högerpil 2$ (beräknar enligt ovan).

$=f^{65}(1)$

$$=&3 \underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\ ;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3\\&3\uparrow 3\end{matris}}\right\}{\text{65 lager }}}$$

Eftersom f är strikt ökande ,

$f^{64}(1)<f^{64}(4)<f^{64}(27)$

vilket är den givna ojämlikheten.

Med kedjade pilar är det mycket enkelt att ange ett tal som är mycket större än $G$ , till exempel $3\rightarrow 3\rightarrow 3\rightarrow 3$ .

$3\rightarrow 3\rightarrow 3\rightarrow 3$

$=3\högerpil 3\högerpil (3\högerpil 3\högerpil 27\högerpil 2)\högerpil 2\,$

$=f^{3\rightarrow 3\rightarrow 27\rightarrow 2}(1)$

$=f^{f^{27} (1)}(1)$

$$&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \ uparrow \cdots \cdots \cdots \uparrow } 3\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3 \\&3\uparrow 3\end{matrix}}\right\}\left.{\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3\\\underbrace {\qquad \;\;\vdots \qquad \;\;} \\3\underbrace {\uparrow \cdots \cdot \ uparrow } 3\\3\uparrow 3\end{matrix}}\right\}\ 3\uparrow 3={\text{27 lager}}}$$

vilket är mycket större än Grahams tal, eftersom talet $3\rightarrow 3\rightarrow 27\rightarrow 2$$=f^{27}(1)$ är mycket större än $65$ .

CG-funktion

Conway och Guy skapade en enkel funktion med ett argument som diagonaliserar över hela notationen, definierad som:

$cg(n)=\underbrace {n\högerpil n\högerpil \prickar \högerpil n\högerpil n\ högerpil n} _{n}$

vilket betyder att sekvensen är:

$cg(1)=1$

$cg(2)=2\to 2=2^{2}=4$

$cg(3)=3\to 3\to 3=3\uparrow \uparrow \uparrow 3$

$cg(4)=4\to 4\to 4\to 4$

$cg(5)=5\to 5\to 5\to 5\to 5$

...

Denna funktion växer, som man kan förvänta sig, utomordentligt snabbt.

Förlängning av Peter Hurford

Peter Hurford, en webbutvecklare och statistiker, har definierat ett tillägg till denna notation:

$a\rightarrow _{b}c =\underbrace {a\högerpil _{b-1}a\högerpil _{b-1}a\högerpil _{b-1}\dots \rightarrow _{b-1}a\högerpil _{b-1} a\högerpil _{b-1}a} _{c{\text{ pilar}}}$

$a\rightarrow _{1}b=a\rightarrow b$

Alla normala regler är i övrigt oförändrade.

$a\rightarrow _{2}(a-1)$ är redan lika med ovannämnda $cg(a)$ , och funktionen $f(n)=n\rightarrow _{n}n$ växer mycket snabbare än Conway och Guys $cg(n)$ .

Observera att uttryck som $a\rightarrow _{b}c\rightarrow _{d}e$ är olagliga om $b$ och $d$ är olika nummer; en kedja får bara ha en typ av högerpil.

Men om vi ändrar detta något så att:

$a\ högerpil _{b}c\högerpil _{d}e=a\högerpil _{b}\underbrace {c\högerpil _{d-1}c\högerpil _{d-1}c\högerpil _{d-1 }\dots \rightarrow _{d-1}c\rightarrow _{d-1}c\rightarrow _{d-1}c} _{e{\text{ pilar}}}$

då blir inte bara $a\rightarrow _{b}c\rightarrow _{d}e$ laglig, utan notationen som helhet blir mycket starkare.

Se även

• Steinhaus–Moser notation
• Skapa systematiskt allt snabbare ökande sekvenser

externa länkar

• Fakta > stora siffror
• Robert Munafos Stora siffror
• The Book of Numbers av JH Conway och RK Guy