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^[1]. Jest to rodzina zbiorów szybko rosnących funkcji ${\displaystyle f_{\alpha }\colon \mathbf {N} \to \mathbf {N} }$ (gdzie ${\displaystyle \mathbf {N} }$ jest zbiorem liczb naturalnych ${\displaystyle \{0,1,2,\dots \},}$ natomiast ${\displaystyle \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 ${\displaystyle \alpha }$ < ε₀. Hierarchie te segregują funkcje obliczalne, bazując na ich tempie wzrostu oraz złożoności obliczeniowej^[2].

Definicja i podstawowa hierarchia Grzegorczyka

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

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

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

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

Hierarchia Grzegorczyka^[3][4]

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

Przykłady

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

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

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

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

Koleją liczbą porządkową jest ${\displaystyle \omega +1,}$ czyli zbiór: ${\displaystyle \{0,1,2,3,4,\dots \}\cup \{\omega \},}$ funkcję z tą liczbą porządkową definiujemy następująco: ${\displaystyle f_{\omega +1}(n)=f_{\omega }^{n}(n),}$ na przykład ${\displaystyle 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: ${\displaystyle f_{\omega +2}(n)=f_{\omega +1}^{n}(n),}$ np.: ${\displaystyle 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 ${\displaystyle f_{\omega +1}(64),}$ które jest znacznie mniejsze od ${\displaystyle f_{\omega +2}(2).}$ Obliczanie kolejnych liczb naturalnych dodanych do ${\displaystyle \omega }$ przebiega podobnie.

Kolejnym zbiorem jest: ${\displaystyle \{\omega +1,\omega +2,\omega +3,\dots ,\omega +\omega \}=\omega 2.}$ Obliczanie z użyciem tego zbioru wygląda następująco: ${\displaystyle f_{\omega 2}(n)=f_{\omega +n}(n),}$ np. ${\displaystyle 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 ${\displaystyle \omega 3{:}}$ ${\displaystyle 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 ${\displaystyle \omega 4,}$ ${\displaystyle \omega 5}$ itd.

Następnym zbiorem jest: ${\displaystyle \{\omega 1,\omega 2,\omega 3,\dots ,\omega \omega \}=\omega ^{2},}$ przykład: ${\displaystyle f_{\omega ^{2}}(2)=f_{\omega \omega }(2)=f_{\omega 2}(2).}$ Kolejno zamiast 2 można podstawić większe liczby porządkowe: ${\displaystyle 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: ${\displaystyle \{\omega ,\omega ^{2},\omega ^{3},\omega ^{4},\dots ,\omega ^{\omega }\}}$ będące ${\displaystyle \omega ^{\omega }.}$ Możliwe jest tworzenie kolejnych zbiorów takich jak ${\displaystyle \omega ^{\omega 2},}$ ${\displaystyle \omega ^{\omega ^{2}},}$ ${\displaystyle \omega ^{\omega ^{\omega }}.}$ Zbiór ${\displaystyle \omega ^{\omega ^{\omega ^{\omega ^{...}}}}}$ jest odpowiednikiem ${\displaystyle \varepsilon _{0},}$ które jest jednocześnie ostatnią liczbą porządkową Hierarchii Grzegorczyka^[5][6].

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 ${\displaystyle g(n)\approx f_{\omega +1}(n),}$ funkcja Ackermanna, która rośnie nieco wolniej ${\displaystyle Ack(n)\approx f_{\omega }(n),}$ czy funkcja Goodsteina, której tempo wzrostu wynosi ${\displaystyle \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 ${\displaystyle f_{\omega }(n),}$
• górna granica zapisu strzałkowego Conwaya wynosi ${\displaystyle f_{\omega ^{2}}(n).}$^[9]

Przypisy