Nagy számok

Fő kategória: matek.

Majdnem mindegyik pozitív egész szám nagyon nagy.

Nagy számok körülöttünk

Áttekintés

Az, hogy mi számít nagy számnak, igencsak szubjektív. Vannak kultúrák, melyeknek ahol alig van számra utaló szavuk. Ilyen például a Brazília területén élő Munduruku törzs, akik nyelvében csak 5-ig lehet számolni. Minden bizonnyal számukra igen nagy nehézséget jelent felfogni pl. azt, hogy száz.

De ha belegondolunk, az olyan fejlettnek tartott kultúrákban is, mint pl. a Római Birodalom, a mai fogalmainkhoz képest igen gyenge volt a számfogalmuk: eleve csak pozitív egész számokról lehetett szó kb. 4000-ig, tehát hiányoztak a negatív számok, a nem egész számok és a nagyobb számok is.

Ahogy egy gyerek felcseperedik, a saját számfogalma is fokozatosan bővül. Fontos állomás, amikor már el tudja képzelni a tíz feletti számokat, a százas nagyságrendbe való belépés is egy fontos előrelépés. Ezt követően jön az ezres, majd a milliós nagyságrend. A hétköznapi életben ritkán van szükség az ennél nagyobb, milliárdos nagyságrendbe belépni.

A milliárd után jön a billió, billiárd, trillió és a trilliárd. Személy szerint a gyerekkoromban ez egy tartós határt képezett, mivel akkor még nem használtam az exponenciális alakot, és nem tudtam, hogy mi jön a trilliárd után. Így számomra a létező legnagyobb egész szám a következő volt: 999.999.999.999.999.999.999.999. Azért jól el voltam ezzel is a hétköznapi életben.

Ezen az oldalon gondolunk egy nagyot, meg még egyet, meg még egyet, és olyan magasságokba fogunk kerülni, ami egyesek számára már-már szinte fájdalmat okozhat. Én szóltam! Olyan ez, mint egy hullámvasút, ahol egyszerre rettegünk és élvezzük a rettegést. Jó szórakozást!

Nevesített nagy számok

Először is nézzük, hogy mely nagy számoknak vannak nevei.

Érdemes megjegyezni, hogy az európai (beleértve a magyart is) és az amerikai terminológia eltér egymástól. Pl. az ezer millió magyarul milliárd, az amerikai angolban billion. Amit mi billiónak hívunk (ami a mi terminológiánk szerint a milliárd ezerszerese), azt az amerikai angolban úgy hívják, hogy trillion. És ettől kezdve a magyarban a lépés milliószoros, az angolban ezerszeres.

Itt most a magyar megnevezést vesszük szemügyre.

Megnevezés Decimális alak Exponenciális alak
Ezer 1000 103
Millió 1.000.000 106
Milliárd 1.000.000.000 109
Billió 1.000.000.000.000 1012
Billiárd 1.000.000.000.000.000 1015
Trillió 1.000.000.000.000.000.000 1018
Trilliárd 1.000.000.000.000.000.000.000 1021
Kvadrillió 1.000.000.000.000.000.000.000.000 1024
Kvintillió 1.000.000.000.000.000.000.000.000.000.000 1030
Szextillió 1.000.000.000.000.000.000.000.000.000.000.000.000 1036
Szeptillió 1.000.000.000.000.000.000.000.000.000.000.000.000.000.000 1042
Oktillió 1.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 1048
Nonillió 1.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 1054
Decillió 1.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 1060

A sort lehetne folytatni: undecillió, duodecillió, tredecillió, kvattuordecillió, kvindecillion, szexdecillió, szeptendecillió, oktodecillió, novemdecillió, vigintillió stb. Itt lehet böngészni a lehetőségeket: https://en.wikipedia.org/wiki/Names_of_large_numbers.

Érdemes még három nevesített konstanst megemlíteni:

  • Googol: $10^{100}$
  • Googolplex: $10^{\text{Googol}} = 10^{10^{100}}$ (decimális formában leírhatatlan, ld. később)
  • Googolplexian: $10^{\text{Googolplex}} = 10^{10^{10^{100}}}$ (az emberi agy számára felfoghatatlan)

Hogy milyen nagy mondjuk a Googolplex, arról itt látható egy videó: https://www.youtube.com/watch?v=8GEebx72-qs.

A nagy számokról egy Wiki oldal: https://googology.fandom.com/wiki/Googology_Wiki.

Van-e ezeknek a számoknak értelme? A hétköznapi életben talán nem, ám előfordulhatnak olyan jelenségek, elméleti eredmények, amikor ebben a nagyságrendben mozgunk.

