Hızlı büyüyen hiyerarşi - Fast-growing hierarchy

İçinde hesaplanabilirlik teorisi, hesaplama karmaşıklığı teorisi ve kanıt teorisi, bir hızlı büyüyen hiyerarşi (ayrıca bir Genişletilmiş Grzegorczyk hiyerarşisi), hızla artan işlevlerin sıralı indeksli bir ailesidir f_α: N → N (nerede N kümesidir doğal sayılar {0, 1, ...} ve α bazı büyük sayılabilir değerlere kadar değişir sıra ). Birincil örnek, Wainer hiyerarşisiveya Löb-Wainer hiyerarşisi, tüm α ε₀. Bu tür hiyerarşiler, sınıflandırmanın doğal bir yolunu sağlar. hesaplanabilir işlevler büyüme oranına göre ve hesaplama karmaşıklığı.

Tanım

Μ bir büyük sayılabilir sıra her biri için sıra sınırı α <μ bir temel sıra (supremumu α olan, kesinlikle artan sıra sırası). Bir hızlı büyüyen hiyerarşi fonksiyonların f_α: N → N, α <μ için aşağıdaki gibi tanımlanır:

${ displaystyle f_ {0} (n) = n + 1,}$
${ displaystyle f _ { alpha +1} (n) = f _ { alpha} ^ {n} (n),}$
${ displaystyle f _ { alfa} (n) = f _ { alfa [n]} (n)}$ α bir limit ordinal ise.

Buraya f_αⁿ(n) = f_α(f_α(...(f_α(n)) ...)), n^inci yinelemesi f_α uygulanan nve α [n] gösterir n^inci α sınırına atanan temel dizinin elemanı. (Alternatif bir tanım, yinelemelerin sayısını alır nYerine +1 n, yukarıdaki ikinci satırda.)

Bu hiyerarşinin işlevleri içeren ilk bölümü f_α ile sonlu indeks (yani, α <ω), genellikle Grzegorczyk hiyerarşisi ile yakın ilişkisi nedeniyle Grzegorczyk hiyerarşisi; Bununla birlikte, ilki burada indekslenmiş bir işlev ailesi olduğuna dikkat edin f_nikincisi ise indekslenmiş bir ailedir setleri fonksiyonların ${ displaystyle { mathcal {E}} ^ {n}}$ . (Aşağıdaki İlgi Çekici Noktalara bakın.)

Yukarıdaki tanımı daha da genelleştirerek, a hızlı yineleme hiyerarşisi alınarak elde edilir f₀ herhangi bir artan işlev g: N → N.

Şundan büyük olmayan sıra sıra limitleri için ε₀ temel dizilerin basit bir doğal tanımı vardır (bkz. Wainer hiyerarşisi aşağıda), ancak ötesinde ε₀ tanım çok daha karmaşıktır. Ancak bu, Feferman-Schütte sırasının çok ötesinde mümkündür. Γ₀, en azından Bachmann-Howard sıralı. Kullanma Buchholz psi fonksiyonları bu tanım kolayca sonsuz yinelenen ordinaline genişletilebilir ${ displaystyle Pi _ {1} ^ {1}}$ anlayış (bkz. Analitik hiyerarşi ).

Tam olarak belirtilmiş bir uzantı özyinelemeli sıra sayıları olası olmadığı düşünülmektedir; ör. Prӧmel et al. [1991] (s. 348), böyle bir girişimde "sıralı gösterimde sorunlar bile ortaya çıkacağını" not eder.

Wainer hiyerarşisi

Wainer hiyerarşisi hızlı büyüyen özel işlev hiyerarşisidir f_α (α ≤ ε₀ ) aşağıdaki gibi temel dizilerin tanımlanmasıyla elde edilir [Gallier 1991] [Prӧmel, vd., 1991]:

Limit sıraları için λ < ε₀, yazılmış Kantor normal formu,

eğer λ = ω^α₁ + ... + ω^{α_{k − 1}} + ω^α_k α için₁ ≥ ... ≥ α_{k − 1} ≥ α_k, sonra λ [n] = ω^α₁ + ... + ω^{α_{k − 1}} + ω^α_k[n],
eğer λ = ω^{α + 1}, sonra λ [n] = ω^αn,
eğer λ = ω^α bir limit ordinal α için, sonra λ [n] = ω^{α [n]},

ve

