Rychle rostoucí hierarchie ~ fω(n)

Konečně zjistíme, co znamená fx(n), a ukážeme si několik příkladů.

Rychle rostoucí hierarchie se využívá jako měřítko pro ostatní funkce a velká čísla. Jako vstup bere přirozená čísla a index, jenž označuje rekurzivnost, je libovolný přirozený ordinál. Nejdříve si řekneme, co ordinál vůbec je.

Ordinály určují pořadí; odpovídají na otázku "kolikátý?". Číslo 3 jakožto ordinál říká "třetí". Máme-li 3 tečky, ordinál 3 poukazuje na třetí tečku. Pokud sdělujeme početnost, používáme kardinály; ty zase odpoví na "kolik?". Index v rychle rostoucí hierarchii jednoduše označuje, kolikátou rychle rostoucí funkci z rychle rostoucí hierarchie myslíme.

Podle těchto jednoduchých pravidel se řídí rychle rostoucí hierarchie:

f0(n) = n + 1

fα + 1(n) = fnα(n)

fβ(n) = fβ[n](n) je-li β mezní ordinál

------

Možná to vypadá složitě, tudíž to přeložíme do češtiny.

První pravidlo říká, že je-li index 0, funkce vyplyvne následující přirozené číslo. Tu není co řešit.

Druhé pravidlo je již složitější, proto si to raději ukážeme na příkladu:

f2(3) = f31(3)

f31(3) = f1(f1(f1(3)))

------

Zjednodušme f1(3):

f1(3) = f30(3)

f30(3) = f0(f0(f0(3)))

------

Teď užijeme nultého pravidla:

f0(f0(f0(3))) = f0(f0(4))

f0(f0(4)) = f0(5)

f0(5) = 6

------

Teď můžeme náš výsledek dosadit zpátky:

f1(f1(6))

Nyní bychom znovu opakovali postup, ale s 6 opakováními. f1 zdvojnásobuje vstup. Nevěříš-li, zkus si sám rozvinout zbytek. Výsledek tedy je:

f2(3) = 24

------

Poslední pravidlo je nejsložitější a závisí na naší volbě takzvané fundamentální posloupnosti. Prozatím používáme Wainerovu hierarchii ordinálů, o níž si povíme více, až nám nebude stačit. Nyní si ukážeme jednoduchý příklad s prvním nekonečným ordinálem ω.

fω(3) = f3(3)

Co jsme tedy udělali? Vyměnili jsme index za vstupní hodnotu. Toto nám pomůže se odrazit a stvořit první opravdu rekurzivní funkci. Zobecníme tedy:

fω(n) = fn(n)

------

Teď již víme, co je rychle rostoucí hierarchie a podle kterých pravidel se řídí. V další části si s ní pohrajeme a setkáme se tváří v tvář s prvním slavným obrem googologie, Grahamovým číslem.