Nagy számok a fizikában

  • Az emberi testben levő sejtek száma: kb. $3.7 \cdot 10^{13}$
  • Bitek száma egy 5 terrabájtos merevlemezen: $4\cdot 10^{13}$
  • Avogadro konstans: $6.02\cdot 10^{23}$
  • A Nap tömege kb. $2\cdot 10^{30} \text{kg}$
  • A megfigyelhető világegyetemben található elemi részecskék száma: $10^{80}$. Ez egyúttal azt is jelenti, hogy a Googolplex számot még elméletileg sem lehet leírni decimális formában.
  • A másik véglet, az elektron tömege kb. $9.1 \cdot 10^{-31} \text{kg} \approx 10^{-30} \text{kg}$. Kicsit furcsán hangzik, de ebből az is következik, $10^{30}$ darab elektron tömege 1 kg.
  • A Planck-idő nagyon leegyszerűsítve az idő kvantuma,a mi azt jelenti, hogy ennél rövidebb idő alatt nincs értelme összehasonlítani az univerzum két egymást követő állapotát. Ennek az értéke kb. $5.4\cdot 10^{-44}$ másodperc. Az univerzum becsült élettartama nagyjából $8\cdot 10^{60}$-szorosa a Plack-időnek.
  • A Planck-hossz úgymond a létező legkisebb hosszúság; hosszúság még elméletileg sem mérhető ennél kisebb pontossággal. Ennek az értéke kb. $1.6\cdot 10^{-35}$ méter. A teljes világmindenség teljes mérete a Plack-hossznak $4\cdot 10^{185}$-szöröse.
  • Poincaré ismétlődési idő. Poincaré ismétlődési tétele szerint minden dinamikus rendszer kellően hosszú idő elteltével visszatér eredeti állapotába. Tehát ha pl. egy zárt rendszerben összekeverünk kétféle gázt, akkor a gázmolekulák véletlenszerű mozgásával előbb-utóbb nagyon hosszú idő elteltével létrejön az eredeti, nem keveredett állapot. Ebből egy merész gondolattal az is következik, hogy mivel a teljes világegyetem tekinthető dinamikus rendszernek, a világegyetemünk is végtelen ismétlődések sorozatát éli át. Magyarán aki ezt olvassa, az gondolhat arra, hogy nagyon hosszú periódussal már végtelen sokszor előfordult, hogy pont így olvastad, és még végtelen sokszor elő fog fordulni. De milyen hosszú ez az idő? Erre van egy érdekes becslés: $10^{10^{10^{10^{2.08}}}}$, mondjuk év. De ha valaki ráérzett a nagy számok ízére, az érteni fogja, hogy lehet ennyi évezred, vagy akár ennyi nanoszekundum is, ez majdnem mindegy. Mekkora ez a szám? Nagyjából a Googolplexian. $10^{10^{10^{10^{2.08}}}} = 10^{10^{10^{120}}} = 10^{10^{1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000}}$. Tehát a 10 kitevőjében van egy egyes és 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 darab nulla. Ez egy olyan irtózatosan nagy szám, és a levezetés olyan elképesztő kerekítéseket tartalmazott, hogy elhanyagolható kerekítési hiba akár ennyi Planck-időt, akár ennyi évmilliárdot mondani. (Javasolt videó: https://www.youtube.com/watch?v=1GCf29FPM4k.)

Inflációs nagy számok

  • A Pengő annyira elértéktelenedett, hogy a Pengő-Forint átváltási arány (lényegében csak elméletben): $4\cdot10^{29}$.
  • Az inflációnál maradva: 1946 júliusában az árak kb. 15,3 óránként duplázódtak. Ezt egész évre kivetítve $3\cdot 10^{174}$ % inflációt kapunk eredményül.
  • A jugoszláv dinár is súlyos inflációt szenvedett el, ráadásul többször is. Denominációk (nullák törlése): 1966.01.01: 2, 1990.01.01: 4, 1991.07.01: 1, 1993.10.01: 6, 1994.01.01: 9, majd 1994.01.24-én 13.000.000 régi dinárért adtak 1 új dinárt. Mindent visszaszámolva elméletben $1.3\cdot10^{29}$ 1966 előtti dinárt kellett adni 1 új dinárért.

Játékkal kapcsolatos nagy számok

  • Shannon-szám, ami a lehetséges sakkjátszmák számát becsüli: $10^{120}$. Ez azzal a feltételezéssel jött ki, hogy egy átlagos pozícióban 30-35 legális lépéslehetőség van, és egy átlagos sakkparti kb. 40 lépéspár után befejeződik. A valóságban ez a szám ennél jóval nagyobb lehet, ugyanis az elvi leghosszabb sakkparti az 50 lépés szabály miatt megközelíti a 6000 lépést (3000 lépéspárt), és ha a legális sakkpartik átlagos hosszát mondjuk 5000-re becsüljük, akkor ennél jobb becslés a $35^{5000} \approx 10^{7500}$
  • A legális sakk álláslehetőségek számának becsült értéke: $4.8\cdot 10^{44}$
  • A góban hasonlóan impozáns jönnek ki. A különböző gó partik számának durva becslése $(19\cdot 19)! = 361! \approx 1.4\cdot 10^{768}$. Ezt a számot csökkentik a szabálytalan lépések, ugyanakkor növelik a körbekerített és levett kövek által felszabadult helyek beépítési lehetősége.
  • A legális gó állások száma: $2\cdot 10^{170}$
  • Egy 52 lapos francia kártyapakli összes lehetséges sorrendje: $1.24\cdot 10^{68}$
  • Egy 6*6*6-os Rubik kocka lehetséges állapotainak a száma kb. $1.57\cdot 10^{116}$

Nagy számok a matematikában

  • Számos számokkal kapcsolatos matematikai sejtés van, amit még nem sikerült bizonyítani, de ellenpéldát találni sem. Ugyanakkor akadnak olyanok, amit már sikerült megcáfolni. Pl. volt egy olyan sejtés, hogy minden pozitív $n$-re $n^{17}+9$ és $(n+1)^{17}+9$ relatív prímek. Az első ellenpélda ez a szám: $8424432925592889329288197322308900672459420460792433$.
  • A legnagyobb ismert prímszám: $2^{82,589,933}-1$
  • Skewes száma: egy 1933-as tanulmányban jelent meg a $10^{10^{10^{34}}}$ szám. Ezt már abban a magasságban van, amit igen nehéz felfogni: nehogy decimális, de sima exponenciális alakban sem lehet leírni. Ez a Googolplexnél is jóval nagyobb. Nagyjából az első olyan, felfoghatatlanul hatalmas szám, aminek van elméleti jelentősége. $10^{10^{10^{34}}} = 10^{10^{10000000000000000000000000000000000}}$, tehát egy egyes és utána $10^{10000000000000000000000000000000000}$ darab nulla. És mi ez a szám? A prímszámok darabszámára kétféle becslés van: a $\pi(x) = \frac{x}{\log(x)}$ és a $\text{li}(x) = \int_0^x \frac{1}{\ln t} dt$. Néhány próbálkozással azt tapasztaljuk, hogy $\pi(x) > \text{li}(x)$. Viszont nagy értékek esetén előfordulhat az is, hogy $\pi(x) < \text{li}(x)$. Azt nem tudjuk, hogy melyik a legkisebb szám, melyre ez utóbbi egyenlőtlenség igaz. Skewes dél-afrikai matematikus az említett tanulmányában az említett számot adta meg felső korlátnak. Azóta egyébként találtak jóval kisebb számokat is, pl. a $1.397\cdot 10^{316}$.

Látható, hogy ebben a "ligában", ha nem is a teljesen hétköznapi életben (a Munduruku törzs számára minden bizonnyal érdektelen az, hogy az univerzum teljes élettartama hány Planck-időnyi egység, ahogy a matematikai sejtések ellenpéldái is minden bizonnyal érdektelenek a számukra), de azért előfordulnak óriási számok.

Műveletek

Az igazán nagy számok leírásához a hagyományos műveletek alkalmatlanok. Lássunk néhány ismert és új műveletet!

Néhány helyen sajnos csak úgy tudtam megoldani, hogy előre hivatkozok. Remélhetőleg ez nem megy az érthetőség rovására.

Faktoriális

Az ismételt faktoriális egy igen erős játékos igazán nagy számok létrehozására.

Induljunk ki az alábbiból:

$10! = 3,628,800$

Tegyünk hozzá még egy felkiáltójelet!

$10!! = 3,628,800!$

Ezt már nem igazán tudjuk kiszámolni. Próbáljuk meg megbecsülni! A hatványozás felső korlátot ad a faktoriálisra. Emiatt vegyünk egy kisebb értéket, pl. az egymilliót, és vegyük az az egymillió egymilliomodik hatványát:

$1,000,000^{1,000,000} = 10^{6,000,000}$

Nagyon durva nagyságrendi becslésre ez is alkalmas volt. Ami egyébként nem is annyira rossz, ugyanis a tényleges érték kb. $1.020426 \cdot 10^{7,216,916}$.

És most jön az elfajulás: írjunk további faktoriálist jelző felkiáltójeleket. A harmadik felkiáltójel tehát jelentse a nagyjából hétmillió számjegyből álló szám faktoriálisát. Ezt már nyilván becsülni sem tudjuk.

De mennyi legyen a felkiáltójelek száma?

  • Látjuk, hogy már 3-nál is igen elfajuló a dolog.
  • Lehet a felkiáltójelek száma mondjuk $n$.
  • De lehet akár $n!$ is!

Tehát pl. $n=10$ esetén a szám:

$10\underbrace{!!!!\dots!}_{10!\text{ darab}}$

ahol a faktoriálist jelentő felkiáltójelek száma 10!, azaz 3.628.800.

Még sokkal nagyobb számokat kreálhatunk, ha a felkiáltójelek száma nem 10!, hanem mondjuk Googolplex. Ám az alábbi ötlet még ezt is bőven túlszárnyalja:

  • A sorozat első eleme legyen a 10!
  • A második eleme az, ahol a felkiáltójelek száma 10!
  • A harmadik elemben a felkiáltójelek száma legyen a második elem értéke.
  • És így tovább.
  • Ennek a sorozatnak vegyük mondjuk a Googolplexedik elemét!

Erős versenyző, és első blikkre nehéz elképzelni, hogy vannak ennél nagyobb számok. De az a helyzet, hogy akármilyen területen is ha vesszük a legerősebb szereplőket, akkor nekünk semmi esélyünk sincs. Magyarán: vannak ennél nagyobb számok is!

Műveletek ismétlése

0. Szukcesszió

$a + 1$

1. Összeadás: ismételt szukcesszó.

$a + b = a + \underbrace{1 + 1 + \dots + 1}_{b\text{ darab 1-es}}$

2. Szorzás: ismételt összeadás.

$a \cdot b = \underbrace{a + a + \dots + a}_{b\text{ darab }a}$

3. Hatványozás: ismételt szorzás.

$a^b = \underbrace{a \cdot a \cdot \dots \cdot a}_{b\text{ darab }a}$

4. Tetráció: ismételt hatványozás

$^b a = \underbrace{a^{a^{a^{\unicode{x22F0}^a}}}}_{b\text{ darab }a}$

5. Pentáció: ismételt tetráció

Lehetséges jelölések (némelyeket ld. később):

  • $a[5]b$ (hiperművelet jelölés)
  • $a\uparrow\uparrow\uparrow b$ (Knuth felfelé nyíl jelölés)
  • $a\rightarrow b \rightarrow 3$ (Conway láncolt nyíl jelölés)
  • $_b a$ (egy javaslat)

5. Hexáció: ismételt pentáció

Jelölések:

  • $a[6]b$ (hiperművelet jelölés)
  • $a\uparrow\uparrow\uparrow\uparrow b$ (Knuth felfelé nyíl jelölés)

A Knuth felfelé nyíl jelölés

Vezessünk be az ún. Knuth felfelé nyíl jelölést.

Egyszeres felfelé nyíl: hatványozás

$a \uparrow b = a^b$

Példa:

$3 \uparrow 3 = 3^3 = 27$

Kétszeres felfelé nyíl: ismételt egyszeres felfelé nyíl

$a \uparrow\uparrow b = \underbrace{a \uparrow(a \uparrow(\cdots\uparrow a))}_{\text{az $a$ $b$ alkalommal szerepel}}$

Példa:

$3 \uparrow\uparrow 3 = 3 \uparrow (3 \uparrow 3) = 3^{3^3} = 3^{27} = 7,625,597,484,987 \approx 7.6\cdot 10^{12}$

Ez tehát a tetráció; így is írhattuk volna:

$a \uparrow\uparrow b = ^b a$

Ugyanis a $b$ itt az emeletes hatványozás magasságát jelenti. Pl.

$10 \uparrow\uparrow 4 = ^{4} 10 = 10^{10^{10^{10}}}$

Ezt már igen nehéz elképzelni.

Háromszoros felfelé nyíl: ismételt kétszeres felfelé nyíl

$a \uparrow\uparrow\uparrow b = \underbrace{a \uparrow\uparrow(a \uparrow\uparrow(\cdots\uparrow\uparrow a))}_{\text{az $a$ $b$ alkalommal szerepel}}$

Ez a művelet a pentáció.

Példa hármassal:

$3 \uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow (3 \uparrow\uparrow 3)$

Mivel tudjuk, hogy $3 \uparrow\uparrow 3$ értéke kb. $7.6\cdot 10^{12}$, ezért ennek jelentése:

$3 \uparrow\uparrow 7.6\cdot 10^{12} = 3 \uparrow (3 \uparrow (3 \uparrow \dots (3 \uparrow 3) \dots)))$

