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 $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^[2].

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^[3]^[4]

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.^[5] $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}$ ^[6].

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$ ^[7]^[8].

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^[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 $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).$ ^[9]

Przypisy

↑ BuchholzB. Wainer BuchholzB., Provably Computable Functions and the Fast Growing Hierarchy, 1987 .
↑ SchmidtS. Diana SchmidtS., Built-Up Systems of Fundamental Sequences and Hierarchies of Number-Theoretical Functions .
↑ Unrelated Numbers [online], PlantStar’s Large Numbers, 2 lutego 2018 [dostęp 2020-04-22] (ang.).
↑ Czego informatycy nauczyli się of Andrzeja Grzegorczyka? [online], 2012 [dostęp 2020-04-22] [zarchiwizowane z adresu 2020-03-20] .
↑ ^a ^b CichonC. E. CichonC., The slow-growing and the Grzegorczyk hierarchies, The Journal of Symbolic Logic, 1983, ISSN 0022-4812 .
↑ ^a ^b Jean-YvesJ.Y. Girard Jean-YvesJ.Y., Π12-logic. I. Dilators, Annals of Mathematical Logic, 1981, DOI: 10.1016/0003-4843(81)90016-4, ISSN 0003-4843 .
↑ M.H.M.H. Löb M.H.M.H., Wainer, Hierarchies of number theoretic functions, 1970, DOI: 10.1007/BF01967649 .
↑ H.J.H.J. Prömel H.J.H.J., W.W. Thumser W.W., B.B. Voigt B.B., Fast growing functions based on Ramsey theorems, Discrete Mathematics, 1991, DOI: 10.1016/0012-365X(91)90346-4 .
↑ The Fast Growing Hierarchy, dostęp 15 marca 2021.

[1] BuchholzB. Wainer BuchholzB., Provably Computable Functions and the Fast Growing Hierarchy, 1987 .

[2] SchmidtS. Diana SchmidtS., Built-Up Systems of Fundamental Sequences and Hierarchies of Number-Theoretical Functions .

[:2-3] Unrelated Numbers [online], PlantStar’s Large Numbers, 2 lutego 2018 [dostęp 2020-04-22] (ang.).

[4] Czego informatycy nauczyli się of Andrzeja Grzegorczyka? [online], 2012 [dostęp 2020-04-22] [zarchiwizowane z adresu 2020-03-20] .

[:0-5] CichonC. E. CichonC., The slow-growing and the Grzegorczyk hierarchies, The Journal of Symbolic Logic, 1983, ISSN 0022-4812 .

[:1-6] Jean-YvesJ.Y. Girard Jean-YvesJ.Y., Π12-logic. I. Dilators, Annals of Mathematical Logic, 1981, DOI: 10.1016/0003-4843(81)90016-4, ISSN 0003-4843 .

[:3-7] M.H.M.H. Löb M.H.M.H., Wainer, Hierarchies of number theoretic functions, 1970, DOI: 10.1007/BF01967649 .

[8] H.J.H.J. Prömel H.J.H.J., W.W. Thumser W.W., B.B. Voigt B.B., Fast growing functions based on Ramsey theorems, Discrete Mathematics, 1991, DOI: 10.1016/0012-365X(91)90346-4 .

[9] The Fast Growing Hierarchy, dostęp 15 marca 2021.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Langbahn Team – Weltmeisterschaft

Szybko rosnąca hierarchia