Pomalu rostoucí hierarchie - Slow-growing hierarchy

v teorie vypočítatelnosti, teorie výpočetní složitosti a teorie důkazů, pomalu rostoucí hierarchie je řadová indexovaná rodina pomalu se zvyšujících funkcí G_α: N → N (kde N je sada přirozená čísla, {0, 1, ...}). To kontrastuje s rychle rostoucí hierarchie.

Definice

Nechť μ je a velké počitatelné pořadové číslo takové, že a základní posloupnost je přiřazen každému mezní pořadové číslo méně než μ. The pomalu rostoucí hierarchie funkcí G_α: N → N, pro α <μ, je pak definováno takto:

• ${ displaystyle g_ {0} (n) = 0}$
• ${ displaystyle g_ {k + 1} (n) = g_ {k} (n) +1}$
• ${ displaystyle g _ { alpha} (n) = g _ { alpha [n]} (n)}$ pro limitní pořadové α.

Zde α [n] označuje n^th prvek základní posloupnosti přiřazený k limitu ordinální α.

Článek o Rychle rostoucí hierarchie popisuje standardizovanou volbu pro základní posloupnost pro všechny α <ε₀.

Vztah k rychle rostoucí hierarchii

Pomalu rostoucí hierarchie roste mnohem pomaleji než rychle rostoucí hierarchie. Dokonce G_ε0 je ekvivalentní pouze F₃ a G_α dosahuje pouze růstu F_ε0 (první funkce, která Peano aritmetika nemůže dokázat celkový v hierarchii), když α je Bachmann – Howard řadový.^[1][2][3]

Girard však nakonec dokázal, že pomalu rostoucí hierarchie dohání s rychle rostoucím.^[1] Konkrétně existuje pořadové α takové, že pro všechna celá čísla n

G_α(n) < F_α(n) < G_α(n + 1)

kde F_α jsou funkce v rychle rostoucí hierarchii. Dále ukázal, že první α, který platí, je pořadové číslo teorie ID_<ω libovolných konečných iterací indukční definice.^[4] Pro přiřazení základních sekvencí nalezených v ^[2] první shoda nahoru nastane na úrovni ε₀.^[5] U řadových stromů ve stylu Buchholz by se mohlo ukázat, že první shoda nastává dokonce v ${ displaystyle omega ^ {2}}$.

Prodloužení výsledku se ukázalo^[4] podstatně větší ordinály ukazují, že pod ordinálem transfinitně iterovaných je velmi málo ordinálů ${ displaystyle Pi _ {1} ^ {1}}$-pochopení, kde se pomalu a rychle rostoucí hierarchie shodují.^[6]

Pomalu rostoucí hierarchie závisí extrémně citlivě na výběru základních fundamentálních sekvencí.^[5][7][8]

Vztah k přepisování termínů

Cichon poskytl zajímavé spojení mezi pomalu rostoucí hierarchií a délkou odvození pro přepis termínů.^[2]

Reference

• Gallier, Jean H. (1991). „Co je tak zvláštního na Kruskalově větě a ordinálu?“₀? Průzkum některých výsledků v teorii důkazů “. Ann. Pure Appl. Logika. 53 (3): 199–260. doi:10.1016 / 0168-0072 (91) 90022-E. PAN  1129778. PDF: část 1 2 3. (Zejména část 3, oddíl 12, str. 59–64, „Pohled na hierarchie funkcí rychlého a pomalého růstu“.)

Poznámky