azaz hatványozásra visszavezetve:

$3 \uparrow\uparrow\uparrow 3 = \underbrace{3^{3^{3^{\unicode{x22F0}^3}}}}_{\text{a hármasok száma kb. $7.6\cdot 10^{12}$}}$

Ne felejtsük el, hogy fentről kezdjük a hatványozást. A "legtetején": $3^{3^{3^3}} = 3^{3^{27}} = 3^{7,625,597,484,987}$

Ez utóbbit már nem tudjuk kiszámolni, olyan nagy. Viszont a hatványoszást még van 7,6 billiószor kell végrehajtani. Ez a pont a hagyományos számfogalmainkban (táhet amikor azt kérdezzük, hogy hány számjegyből áll) már felfoghatatlan.

Négyszeres felfelé nyíl: ismételt háromszoros felfelé nyíl

A fentiek mintájára definiáljuk ezt az újabb szörnyeteget:

$a \uparrow\uparrow\uparrow\uparrow b = \underbrace{a \uparrow\uparrow\uparrow(a \uparrow\uparrow\uparrow(\cdots\uparrow\uparrow\uparrow a))}_{\text{az $a$ $b$ alkalommal szerepel}}$

Tehát:

$3 \uparrow\uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow\uparrow (3 \uparrow\uparrow\uparrow 3) = \underbrace{3 \uparrow\uparrow 3 \uparrow\uparrow 3 \uparrow\uparrow \dots \uparrow\uparrow 3 \uparrow\uparrow 3}_{\text{a hármas $3 \uparrow\uparrow\uparrow 3$ alkalommal szerepel} }$

