急成長階層

在可計算性理論、計算複雜性理論和證明理論中，急成長階層（也稱為擴展Grzegorczyk階層或Schwichtenberg-Wainer階層） 是一類定義域和值域為自然數集，以序數作為索引的函數，即急成長函數f_α: N → N構成的集合（其中N是自然數集 {0, 1, ...}，並且索引 α 的範圍可達某個大的可數序數）。例如：Wainer階層，或Löb–Wainer階層是所有具有索引 α<ε₀ 的急成長函數。

急成長階層提供了一種根據增長率和計算複雜性對可計算函數進行分類的自然方法。

定義

令 μ 為一個大的可數序數，使得對於每個極限序數α<μ，都存在一個基本序列（一個嚴格遞增的序數序列，其上界為α），屬於急成長階層的函數f _α : N → N ，對於 α<μ，定義如下：

• $f_{0}(n)=n+1,$
• $f_{\alpha +1}(n)=f_{\alpha }^{n}(n)$
• $f_{\alpha }(n)=f_{\alpha [n]}(n)$ ，如果 α 是極限序數。

這裡，f_αⁿ(n)=f_α(f_α(...(f_α(n))...)) 為函數f_α以n為起點的第n次迭代；α[n] 表示將基本序列的第n個元素分配給極限序數α。

另一種定義將函數的迭代次數設為n+1，而不是上面第二行中的n。

該層級的初始部分由索引為有限序數（即 α<ω）的函數f_α組成，通常稱為Grzegorczyk階層，因為它與Grzegorczyk 階層密切相關。但請注意，前者是函數f_n的索引族，而後者是函數集的索引族${\mathcal {E}}^{n}$ 。

進一步推廣上述定義，通過將f₀取為任意定義域和值域為自然數集的非減函數 g: N → N來獲得急成長階層。對於不大於ε₀的極限序數，基本序列有一個簡單的自然定義（參見Wainer階層）。但超過ε₀時，定義要複雜得多，然而，急成長階層的定義可能遠遠超出 Feferman-Schütte 序數Γ₀ ，至少達到Bachmann-Howard 序數。使用Buchholz psi 函數，可以將急成長階層的定義擴展到超限迭代的序數$\Pi _{1}^{1}$ -理解（參見層次分析）。

完全確定的超出遞歸序數的擴展被認為不可能；例如，Prӧmel 等人。 [1991]（第 17 頁） 348）指出，在這種嘗試中「問題甚至會出現於序數表示法中」。

Wainer 階層

Wainer階層是通過定義基本序列獲得的函數f_α (α≤ε₀ ) 的特定快速增長層級，如下所示：[Gallier 1991][Prӧmel, et al., 1991]：

對於極限序數 λ<ε₀ ，以康托範式表示，

• 如果 λ=ω^α₁+...+ω^α_k−1+ω^α_k 對於α₁≥...≥α_k−1≥α_k，則 λ[n]=ω^α₁+...+ω^α_k−1+ω^α_k[n],
• 如果 λ=ω^α+1，則 λ[n]=ω^αn，
• 如果 λ=ω^α ，α為極限序數，則 λ[n]=ω^α[n]，

• 如果 λ=ε₀，則取 λ[0]=0 且 λ[n+1]=ω^λ[n]如 [Gallier 1991] 中所述；或者，採用相同的序列，除了以 λ[0]=1 開始，如 [Prӧmel, et al., 1991] 中所示。
  對於n>0，有些版本在生成的指數塔中具有一個附加 ω，即 λ[n]=ω^ω⋰ω，具有n 個ω，或 λ[n]=ω↑↑ω。

一些作者使用略有不同的定義，例如，ω^α+1[n]=ω^α(n+1)，而不是 ω^αn；

有些作者僅針對 α<ε₀定義此層次結構，因此將f_ε0及以上的函數排除在外。

對於索引超出 ε₀ 的函數，請參閱維勃倫層次結構的基本序列。

急成長階層的函數

任何屬於急成長階層的有限索引 (α<ω) 函數與 Grzegorczyk階層的函數一致：（參見超運算）

• f₀(n)=n+1=2[1]n−1
• f₁(n)=f₀ⁿ(n)=n+n=2n=2[2]n
• 對於n≥2，f₂(n)=f₁ⁿ(n)=2ⁿ·n>2ⁿ=2[3]n
• 對於n≥2，k<ω，f_k+1(n)=f_kⁿ(n)>(2[k+1])ⁿn≥2[k+2]n 。

超出有限索引的函數 (ω≤α≤ε₀) 參見Wainer階層：

• 對於n≥4，f_ω(n)=f_n(n)>2[n+1]n>2[n](n+3)−3=A(n,n) ，其中A是阿克曼函數，f_ω是其一元版本。
• 對於所有n>0，f_ω+1(n)=f_ωⁿ(n)≥f_n[n+2]n(n) ，其中n[n+2]n是第 n個阿克曼數。
• f_ω+1(64)=f_ω⁶⁴(64)>葛立恆數=由g₀=4,g_k+1=3[g_k+2]3 定義的序列中的g₆₄。由此可知f_ω(n)>2[n+1]n>3[n]3+2，因此f_ω(g_k+2)>g_k+1+2。
• f_ε0(n) 是 Wainer 階層的第一個增長率超過所有Goodstein 函數的函數。

參見

大數

緩成長階層

來源

• Buchholz, W.; Wainer, S.S (1987). "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics, edited by S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
• Cichon, E. A.; Wainer, S. S., The slow-growing and the Grzegorczyk hierarchies, The Journal of Symbolic Logic, 1983, 48 (2): 399–408, ISSN 0022-4812, JSTOR 2273557, MR 0704094, S2CID 1390729, doi:10.2307/2273557 
• Gallier, Jean H., What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory, Ann. Pure Appl. Logic, 1991, 53 (3): 199–260, MR 1129778, doi:10.1016/0168-0072(91)90022-E   PDF: [1] （頁面存檔備份，存於網際網路檔案館）. (In particular Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
• Girard, Jean-Yves, Π¹₂-logic. I. Dilators, Annals of Mathematical Logic, 1981, 21 (2): 75–219, ISSN 0003-4843, MR 0656793, doi:10.1016/0003-4843(81)90016-4  
• Löb, M.H.; Wainer, S.S. (1970), "Hierarchies of number theoretic functions", Arch. Math. Logik, 13. Correction, Arch. Math. Logik, 14, 1971. Part I doi:10.1007/BF01967649, Part 2 doi:10.1007/BF01973616, Corrections doi:10.1007/BF01991855.
• Prömel, H. J.; Thumser, W.; Voigt, B. "Fast growing functions based on Ramsey theorems", Discrete Mathematics, v.95 n.1-3, p. 341-358, December 1991 doi:10.1016/0012-365X(91)90346-4.
• Wainer, S.S. Slow Growing Versus Fast Growing. Journal of Symbolic Logic. 1989, 54 (2): 608–614. JSTOR 2274873. S2CID 19848720. doi:10.2307/2274873.