Szybko rosnąca hierarchia

Szybko rosnąca hierarchia również znana jako rozszerzona hierarchia Grzegorczyka, stworzona przez matematyka Andrzeja Grzegorczyka. Używana w teorii obliczalności, teorii złożoności obliczeniowej oraz teorii dowodu. Jest to rodzina zbiorów szybko rosnących funkcji $f_{\alpha }\colon \mathbf {N} \to \mathbf {N}$ (gdzie $\mathbf {N}$ jest zbiorem liczb naturalnych $\{0,1,2,\dots \},$ natomiast $\alpha$ jest jakąś liczbą porządkową). Przykładami członków tej rodziny są hierarchia Wainera lub hierarchia Löba-Wainera, które są rozszerzeniem wszystkich $\alpha$ < ε₀. Hierarchie te segregują funkcje obliczalne, bazując na ich tempie wzrostu oraz złożoności obliczeniowej.

Definicja i podstawowa hierarchia Grzegorczyka

Niech $\mu$ będzie dużą liczbą porządkową, taka że dla każdej granicznej liczby porządkowej $\alpha <\mu$ przypisana jest fundamentalna sekwencja (szybko rosnąca sekwencja liczb porządkowych, których supremum jest $\alpha$). Szybko rosnąca hierarchia funkcji $f_{\alpha }\colon \mathbf {N} \to \mathbf {N}$ dla $\alpha <\mu$ zdefiniowana jest następująco:

• $f_{0}(n)=n+1,$
• $f_{\alpha +1}(n)=f_{\alpha }^{n}(n),$
• $f_{\alpha }(n)=f_{\alpha [n]}(n),$ jeśli $\alpha$ jest graniczną liczbą porządkową.

Tutaj $f_{\alpha }^{n}(n)=f_{\alpha }(f_{\alpha }(\dots (f_{\alpha }(n))\dots )),$ określa $n$-tą iterację $f_{\alpha }$ nad argumentem $n,$ natomiast $\alpha [n]$ oznacza $n$-ty element zbioru fundamentalnego przypisanego dla liczby porządkowej $\alpha .$

Początkowa część tej hierarchii, tzn. wszystkie funkcje $f_{\alpha },$ gdzie $\alpha$ jest liczbą naturalną $(\alpha <\omega )$ nazywana jest często podstawową hierarchią Grzegorczyka, gdyż ma z nią wiele wspólnych właściwości:

Hierarchia Grzegorczyka

Zdefiniowane są funkcje $E_{i},$ gdzie $i$ jest liczbą naturalną. Zdefiniowane jest $E_{0}(x,y)=x+y$ i $E_{1}(x)=x^{2}+2$ itd. $E_{0}$ jest funkcją dodawania, $E_{1}$ jest funkcją dwuargumentową, która podnosi parametr do kwadratu, po czym zwiększa wynik o 2. Dla $n$ większych od 1 definiujemy: $E_{n}(x)=E_{n-1}^{x}(2),$ czyli $x$-owa iteracja funkcji $E_{n-1}$ z podanym argumentem 2. Dalej zdefiniowany jest ${\mathcal {E}}^{n},$ który można zapisać jako funkcję $f_{n}$.

Przykłady

Zapis w szybko rosnącej hierarchii	Wartość
$f_{0}(1)$	$1+1=2$
$f_{0}(3)$	$3+1=4$
$f_{1}(3)$	$f_{0}^{3}(3)=f_{0}(f_{0}(f_{0}(3)))=f_{0}(f_{0}(4))=f_{0}(5)=6$
$f_{2}(3)$	$f_{1}^{3}(3)=2\times (2\times (2\times 3))=24$
$f_{3}(3)$	$f_{2}^{3}(3)=f_{2}(f_{2}(2^{3}\times 3))=f_{2}(2^{24}\times 24)=2^{(2^{24}\times 24)}\times 2^{24}\times 24,$ wynik ma ponad 121 milionów cyfr.

Z przykładu numer trzy można wysnuć zasadę: $f_{1}(n)=2n,$ natomiast z przykładu numer cztery $f_{2}(n)=2^{n}n.$

Dla funkcji typu $f_{k}(n)$ można powiedzieć, że wyniki są porównywalne (zazwyczaj większe) do $2\uparrow ^{n-1}n$ co wynika z rekurencji kolejnych funkcji.

Liczby porządkowe do $\varepsilon _{0}$