Mit jelent ez? Jobbról balra haladunk.

  • A sor végén ez látható: $3 \uparrow\uparrow 3 = 3^{3^3} = 3^{27} = 7,625,597,484,987$.
  • A következő lépés: $3 \uparrow\uparrow 3 \uparrow\uparrow 3 = \underbrace{3^{3^{3^{\unicode{x22F0}^3}}}}_{\text{a hármasok száma kb. $7.6\cdot 10^{12}$}}$, ami valójában a $3 \uparrow\uparrow\uparrow 3$
  • A következő lépés: $3 \uparrow\uparrow 3 \uparrow\uparrow 3 \uparrow\uparrow 3 = \underbrace{3^{3^{3^{\unicode{x22F0}^3}}}}_{\text{a hármasok száma $3 \uparrow\uparrow\uparrow 3$} }$
  • A következő lépés: egy olyan magas exponenciális torony, melyben a hármasok száma az előző szám.
  • És így tovább, és így tovább.
  • Mindezt $3 \uparrow\uparrow\uparrow 3$ alkalommal megismételve.

Ez a hexáció.

A Conway láncolt nyíl jelölés

John Horton Conway alkotta meg a nyíl jelölést. Ez egy rekurzív definíció, melynek pontjai az alábbiak ($a$ és $b$ számok, $\#$ pedig valaminek a megismétlése):

  • $a \rightarrow b = a \uparrow b = a^b$
  • $a \rightarrow b \rightarrow c = a \uparrow^c b$
  • $\# \rightarrow a \rightarrow b = \# \rightarrow (\# \rightarrow (a-1) \rightarrow b) \rightarrow (b-1)$
  • $\# \rightarrow 1 \rightarrow ... = \#$

Lássunk pár példát!

$3 \rightarrow 3 = 3 \uparrow 3 = 3^3 = 27$

$3 \rightarrow 3 \rightarrow 4 = 3 \uparrow^4 3 = 3 \uparrow\uparrow\uparrow\uparrow 3 = G1$

(A G1, a G2 stb. az első, második stb. Graham-szám, ld. később.)

$3 \rightarrow 3 \rightarrow 2 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2) \rightarrow 1 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3) = 3 \rightarrow 3 \rightarrow 27 = 3 \uparrow^{27} 3 = 3 \uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow 3 > G1$

