Sagoĉena notacio de Conway

Ĉena Indikila Notacio de Conway estas maniero por skribi ekstreme grandajn nombrojn kreita far John Horton Conway. Numeroj en tiu sistemo estas skribitaj kiel finita ĉeno de naturaloj, dividitaj per dekstrenindikiloj, ekz. 2→3→4→5→6.

Kiel kutimas por kombinatikaj simbolaroj, la difino estas rikursa. 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 difinatas jene:

• Ĉiu positiva nombro estas ĉeno kun longo 1.
• Ĉeno de longo n, sekvanta per dekstrenindikilo → kaj positiva 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 iu alia notacio.

Interpretado

Oni devas ĉiam rigardi ĉenon kiel la tuton. Ĉenoj de indikiloj 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

Neeblas doni plene laborantan interesan ekzemplo ĉar almenaŭ 4 eroj estas bezonataj. Tamen 1, 2 kaj 3 longaj ĉenoj, kiu povas esti prezentitaj en aliaj skribmanieroj, 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 supren-saga skribmaniero 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 skribmaniero 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 skribmaniero 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 skribmaniero 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 ĉenita saga skribmaniero 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 ĉenitan sagan skribmanieron 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
• Skribmaniero de Steinhaus-Moser
• Supren-saga skribmaniero de Knuth
• Akermana funkcio
• Nombro de Graham

Eksteraj ligiloj

greke Pri grandaj nombroj greke Grandaj Nombroj de Robert Munafo