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
(gdzie
jest zbiorem liczb naturalnych
natomiast
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
< ε0. Hierarchie te segregują funkcje obliczalne, bazując na ich tempie wzrostu oraz złożoności obliczeniowej[2].
Definicja i podstawowa hierarchia Grzegorczyka
Niech
będzie dużą liczbą porządkową, taka że dla każdej granicznej liczby porządkowej
przypisana jest fundamentalna sekwencja (szybko rosnąca sekwencja liczb porządkowych, których supremum jest
). Szybko rosnąca hierarchia funkcji
dla
zdefiniowana jest następująco:
![{\displaystyle f_{0}(n)=n+1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cfcb0f004d6404cd0f841d84d28cfb00adc876ed)
![{\displaystyle f_{\alpha +1}(n)=f_{\alpha }^{n}(n),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d0e0b771f20aee683770d09a47cf17f08edd4a4)
jeśli
jest graniczną liczbą porządkową.
Tutaj
określa
-tą iterację
nad argumentem
natomiast
oznacza
-ty element zbioru fundamentalnego przypisanego dla liczby porządkowej
Początkowa część tej hierarchii, tzn. wszystkie funkcje
gdzie
jest liczbą naturalną
nazywana jest często podstawową hierarchią Grzegorczyka, gdyż ma z nią wiele wspólnych właściwości:
Zdefiniowane są funkcje
gdzie
jest liczbą naturalną. Zdefiniowane jest
i
itd.[5]
jest funkcją dodawania,
jest funkcją dwuargumentową, która podnosi parametr do kwadratu, po czym zwiększa wynik o 2. Dla
większych od 1 definiujemy:
czyli
-owa iteracja funkcji
z podanym argumentem 2. Dalej zdefiniowany jest
który można zapisać jako funkcję
[6].
Przykłady
Zapis w szybko rosnącej hierarchii | Wartość |
| |
| |
| |
| |
| wynik ma ponad 121 milionów cyfr. |
Z przykładu numer trzy można wysnuć zasadę:
natomiast z przykładu numer cztery
Dla funkcji typu
można powiedzieć, że wyniki są porównywalne (zazwyczaj większe) do
co wynika z rekurencji kolejnych funkcji.
Liczby porządkowe do
Pierwszą liczbą porządkową w szybko rosnącej hierarchii jest
mająca do siebie przypisany zbiór
tzn.
(
-ty element zbioru). Przykład:
Funkcja
przewyższa każdą funkcję
dla
[7][8].
Koleją liczbą porządkową jest
czyli zbiór:
funkcję z tą liczbą porządkową definiujemy następująco:
na przykład
Dalej jest kolejno:
np.:
oznacza to, że liczba Grahama wynosi około
które jest znacznie mniejsze od
Obliczanie kolejnych liczb naturalnych dodanych do
przebiega podobnie.
Kolejnym zbiorem jest:
Obliczanie z użyciem tego zbioru wygląda następująco:
np.
Kolejnym zbiorem możliwym do utworzenia jest
itd. Podobnie postępuje się z
itd.
Następnym zbiorem jest:
przykład:
Kolejno zamiast 2 można podstawić większe liczby porządkowe:
Kolejnym zbiorem jest:
będące
Możliwe jest tworzenie kolejnych zbiorów takich jak
Zbiór
jest odpowiednikiem
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
funkcja Ackermanna, która rośnie nieco wolniej
czy funkcja Goodsteina, której tempo wzrostu wynosi
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:
Przypisy
- ↑ BuchholzB. Wainer BuchholzB., Provably Computable Functions and the Fast Growing Hierarchy, 1987 . Brak numerów stron w książce
- ↑ SchmidtS. Diana SchmidtS., Built-Up Systems of Fundamental Sequences and Hierarchies of Number-Theoretical Functions . Brak numerów stron w książce
- ↑ 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 . Brak numerów stron w książce
- ↑ 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 . Brak numerów stron w książce
- ↑ M.H.M.H. Löb M.H.M.H., Wainer, Hierarchies of number theoretic functions, 1970, DOI: 10.1007/BF01967649 . Brak numerów stron w książce
- ↑ 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 . Brak numerów stron w książce
- ↑ The Fast Growing Hierarchy, dostęp 15 marca 2021.