$3 \rightarrow 3 \rightarrow 3 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \rightarrow 1 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 27) = 3 \uparrow^{3 \uparrow^{27} 3} 3 > G2$

$3 \rightarrow 3 \rightarrow 4 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 2) > G3$

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

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

És most képzeljünk el ilyen számokat:

  • $100 \rightarrow 100 \rightarrow 100 \rightarrow 100$
  • $100 \rightarrow 100 \rightarrow 100 \rightarrow 100 \rightarrow 100$

Ajánlott oldalak:

Az Ackermann-függvény

Az Ackermann-függvény definíciója:

$A(0, n) = n+1$
$A(m, 0) = A(m-1, 1)$
$A(m, n) = A(m-1, A(m, n-1))$

Az alábbi táblázat összefoglalja a konkrét értékeket, és érzékelteti, hogy milyen nagy sebességgel növekszik:

m \ n 0 1 2 3 4 n
0 1 2 3 4 5 n + 1
1 2 3 4 5 6 n + 2
2 3 5 7 9 11 2n + 3
3 5 13 29 61 125 2n+3 - 3
4 13 65533 265536 - 3 = 2↑↑5 - 3 2↑↑6 - 3 2↑↑7 - 3 2↑↑(n+3) - 3
5 65533 2↑↑↑4 - 3 2↑↑↑5 - 3 2↑↑↑6 - 3 2↑↑↑7 - 3 2↑↑↑(n+3) - 3
6 2↑↑↑↑3 - 3 2↑↑↑↑4 - 3 2↑↑↑↑5 - 3 2↑↑↑↑6 - 3 2↑↑↑↑7 - 3 2↑↑↑↑(n+3) - 3
m 2↑m-23 - 3 2↑m-24 - 3 2↑m-25 - 3 2↑m-26 - 3 2↑m-27 - 3 2↑m-2(n+3) - 3

Látható, hogy igen gyorsan itt is "egekbe szöknek" az értékek.

Ajánlott oldalak:

Gyorsan növekvő hierarchiák