eğer λ = ε₀, λ [0] = 0 ve λ [n + 1] = ω^{λ [n]} [Gallier 1991] 'de olduğu gibi; alternatif olarak, [Prӧmel, et al., 1991] 'de olduğu gibi A [0] = 1 ile başlamak dışında aynı sırayı alın.
İçin n > 0 ise, alternatif versiyon sonuçta ortaya çıkan üstel kulede bir ek ω'ye sahiptir, yani λ [n] = ω^{ω^{.^{.^{.^ω}}}} ile n omegas.

Bazı yazarlar biraz farklı tanımlar kullanır (örneğin, ω^{α + 1}[n] = ω^α(n + 1) yerine ω^αn) ve bazıları bu hiyerarşiyi yalnızca α <ε₀ (dolayısıyla hariç f_ε₀ hiyerarşiden).

Ötesine devam etmek için ε₀bakın Veblen hiyerarşisi için temel diziler.

İlgi noktaları

Hızla büyüyen hiyerarşilerle ilgili bazı ilgi çekici noktalar aşağıdadır:

Her f_α bir toplam işlev. Temel diziler hesaplanabilirse (örneğin, Wainer hiyerarşisinde olduğu gibi), o zaman her f_α toplam hesaplanabilir işlev.
Wainer hiyerarşisinde, f_α hakimdir f_β eğer α <β. (Herhangi iki işlev için f, g: N → N, f söylendi hakim olmak g Eğer f(n) > g(n) yeterince büyük herkes için nAynı özellik, sözde karşılayan temel dizilerle hızlı büyüyen herhangi bir hiyerarşide de geçerlidir. Bachmann özelliği. (Bu özellik, çoğu doğal kuyu sıralaması için geçerlidir.)^{[açıklama gerekli ]}
Grzegorczyk hiyerarşisinde her biri ilkel özyinelemeli işlev bazılarının hakimiyeti altında f_α α <ω ile. Bu nedenle, Wainer hiyerarşisinde, her ilkel özyinelemeli işlev, f_ω, bir çeşidi olan Ackermann işlevi.
İçin n ≥ 3, set ${ displaystyle { mathcal {E}} ^ {n}}$ içinde Grzegorczyk hiyerarşisi Yeterince büyük argümanlar için, bazı sabit yinelemeler tarafından sınırlanan zaman içinde hesaplanabilen toplam çoklu argüman işlevlerinden oluşur. f_n-1^k maksimum argümanda değerlendirilir.
Wainer hiyerarşisinde her biri f_α α ε₀ hesaplanabilir ve kanıtlanabilir şekilde toplam Peano aritmetiği.
Peano aritmetiğinde kanıtlanabilir şekilde toplam olan her hesaplanabilir işlev, bazılarının hakimiyetindedir. f_α α ε₀ Wainer hiyerarşisinde. Bu nedenle f_ε₀ Wainer hiyerarşisinde Peano aritmetiğinde kanıtlanabilir bir bütün değildir.
Goodstein işlevi yaklaşık olarak aynı büyüme oranına sahiptir (yani her birine diğerinin bazı sabit yinelemeleri hakimdir) f_ε₀ Wainer hiyerarşisinde f_α bunun için α < ε₀ ve bu nedenle Peano Aritmetiğinde kanıtlanabilir bir şekilde toplam değildir.
Wainer hiyerarşisinde, eğer α <β < ε₀, sonra f_β bazı sabit yinelemelerle sınırlandırılmış zaman ve alan içindeki her hesaplanabilir işleve hakimdir f_α^k.
Friedman'ın AĞACI fonksiyon hakimdir f_Γ₀ Gallier (1991) tarafından tanımlanan hızlı büyüyen bir hiyerarşide.
Wainer işlev hiyerarşisi f_α ve Hardy hiyerarşisi fonksiyonların h_α ile ilgilidir f_α = h_ω^α hepsi için α <ε₀. Hardy hiyerarşisi, α = ε'deki Wainer hiyerarşisine "yetişir"₀, öyle ki f_ε₀ ve h_ε₀ aynı büyüme oranına sahip f_ε₀(n-1) ≤ h_ε₀(n) ≤ f_ε₀(n+1) hepsi için n ≥ 1. (Gallier 1991)
Girard (1981) ve Cichon & Wainer (1983), yavaş büyüyen hiyerarşi fonksiyonların g_α işlevle aynı büyüme oranına ulaşır f_ε₀ Wainer hiyerarşisinde α olduğunda Bachmann-Howard sıralı. Girard (1981) ayrıca, yavaş büyüyen hiyerarşinin g_α aynı büyüme oranına ulaşır f_α (belirli bir hızlı büyüyen hiyerarşide) α teorinin ordinali olduğunda İD_<ω endüktif bir tanımın keyfi sonlu yinelemeleri. (Wainer 1989)

Hızlı büyüyen hiyerarşilerdeki işlevler

Herhangi bir hızlı büyüyen hiyerarşinin sonlu seviyelerindeki (α <ω) işlevler, Grzegorczyk hiyerarşisininkilerle çakışır: (kullanarak aşırı operasyon )

f₀(n) = n + 1 = 2 [1] n − 1
f₁(n) = f₀ⁿ(n) = n + n = 2n = 2 [2] n
f₂(n) = f₁ⁿ(n) = 2ⁿ · n > 2ⁿ = 2 [3] n için n ≥ 2
f_k+1(n) = f_kⁿ(n) > (2 [k + 1])ⁿ n ≥ 2 [k + 2] n için n ≥ 2, k <ω.

Sonlu seviyelerin ötesinde, Wainer hiyerarşisinin işlevleri vardır (ω ≤ α ≤ ε₀):

f_ω(n) = f_n(n) > 2 [n + 1] n > 2 [n] (n + 3) − 3 = Bir(n, n) için n ≥ 4, nerede Bir ... Ackermann işlevi (olan f_ω tek versiyondur).
f_{ω + 1}(n) = f_ωⁿ(n) ≥ f_{n [n + 2] n}(n) hepsi için n > 0, nerede n [n + 2] n ... n^inci Ackermann numarası.
f_{ω + 1}(64) > f_ω⁶⁴(6) > Graham'ın numarası (= g₆₄ tarafından tanımlanan sırayla g₀ = 4, g_k+1 = 3 [g_k + 2] 3). Bunu not ederek izler f_ω(n) > 2 [n + 1] n > 3 [n] 3 + 2 ve dolayısıyla f_ω(g_k + 2) > g_k+1 + 2.
f_ε₀(n), Wainer hiyerarşisinde egemen olan ilk işlevdir. Goodstein işlevi.

Referanslar

Buchholz, W .; Wainer, SS (1987). "Sağlanabilir Şekilde Hesaplanabilir İşlevler ve Hızla Büyüyen Hiyerarşi". Mantık ve KombinatorikS. Simpson, Contemporary Mathematics, Cilt tarafından düzenlenmiştir. 65, AMS, 179-198.
Cichon, E. A .; Wainer, S. S. (1983), "Yavaş büyüyen ve Grzegorczyk hiyerarşileri", Sembolik Mantık Dergisi, 48 (2): 399–408, doi:10.2307/2273557, ISSN 0022-4812, BAY 0704094
Gallier, Jean H. (1991), "Kruskal teoremi ve sıralı hakkında bu kadar özel olan şey Γ₀? İspat teorisiyle ilgili bazı sonuçların incelenmesi ", Ann. Pure Appl. Mantık, 53 (3): 199–260, doi:10.1016 / 0168-0072 (91) 90022-E, BAY 1129778^{[kalıcı ölü bağlantı ]} PDF: [1]. (Özellikle Bölüm 12, s. 59-64, "Hızlı ve Yavaş Büyüyen İşlevlerin Hiyerarşilerine Bir Bakış".)
Girard, Jean-Yves (1981), "Π¹₂-mantık. I. Dilatörler ", Matematiksel Mantık Yıllıkları, 21 (2): 75–219, doi:10.1016/0003-4843(81)90016-4, ISSN 0003-4843, BAY 0656793
Löb, M.H .; Wainer, S.S. (1970), "Sayı teorik fonksiyonlarının hiyerarşileri", Arch. Matematik. Logik, 13. Düzeltme, Arch. Matematik. Logik, 14, 1971. Bölüm I doi:10.1007 / BF01967649, Bölüm 2 doi:10.1007 / BF01973616, Düzeltmeler doi:10.1007 / BF01991855.
Prömel, H. J .; Thumser, W .; Voigt, B. "Ramsey teoremlerine dayalı hızlı büyüme fonksiyonları", Ayrık Matematik, cilt 95 n.1-3, s. 341-358, Aralık 1991 doi:10.1016 / 0012-365X (91) 90346-4.
Wainer, S.S (1989). "Hızlı Büyümeye Karşı Yavaş Büyüyen". Journal of Symbolic Logic. 54 (2): 608–614. JSTOR 2274873.