Sagoĉena notacio de Conway

Sagoĉena notacio de Conway estas notacio por ekstreme grandaj nombroj, kiun kreis John Horton Conway. Nombroj en tiu ĉi sistemo estas skribitaj kiel finia ĉeno de naturaj nombroj, dividitaj per sagoj, ekz. 2→3→4→5→6.

Kiel kutimas en kombinatorikaj simbolaroj, la difino estas rekursia. En tiu ĉi okazo, la notacio povas esti transformita kiel la plej maldekstra numeralo en iu (plej ofte enorma) potenco.

Difino

La Ĉeno de Conway estas difinebla jene:

• Ĉiu pozitiva nombro estas ĉeno kun longo 1.
• Ĉeno de longo n, sekvanta per dekstren-montra sago → kaj pozitiva nombro, kune formas ĉenon kun longo $n+1$.

Ĉiu ĉeno reprezentas nombron laŭ jenaj reguloj:

Se p kaj q estas pozitivaj nombroj kaj X signifas ĉenon, do:

1. Ĉeno $p$ representas nombron p.
2. $p\to q$ representas $p^{q}$.
3. $X\to p\to 1$ estas sama kiel $X\to p$.
4. $X\to p\to (q+1)$ signifas $X\to (X\to (\dots (X\to (X)\to q)\dots )\to q)\to q$
   (kun p kopioj de X, p - 1 kopioj de q, kaj p - 1 paroj de parentezoj; aplikeblas kiam q > 0).

Observoj pri pli longaj ĉenoj:

• Ĉeno kun longo 3 transformeblas per Notacio de Knuth kaj Hiper-operatoroj:

${\begin{matrix}p\to q\to r={\mbox{hyper}}(p,r+2,q)=p\!\!\!&\underbrace {\uparrow \dots \uparrow } &\!\!\!q=p\uparrow ^{r}q.\\&\!\!\!r{\mbox{ indikiloj}}\!\!\!\end{matrix}}$

• Valoroj de ĉenoj kun longo 4 aŭ pli estas plej ofte neimageble grandaj kaj ne povas esti adekvate representitaj per notacio uzanta elementarajn aritmetikajn funkciojn.

Interpretado

Oni devas ĉiam rigardi ĉenon kiel la tuton. Sagoĉenoj ne priskribas iteraciitan aplikon de sama operatoro, kaj do ilin ne eblas dispartigi. La ĉenon de kutimaj matematikaj operatoroj (ekz. 3+4+5+6+7) oni povas dividigi en fragmentojn (ekz. (3+4)+5+(6+7)) sen ŝanĝo la rezulton, aŭ almenaŭ popaŝe solvi en difinita ordo (ekz. $2^{3^{4}}$ solveblas de dekstre maldekstren, kaj samon oni povas fari pri notacio de Knuth). Sed al ĉeno de Conway tio ne aplikeblas.

Ekzemple:

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

Notu, ke parentezoj ne necesas en la dua okazo por potenciiga notacio, ĉar la ordo de dekstre maldekstren estas defaŭlte akceptita. Sed por la ĉeno de Conway oni ilin bezonas, ĉar alie la signifo estus sama kiel en la unua okazo.

La kvaran regulon de difino necesas tre atente pririgardi: Ĉeno de 3 aŭ pli elementoj, kiu finiĝas je 2 aŭ pli granda nombro, povas esti transformita en la ĉenon de sama longo sed kun malpligrandigita lasta elemento per ioma (plej ofte enorma) grandigo de antaŭlasta elemento. Tiel eblas transformi la lastan elementon en 1 kaj do malplilongigi ĉenon laŭ la tria regulo. Kiam la ĉeno estos malplilongigita ĝis longo de 2 elementoj, ĝi iĝos simpla potenciiga operatoro. Praktike, tamen, la nombroj tre ofte iĝas tiom grandaj, ke tion ne eblas fari.

Specialaj Ecoj

• ĉeno X→Y havas formon X→p; do:
  • ĉeno komencanta je a estas potenco de a
    • ĉeno 1→Y estas egala al 1