Definiáljunk számsorozatokat!

$f_0(n) = n+1$

Ez a következő szám függvény, azaz a számolás. A sorozat elemei $2$, $3$, $4$, $5$, …

$f_1(n) = \underbrace{f_0(f_0(\dots f_0(n)\dots))}_{\text{n-szer}} = f_0^n(n) = 2n$

Tehát az n számra n-szer alkalmazzuk a következő számot, és ez a duplázás. Azaz a sorozat elemei: $2$, $4$, $6$, $8$, $10$, …

$f_2(n) = f_1^n(n) = n\cdot 2^n$

Ez már hatványozás, és a sorozat elemei 2, 8, 24, 64, 160, …

$f_3(n) = f_2^n(n) > 2 \uparrow\uparrow n$

Itt már megjelent a hatványozás hatványozása. A megadott alsó határ sorozat elemei: $2$, $4$, $16$, $256$, majd $2^{256}$ stb., tehát itt már a sorozat ötödik eleme (ill. annak alsó korlátja) is egy óriási szám; közel akkora, mint az univerzumban található összes elemi részecskék száma.

Ezt folytathatjuk tovább 4r, 5-re, 6-re stb. Akár G64-ig is eljuthatunk, akár TREE(3)-ig is. De lépjünk szintet! Képezzük az alábbi végtelen:

$f_1(1)$ $f_1(2)$ $f_1(3)$ $\cdots$
$f_2(1)$ $f_2(2)$ $f_2(3)$ $\cdots$
$f_3(1)$ $f_3(2)$ $f_3(3)$ $\cdots$
$\vdots$ $\vdots$ $\vdots$ $\ddots$

Behelyettesítve a konkrét értékeket:

$2$ $4$ $6$ $\cdots$
$2$ $8$ $24$ $\cdots$
$2$ $2048$ $\sim 10^{121}$ $\cdots$
$\vdots$ $\vdots$ $\vdots$ $\ddots$

A sorozat elemei legyen a mátrix átlója: $2$, $8$, $\sim 10^{121}$, és érdekességképpen $10 \uparrow\uparrow\uparrow 4 < f_4(4) < 10 \uparrow\uparrow\uparrow 5$, csak hogy legyen némi elképzelésünk, hogy mennyire nagyon gyorsan növekszik ez a sorozat. Emlékezzünk arra, hogy a $3 \uparrow\uparrow\uparrow 3$ milyen hatalmas volt!

A mátrix átlóját jelöljük a következőképpen:

$f_\omega(n) > 2\uparrow^{n-1} n$

Itt az ω tulajdonképpen a végtelen. Normál esetben persze ennek nem lenne értelme, de itt arról beszélünk, hogy melyik sorozat milyen gyorsan nő. Végtelen sok $f_N$ sorozat van, ami az $f_\omega$ alatt van, de van értelme az $f_\omega$ sorozatnak is. És láthatjuk, hogy ezzel a felfelé nyilak számát növeljük.

De ne álljunk meg itt, definiáljuk a következőt:

$f_{\omega+1}(n) = f_{\omega}^n(n)$

azaz az előzőekhez hasonlóan alkalmazzuk az $f_\omega(n)$-t n-szer. Folytassuk a sort:

$f_{\omega+2}(n) = f_{\omega+1}^n(n)$

$f_{\omega+3}(n) = f_{\omega+2}^n(n)$

$f_{\omega+4}(n) = f_{\omega+3}^n(n)$

stb.

Eljuthatunk $f_{\omega+\omega}(n)$-ig, azaz $f_{2\omega}(n)$-ig, majd $f_{2\omega+1}(n)$, $f_{2\omega+2}(n)$, …, utána $f_{3\omega}(n)$, …, $f_{4\omega}(n)$, …, $f_{\omega\cdot\omega}(n) = f_{\omega^2}(n)$, … Tekintsük csak a sorozat indexeit, az elejértől:

  • $0, 1, 2, 3, \dots$
  • $\omega, \omega+1, \omega+2, \omega+3, \dots$
  • $\omega+\omega = 2\omega, 2\omega+1, \dots, 3\omega, 4\omega \dots$
  • $\omega\cdot\omega = \omega^2, \omega^3, \omega^4, \dots$
  • $\omega^\omega = \omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}}, \dots$
  • $\omega^{\omega^{\omega^{\unicode{x22F0}^\omega}}} = \epsilon_0, \epsilon_1, \epsilon_2, \cdots$
  • $\epsilon_{\epsilon_0}, \epsilon_{\epsilon_{\epsilon_0}}, \epsilon_{\epsilon_{\epsilon_{\epsilon_0}}} \dots$
  • $\epsilon_{\epsilon_{\epsilon_{\ddots{\epsilon_0}}}} = \zeta_0, \dots, \eta_0, \dots, \Gamma_0$

A $\Gamma_0$ az ún. Fefermann-Schütte sorozat.

