Szybko rosnąca hierarchia

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Hierarchia Grzegorczyka)
Przejdź do nawigacji Przejdź do wyszukiwania

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[edytuj | edytuj kod]

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:

  • 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:

Hierarchia Grzegorczyka[3][4][edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 [edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  1. Buchholz Wainer, Provably Computable Functions and the Fast Growing Hierarchy, 1987.
  2. Schmidt Diana, Built-Up Systems of Fundamental Sequences and Hierarchies of Number-Theoretical Functions.
  3. Unrelated Numbers, PlantStar’s Large Numbers, 2 lutego 2018 [dostęp 2020-04-22] (ang.).
  4. Czego informatycy nauczyli się of Andrzeja Grzegorczyka?, 2012.
  5. a b Cichon E., The slow-growing and the Grzegorczyk hierarchies, The Journal of Symbolic Logic, 1983, ISSN 0022-4812.
  6. a b Jean-Yves Girard, Π12-logic. I. Dilators, Annals of Mathematical Logic, 1981, DOI10.1016/0003-4843(81)90016-4, ISSN 0003-4843.
  7. M.H. Löb, Wainer, Hierarchies of number theoretic functions, 1970, DOI10.1007/BF01967649.
  8. H.J. Prömel, W. Thumser, B. Voigt, Fast growing functions based on Ramsey theorems, Discrete Mathematics, 1991, DOI10.1016/0012-365X(91)90346-4.
  9. The Fast Growing Hierarchy, dostęp 15 marca 2021.