• ĉeno X→1→Y estas egala al X
• ĉeno 2→2→Y estas egala al 4
• ĉeno X→2→2 estas egala al X→(X) (ĉeno X kun ĝia valoro aldonita kiel la lasta elemento)

Jenas la plej simplaj okazoj (kiam la ĉeno enhavas elementojn malpli grandajn ol 2):

• $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\to a^{b}$

(tio sekvas de last-menciita eco)

• $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)\to 1=a\to b\to (a\to b\to a^{b})$

Ĉiuj pli komplikaj ĉenoj kreskas enorme:

• $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$
• $a\to b\to 4\to 2=a\to b\to (a\to b\to (a\to b\to a^{b}))$

Se, por iu ajn ĉenoX, ni skribas $X\to p=f(p)$ do $X\to p\to 2=f^{p}(1)\!$ (vidu ankaŭ: Funkcia potenco).

Same, kiam ni skribas $X\to p\to q=f_{q}(p)$ ni havos $X\to p\to q+1=f_{q}^{p}(1)\!$, kaj, sekve, $f_{q+1}(p)=f_{q}^{p}(1)\!$.

Se ni aplikas tion al nova ĉeno X egala al $X\to p$, ni vidos ke ekz. $X\to p\to 3\to 2=f_{f_{f(p)}(p)}(p)\!$

Ekzemple, $10\to 10\to 3\to 2=10\uparrow ^{10\uparrow ^{10^{10}}10}10\!$, ĉar por X = (10) ni havas $f_{q}(10)=10\uparrow ^{q}10$, kaj ni rigardas la trian funkcian potencon de tiu ĉi funkcio kiel funkcion de q, kun q = 1.

Ekzemploj

Ne eblas doni plene laborantan interesan ekzemplo ĉar almenaŭ 4 eroj estas bezonataj. Tamen 1, 2 kaj 3 longaj ĉenoj, kiu povas esti prezentitaj en aliaj notacioj, estas elvolvita ĉi tie kiel ilustraj ekzemploj.

n

Ĉiu sola entjero n estas ĝuste la valoro n, ekzemple 7 = 7. Ĉi tiu ne konflikto kun la reguloj, ĉar kombinante regulon 3 malantaŭen kun regulo 2 oni havas ke 7 = 7→1 = 7¹ = 7.

p→q

= p^q (per regulo 2)

Tial 3→4 = 3⁴ = 81

Ankaŭ 123456→1 = 123456¹ = 123456 (per ambaŭ reguloj 3 kaj 2)

1→(ĉiu esprimo)

= 1 pro tio ke la tuta esprimo eble malpligrandigas al 1^nombro = 1. Plu ĉiu ĉeno enhavanta na 1 povas esti tranĉita, ĝuste) antaŭ tiu 1; ekzemple X→1→Y=X por ĉiuj subĉenoj X,Y.

4→3→2

= 4→(4→(4)→1)→1 (per 1) kaj tiam, laborante de la enaj parentezoj eksteren,

= 4→(4→4→1)→1 (forpreni redundajn parentezojn)

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

= 4→(256)→1 (3)

= 4→256→1 (forpreni redundajn parentezojn)

= 4→256 (2)

= 1.34078079299 × 10¹⁵⁴ proksimume (3)

4→3→2 alternative analizita

= 4→(4→(4)→1)→1 (per 1) kaj tiam, forprenante lastan "→1",

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

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

= 4→(256) (forpreni redundajn parentezojn, 3)

= 1.34078079299 × 10¹⁵⁴ proksimume (forpreni redundajn parentezojn, 3)

Per notacio de Knuth: $4\uparrow \uparrow 3=4\uparrow 4\uparrow 4=4^{256}$

2→2→4

= 2→(2)→3 (per 1)

= 2→2→3 (forpreni redundajn parentezojn)

= 2→2→2 (1, forpreni redundajn parentezojn)

= 2→2→1 (1, forpreni redundajn parentezojn)

= 2→2 (2)

= 4 (3) (Fakte ĉiu ĉeno komencanta kun 2→2 estas 4.)

2→4→3