Ajánlott videó: https://www.youtube.com/watch?v=0X9DYRLmTNY

A számjegyek összegeinek perzisztenciája

A matematikában egy szám perzisztenciája azt jelenti, hogy hányszor kell egy adott műveletet egy egész számra alkalmazni, mielőtt elérnénk egy fix pontot, ahol a művelet már nem változtatja meg a számot. Jelen esetben a számjegyek összege a művelet, tehát összeadjuk a szám számjegyeit, majd az eredményét is, és a műveletet addig ismételjük, amíg az eredmény egyjegyű nem lesz. Például a 276 esetén a következő lépésben 15-öt kapunk, majd 6-ot, és onnan nem tudunk tovább menni, 2 lépésben elértük a végeredményt.

A kérdés az az, hogy melyik a legkisebb szám, melynek a perzisztenciája egy adott szám. Az eredmények:

  • 1: 10
  • 2: 19
  • 3: 199

Eddig semmi különös. De ami ezután következik, az egészen brutális:

  • 4: 19999999999999999999999 (itt a kilences száma 22)
  • 5: 1999…999 úgy, hogy a kilencesek száma 2222222222222222222222 (ez utóbbi számban a kettesek száma 22)

Persze ez messze nem növekszik oly mértékben, mint az imént bemutatott, mégis, meglepő, hogy ennyire gyors a növekedése

Fekete öves gigantikus számok

Graham-szám

A Graham-szám a következő feladat megoldása. Ezzel csak azt akarom illusztrálni, hogy a szám maga nem öncélú, hanem egy valós elméleti matematikai probléma megoldása.

Képzeljünk el egy $n$ dimenziós hiperkockát, és kössük össze minden csúcspárját, hogy egy $2^n$ csúcsú teljes gráfot kapjunk. Ezt követően színezzük ki e gráfnak minden élét csupán két színnel (például pirossal és kékkel). Mi $n$ legkisebb olyan értéke (azaz legalább hány dimenziós kell legyen a hiperkocka), amelyiknél minden ilyen színezés szükségképpen tartalmaz egy olyan teljes részgráfot, mely egyszínű (tehát minden éle piros, vagy minden éle kék), és még 4, egy síkban fekvő csúcsa is van?

A Graham-szám megértéséhez először meg kell értenünk a Knuth felfelé nyíl jelölést és az ott leírtakat.

Az első Graham-szám:

$\mathbf{G1} = 3 \uparrow\uparrow\uparrow\uparrow 3$

A második Graham-szám definíciója:

$\mathbf{G2} = 3 \underbrace{\uparrow\uparrow\uparrow\cdots\uparrow}_{\mathbf{G1} \text{ darab}} 3$

Nem 5, 100, vagy egymilliárd felfelé nyíl van a kát hármas között, hanem G1 darab! A harmadik:

$\mathbf{G3} = 3 \underbrace{\uparrow\uparrow\uparrow\cdots\uparrow}_{\mathbf{G2} \text{ darab}} 3$

És így tovább:

(1)
\begin{align} G_n = \begin{cases} 3 \uparrow\uparrow\uparrow\uparrow 3 & \text{ha $n = 1$} \\ 3 \uparrow^{G_{n-1}} 3 & \text{ha $n > 1$} \end{cases} \end{align}

A Graham-szám valójában a G64.

Egy látványos levezetése ennek a számnak: https://www.youtube.com/watch?v=txajrEOTkuY

TREE(3)

Nagynak gondoljuk a Graham-számot? A TREE(3)-hoz képest a G64 semmi. Nulla.

A játék a következő. Gráfelméleti fákat fogunk rajzolni. A TREE(1) játékban összesen egyféle színű lehet a csúcs (pl. zöld), a TREE(2)-ben kétféle (pl. zöld és piros), a TREE(3)-ban háromféle (pl. zöld, piros és fekete) stb. A játéknak két szabálya van:
1. Az n-edik fa legfeljebb n darab csúcsot tartalmazhat.
2. Nem rajzolhatunk olyan fát, aminek része egy korábbi fa a sorban.

A létező leghosszabb sorozatot kell rajzolnunk.

A döbbenetes itt az, hogy az első két elem meglehetősen kicsi, a harmadik pedig olyan nagy, ami mellett lényegében nulla a G64.

Lássuk először az első kettőt!

TREE(1)

Ezt csak így tudjuk lerajzolni:

Itt be is fejeződött, mert pl. a következő már tartalmazza az előzőt:

Tehát TREE(1) = 1

TREE(2)

Elindulhatunk így:

de így egyből befejezzük. Van ennél eggyel jobb megoldás:

Ennél jobbat nem találunk, tehát tehát TREE(2) = 3.

TREE(3)