Pierwszą liczbą porządkową w szybko rosnącej hierarchii jest $\omega$ mająca do siebie przypisany zbiór $\{1,2,3,4,5,\dots \},$ tzn. $\omega [n]=n[n]$ ($n$-ty element zbioru). Przykład: $f_{\omega }(3)=f_{3}(3).$ Funkcja $f_{\omega }(n)$ przewyższa każdą funkcję $f_{i}(n)$ dla $i<n$.

Koleją liczbą porządkową jest $\omega +1,$ czyli zbiór: $\{0,1,2,3,4,\dots \}\cup \{\omega \},$ funkcję z tą liczbą porządkową definiujemy następująco: $f_{\omega +1}(n)=f_{\omega }^{n}(n),$ na przykład $f_{\omega +1}(2)=f_{\omega }(f_{\omega }(2))=f_{\omega }(f_{2}(2))=f_{\omega }(8)=f_{8}(8)>2\uparrow ^{7}8>g(1).$

Dalej jest kolejno: $f_{\omega +2}(n)=f_{\omega +1}^{n}(n),$ np.: $f_{\omega +2}(2)=f_{\omega +1}(f_{\omega +1}(2))=f_{\omega +1}(f_{8}(8))=f_{\omega }^{8}(8)\approx g(f_{8}(8))>G,$ oznacza to, że liczba Grahama wynosi około $f_{\omega +1}(64),$ które jest znacznie mniejsze od $f_{\omega +2}(2).$ Obliczanie kolejnych liczb naturalnych dodanych do $\omega$ przebiega podobnie.

Kolejnym zbiorem jest: $\{\omega +1,\omega +2,\omega +3,\dots ,\omega +\omega \}=\omega 2.$ Obliczanie z użyciem tego zbioru wygląda następująco: $f_{\omega 2}(n)=f_{\omega +n}(n),$ np. $f_{\omega 2}(2)=f_{\omega +2}(2)=f_{\omega }^{8}(8)\approx g(f_{8}(8))>G.$ Kolejnym zbiorem możliwym do utworzenia jest $\omega 3{:}$ $f_{\omega 3}(2)=f_{\omega 2+\omega }(2)=f_{\omega 2+2}(2)=f_{\omega 2+1}^{2}(2)$ itd. Podobnie postępuje się z $\omega 4,$ $\omega 5$ itd.

Następnym zbiorem jest: $\{\omega 1,\omega 2,\omega 3,\dots ,\omega \omega \}=\omega ^{2},$ przykład: $f_{\omega ^{2}}(2)=f_{\omega \omega }(2)=f_{\omega 2}(2).$ Kolejno zamiast 2 można podstawić większe liczby porządkowe: $f_{\omega ^{3}}(2)=f_{\omega ^{2}\times \omega }(2)=f_{\omega ^{2}\times 2}(2)=f_{\omega ^{2}+\omega ^{2}}(2)=f_{\omega ^{2}+\omega +2}(2)=f_{\omega ^{2}+\omega +1}^{2}(2).$

Kolejnym zbiorem jest: $\{\omega ,\omega ^{2},\omega ^{3},\omega ^{4},\dots ,\omega ^{\omega }\}$ będące $\omega ^{\omega }.$ Możliwe jest tworzenie kolejnych zbiorów takich jak $\omega ^{\omega 2},$ $\omega ^{\omega ^{2}},$ $\omega ^{\omega ^{\omega }}.$ Zbiór $\omega ^{\omega ^{\omega ^{\omega ^{\dots }}}}$ jest odpowiednikiem $\varepsilon _{0},$ które jest jednocześnie ostatnią liczbą porządkową Hierarchii Grzegorczyka.

Szacowanie tempa wzrostu funkcji

Każdą obliczalną funkcję można przybliżyć szybką rosnącą hierarchią przy użyciu odpowiednich funkcji. Przykładem może być funkcja Grahama, którą można zapisać jako $g(n)\approx f_{\omega +1}(n),$ funkcja Ackermanna, która rośnie nieco wolniej $Ack(n)\approx f_{\omega }(n),$ czy funkcja Goodsteina, której tempo wzrostu wynosi $\varepsilon _{0}.$

Używając szybko rosnącej hierarchii, można ustalić także górną granicę danej notacji, czyli odpowiadające im miejsce w szybko rosnącej hierarchii, które wyznaczają granicę rekurencyjną danej notacji:

• górna granica notacji strzałkowej i notacji Steinhausa-Mosera to $f_{\omega }(n),$
• górna granica zapisu strzałkowego Conwaya wynosi $f_{\omega ^{2}}(n).$