= 2→(2→(2→(2)→2)→2)→2 (per 1) La kvar kopioj de X (kiu estas 2 ĉi tie) estas en grasa tiparo por distingi ilin de la tri kopioj de q (kiu estas ankaŭ 2)

= 2→(2→(2→2→2)→2)→2 (forpreni redundajn parentezojn)

= 2→(2→(4)→2)→2 (antaŭa ekzemplo)

= 2→(2→4→2)→2 (forpreni redundajn parentezojn) (esprimo elvolvita en venonta ekvacio montrita en grasa tiparo en ambaŭ linioj)

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

= 2→(2→(2→(2→2→1)→1)→1)→2 (forpreni redundajn parentezojn)

= 2→(2→(2→(2→2)))→2 (2 multfoje)

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

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

= 2→65536→2 (3, forpreni redundajn parentezojn)

= 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1 (1) kun 65535 aroj de parentezoj

= 2→(2→(2→(...2→(2→(2))...)))) (2 multfoje)

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

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

= $2^{2^{\dots ^{2}}}$ (turo kun 2¹⁶ = 65536 etaĝoj)

kio estas neimageble granda. Per notacio de Knuth: $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 (per 1)

= 2→3→8 (2 kaj 3)

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

= 2→4→7 (2→2 komence rezultiĝas je 4)

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

= 2→(2→4→6)→6 (2→2 komence rezultiĝas je 4)

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

= 2→(2→(2→4→5)→5)→6 (2→2 komence rezultiĝas je 4)

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

= 2→(2→(2→(2→4→4)→4)→5)→6 (2→2 komence rezultiĝas je 4)

= 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 (2→2 komence rezultiĝas je 4)

= 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6 (antaŭa ekzemplo)

kio estas ankoraŭ multe pli granda ol la antaŭa nombro

Per notacio de Knuth: $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 kaj 3)

= 3→3→8 (1)

Per notacio de Knuth: $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.6\times 10^{12}$.

Nombro de Graham

Nombro de Graham $G\!$ ne povas esti koncize esprimita per la sagoĉena notacio de Conway, sed per difino de funkcio $f(n)=3\rightarrow 3\rightarrow n\!$, oni havas, ke

$G=f^{64}(4)\,$ (vidu en funkcia komponaĵo), kaj

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

Pruvo: Aplikante laŭvice la difinon, regulon 3, kaj regulon 4, oni havas ke:

$f^{64}(1)\,$

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\dots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 1))\dots ))\,$ (kun 64 da $3\rightarrow 3$)

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\dots (3\rightarrow 3\rightarrow (3\rightarrow 3)\rightarrow 1)\dots )\rightarrow 1)\rightarrow 1\,$

$=3\rightarrow 3\rightarrow 64\rightarrow 2;\,$

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

$f^{64}(27)\,$

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\dots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27))\dots ))\,$ (kun 64 da $3\rightarrow 3$)

$=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\dots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (3\rightarrow 3)))\dots ))\,$ (kun 65 da $3\rightarrow 3$)

$=3\rightarrow 3\rightarrow 65\rightarrow 2\,$ (komputante kiel pli supre).

Pro tio ke f estas severe pligrandiĝanta,

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

kiu estas la donita neegalaĵo. Noto ke

$3\rightarrow 3\rightarrow 3\rightarrow 3=3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27\rightarrow 2)\rightarrow 2\,$

kio estas multe pli granda ol nombro de Graham.

Akermana funkcio

La akermana funkcio povas esti esprimita uzante la sagoĉenan notacion de Conway:

A(m, n) = (2 → (n+3) → (m-2)) -3 por m>2

de ĉi tie

2 → n → m = A(m+2,n-3) + 3 por n>2

(n=1 kaj n=2 devus respektivi alA(m,-2)=-1 kaj A(m,-1)=1, kio povis logike ricevita).

Vidu ankaŭ

• Hiperoperatoro
• Notacio de Steinhaus-Moser
• Notacio de Knuth
• Akermana funkcio
• Nombro de Graham

Eksteraj ligiloj

• Pri grandaj nombroj
• Grandaj Nombroj de Robert Munafo