És itt a szörny! Lássuk az első pár elemet (forrás: https://upload.wikimedia.org/wikipedia/commons/1/1e/TREE%283%29_sequence.png):

TREE3.png

Bizonyított, hogy véges (ld. Kruskal-tétel: https://en.wikipedia.org/wiki/Kruskal's_tree_theorem). A bizonyításhoz az elsőrendű halmazelmélet $2 \uparrow\uparrow 1000$ darab szimbólum kell. Ugyanakkor nincs univerzális bizonyítás arra, hogy ez tetszőleges n-re igaz, viszont tetszőleges n-re külön bizonyítható.

Ez a szám sokkal nagyobb mint a G(64), ld. az összehasonlításokat a végén. A Conway jelölés sem alkalmas ennek a szörnyetegnek a leírására.

A részletek meghaladják a kapacitásaimat. Elfogadom. Ezzel kapcsolatos ajánlott videók:

Busy Beaver

Jelentése: Szorgalmas hód. Szokásos rövidítéssel BB.

Tekintsük következő Turing-gépet:

  • Alapértelmezésben a teljes szalag mindegyik cellájának az értéke legyen 0.
  • A gépnek legyen n állapota, +1, a végállapot.
  • A gép legyen determinisztikus. Az aktuális állapota és az a bit, ahol éppen áll, egyértelműen határozza meg a következő lépést, ami a következő 3 dolgot jelenti:
    • Beállítja adott értékre az aktuális bitet.
    • Jobbra vagy balra lép.
    • Állapotot vált.

Vegyük az összes n állapotú Turing-gépet. (Az ilyen gépek száma $(4n+4)^{2n}$.) Vegyük az összes olyat, amelyik megáll. (Ezáltal a játék nem kiszámíthatóvá válik, mivel a megállási probléma nem eldönthető.) Mindegyik esetben számoljuk meg az egyeseket a szalagon, tehát egy adott Turing-gépen ez az eredménye. Az adott állapotú Turing-gép halmaz közös eredménye, azaz a $\Sigma(n)$ a legmagasabb ilyen szám.

Az elég egyértelmű, hogy ez a szám véges lesz, mivel a véges lépésben megálló Turing-gépekről beszélünk, és véges lépésben csak véges sok bitet tud egyesre állítani. Az viszont már sokkal nehezebb belátni, hogy ez nagyobb a Graham számoknál, de még a TREE számoknál is.

Sőt, van egy erős tétel: a BB számok bizonyos n érték felett egészen biztosan nagyobbak, mint a véges algoritmussal létrehozott, kiszámolható számsorozatok bármelyike.

Néhány BB érték:

  • 2 állapotú: 4
  • 3 állapotú: 6
  • 4 állapotú: 13
  • 5 állapotú: >= 4098
  • 6 állapotú: $> 10 \uparrow\uparrow 15$

Javasolt videó a témában:

Rayo száma

2007-ben az MIT-ban tartottak egy érdekes párbajt: ki tud nagyobb számot mondani. Nyilván voltak szabályok, pl. nem volt elég eggyel nagyobbat mondani mint az előző; valami egészen újszerűvel kellett előállni. A párbajt a mexikói filozófia professzor, Agustin Rayo nyerte az alábbi definícióval:

A legkisebb szám, amely nagyobb bármely olyan véges számnál, amelyet az elsőrendű halmazelmélet nyelvén Googol darabszámú szimbólummal vagy annál kevesebbel neveznek meg.

(The smallest number bigger than any finite number named by an expression in the language of first-order set theory with a Googol symbols or less.)

Van ennél formálisabb definíciója is. Ez elfogadták nagyobbnak mint a BB számokat.

Ajánlott videó:

Összehasonlítások

Ezeket az irdatlan nagy számokat nagyon nehéz összehasonlítani, részeredmények viszont vannak. A következőt tudjuk:

Graham(n) < TREE(n) < BB(n) < Rayo(n)

kellően nagy n-re.

  • A Graham sorozat, tehát G1, G2, G3, G4 stb. gyorsabban nő, mint bármelyik $f_N$ tetszőleges véges $N$-re, sőt, még az $f_{\omega}$-nál is gyorsabb, de nem olyan gyors, mint az $f_{\omega+1}$.
  • A TREE sorozat tehát a TREE(1), TREE(2), TREE(3), TREE(4) gyorsabban nő, mint bármelyik $f$ sorozat, beleértve az $f_{\Gamma_0}$-t is. Sőt, annál is gyorsabb lenne, ha ugyanezt folytatnánk egy olyan ábécén, ami Googleplex darab jelet tartalmaz.
  • A TREE(3) nagyobb mint G(64), sőt, a G(G(64))-nél is nagyobb, és még annál is, ahol a G(G(G(…G(G64)…))), ahol a G-k száma G64.
  • BB(16) > G(64)
  • BB(748) > TREE(748)
  • A Rayo-sorozat nagyon nehezen "indul be". Kb. 10-nél éri el az 1-et, 30-nál a 2-t, 56-nál a 3-at stb.
  • Rayo(7339) > BB(265536)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License