Hardy hierarchie - Hardy hierarchy - Wikipedia

v teorie vypočítatelnosti, teorie výpočetní složitosti a teorie důkazů, Hardy hierarchie, pojmenoval podle G. H. Hardy, je řadová indexovaná rodina funkcí h_α: N → N (kde N je sada přirozená čísla, {0, 1, ...}). Souvisí to s rychle rostoucí hierarchie a pomalu rostoucí hierarchie. Hierarchie byla poprvé popsána v Hardyho dokumentu z roku 1904 „Věta o nekonečných světových číslech“.

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 Hardy hierarchie funkcí h_α: N → N, pro α < μ, je pak definován takto:

${ displaystyle h_ {0} (n) = n,}$
${ displaystyle h _ { alpha +1} (n) = h _ { alpha} (n + 1),}$
${ displaystyle h _ { alpha} (n) = h _ { alpha [n]} (n)}$ pokud α je limitní pořadové číslo.

Zde α [n] označuje n^th prvek základní posloupnosti přiřazený k meznímu pořadovému čísluα. Standardizovaná volba základní posloupnosti pro všechnyα ≤ ε₀ je popsán v článku o rychle rostoucí hierarchie.

Caicedo (2007) definuje modifikovanou Hardyho hierarchii funkcí ${ displaystyle H _ { alpha}}$ pomocí standardních základních sekvencí, ale s α [n+1] (místo α [n]) ve třetím řádku výše uvedené definice.

Vztah k rychle rostoucí hierarchii

The Wainerova hierarchie funkcí F_α a Hardyho hierarchie funkcí h_α jsou ve vztahu F_α = h_ω^α pro všechny α <ε₀. Tedy pro jakékoli α <ε₀, h_α roste mnohem pomaleji než roste F_α. Hardyho hierarchie se však „doháněla“ k Wainerově hierarchii při α = ε₀, takový, že F_ε₀ a h_ε₀ mít stejnou míru růstu v tom smyslu F_ε₀(n-1) ≤ h_ε₀(n) ≤ F_ε₀(n+1) pro všechny n ≥ 1. (Gallier 1991 )

Reference

Hardy, G.H. (1904), „Věta o nekonečných světových číslech“, Quarterly Journal of Mathematics, 35: 87–94
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ů “ (PDF), Ann. Pure Appl. Logika, 53 (3): 199–260, doi:10.1016 / 0168-0072 (91) 90022-E, PAN 1129778. (Zejména oddíl 12, s. 59–64, „Pohled na hierarchie funkcí rychlého a pomalého růstu“.)
Caicedo, A. (2007), "Goodsteinova funkce" (PDF), Revista Colombiana de Matemáticas, 41 (2): 381–391.