iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://eo.wikipedia.org/wiki/Sagoĉena_notacio_de_Conway
Sagoĉena notacio de Conway - Vikipedio Saltu al enhavo

Sagoĉena notacio de Conway

Nuna versio (nereviziita)
El Vikipedio, la libera enciklopedio

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.

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 .

Ĉiu ĉeno reprezentas nombron laŭ jenaj reguloj:

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

  1. Ĉeno representas nombron p.
  2. representas .
  3. estas sama kiel .
  4. signifas
    (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:

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

Interpretado

[redakti | redakti fonton]

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. solveblas de dekstre maldekstren, kaj samon oni povas fari pri notacio de Knuth). Sed al ĉeno de Conway tio ne aplikeblas.

Ekzemple:

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

[redakti | redakti fonton]
  • ĉ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):

(tio sekvas de last-menciita eco)

Ĉiuj pli komplikaj ĉenoj kreskas enorme:

Se, por iu ajn ĉenoX, ni skribas do (vidu ankaŭ: Funkcia potenco).

Same, kiam ni skribas ni havos , kaj, sekve, .

Se ni aplikas tion al nova ĉeno X egala al , ni vidos ke ekz.

Ekzemple, , ĉar por X = (10) ni havas , kaj ni rigardas la trian funkcian potencon de tiu ĉi funkcio kiel funkcion de q, kun q = 1.

Ekzemploj

[redakti | redakti fonton]

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 = 71 = 7.

p→q

= pq (per regulo 2)
Tial 3→4 = 34 = 81
Ankaŭ 123456→1 = 1234561 = 123456 (per ambaŭ reguloj 3 kaj 2)

1→(ĉiu esprimo)

= 1 pro tio ke la tuta esprimo eble malpligrandigas al 1nombro = 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 × 10154 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 × 10154 proksimume (forpreni redundajn parentezojn, 3)

Per notacio de Knuth:

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)
= (turo kun 216 = 65536 etaĝoj)

kio estas neimageble granda. Per notacio de Knuth: .

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:

3→2→2→2

= 3→2→(3→2)→1 (1)
= 3→2→9 (2 kaj 3)
= 3→3→8 (1)

Per notacio de Knuth: .

Nombro de Graham

[redakti | redakti fonton]

Nombro de Graham ne povas esti koncize esprimita per la sagoĉena notacio de Conway, sed per difino de funkcio , oni havas, ke

(vidu en funkcia komponaĵo), kaj

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

(kun 64 da )

(kun 64 da )
(kun 65 da )
(komputante kiel pli supre).

Pro tio ke f estas severe pligrandiĝanta,

kiu estas la donita neegalaĵo. Notu, ke

kio estas multe pli granda ol nombro de Graham.

Akermana funkcio

[redakti | redakti fonton]

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ŭ

[redakti | redakti fonton]

Eksteraj ligiloj

[redakti | redakti fonton]