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

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

定義

編輯

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

  •  
  •  
  •   ,如果 α 是極限序數。

這裡,fαn(n)=fα(fα(...(fα(n))...)) 為函數fαn為起點的第n迭代;α[n] 表示將基本序列的第n個元素分配給極限序數α。

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

該層級的初始部分由索引為有限序數(即 α<ω)的函數fα組成,通常稱為Grzegorczyk階層,因為它與Grzegorczyk 階層密切相關。但請注意,前者是函數fn的索引族,而後者是函數的索引族 

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

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

Wainer 階層

編輯

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

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

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

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

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

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

急成長階層的函數

編輯

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

  • f0(n)=n+1=2[1]n−1
  • f1(n)=f0n(n)=n+n=2n=2[2]n
  • 對於n≥2,f2(n)=f1n(n)=2n·n>2n=2[3]n
  • 對於n≥2,k<ω,fk+1(n)=fkn(n)>(2[k+1])nn≥2[k+2]n

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

  • 對於n≥4,fω(n)=fn(n)>2[n+1]n>2[n](n+3)−3=A(n,n) ,其中A阿克曼函數fω是其一元版本。
  • 對於所有n>0,fω+1(n)=fωn(n)≥fn[n+2]n(n) ,其中n[n+2]n第 n阿克曼數
  • fω+1(64)=fω64(64)>葛立恆數=由g0=4,gk+1=3[gk+2]3 定義的序列中的g64。由此可知fω(n)>2[n+1]n>3[n]3+2,因此fω(gk+2)>gk+1+2。
  • fε0(n) 是 Wainer 階層的第一個增長率超過所有Goodstein 函數的函數。

參見

編輯

大數

緩成長階層

參考

編輯
  1. ^ Beklemishev, L.D. Proof-theoretic analysis by iterated reflection. Archive for Mathematical Logic. 2003, 42 (6): 515–552 [2024-03-14]. S2CID 10454755. doi:10.1007/s00153-002-0158-7. (原始內容存檔於2023-05-13). 

來源

編輯