急成長階層のソースを表示

'''急成長階層'''（きゅうせいちょうかいそう、{{Lang-en-short|fast-growing hierarchy}}）および'''拡張[[グジェゴルチク階層]]'''（かくちょうグジェゴルチクかいそう、{{Lang-en-short|extended Grzegorczyk hierarchy}}）とは、1970年にマーティン・レーペ（[[:en:Martin Löb|Martin Löb]]）とスタンリー・S・ウェイナーによって定義された<ref>{{Cite journal|last=Löb|first=M. H.|last2=Wainer|first2=S. S.|date=1970-03-01|title=Hierarchies of number-theoretic functions. I|url=https://doi.org/10.1007/BF01967649|journal=Archiv für mathematische Logik und Grundlagenforschung|volume=13|issue=1|pages=39–51|language=en|doi=10.1007/BF01967649|issn=1432-0665}}</ref>、最大 <math>\aleph_{1}</math> 層からなる[[計算可能関数]]の階層である。急成長階層の定義にはいくつかのバージョンがあるが、特にウェイナーが {{Math|''α'' ≦ ''ε''<sub>0</sub>}} の範囲について1972年の論文<ref>{{Cite journal|last=Wainer|first=S. S.|date=1972|title=Ordinal Recursion, and a Refinement of the Extended Grzegorczyk Hierarchy|url=https://www.jstor.org/stable/2272973|journal=The Journal of Symbolic Logic|volume=37|issue=2|pages=281–292|doi=10.2307/2272973|issn=0022-4812}}</ref>で定義し、ケトネンとソロヴェイが簡略化した<ref name=":0">{{Cite journal|last=Ketonen|first=Jussi|last2=Solovay|first2=Robert|date=1981|title=Rapidly Growing Ramsey Functions|url=https://www.jstor.org/stable/2006985|journal=Annals of Mathematics|volume=113|issue=2|pages=267–314|doi=10.2307/2006985|issn=0003-486X}}</ref>バージョンを'''ウェイナー階層'''（{{Lang-en-short|Wainer hierarchy}}）と呼ぶ<ref>{{Cite journal|date=1991-12-03|title=Fast growing functions based on Ramsey theorems|url=https://www.sciencedirect.com/science/article/pii/0012365X91903464|journal=Discrete Mathematics|volume=95|issue=1-3|pages=341–358|language=en|doi=10.1016/0012-365X(91)90346-4|issn=0012-365X}}</ref>。 

急成長階層の定義に登場する、可算な[[順序数]]で添字づけられた計算可能関数の族 <math>\{f_\alpha\}_{\alpha<\tau}</math>（{{Math|''τ''}} は適当な極限順序数）を'''急増加関数'''と呼ぶ。 

== 定義 ==
以下の関数 {{Math|''f''<sub>''α''</sub>}} の定義はケトネンとソロヴェイの論文<ref name=":0" />による。極限順序数 {{Math|''α''}} の基本列とは、自然数で添え字づけられた順序数の単調増加列 {{Math|{''α''<sub>''n''</sub>}<sub>''n'' < ''ω''</sub>}} であって {{Math|''α''}} に収束するものである。

極限順序数 {{Math|''α'' (≦ ''ε''<sub>0</sub>)}} と自然数 {{Mvar|n}} に対して {{Math|''α''[''n'']}} を以下で定義する：

* {{Math|''α''}} が <math>\alpha=\omega^{\beta+1}\cdot(\gamma+1)</math> と書ける場合、<math>\alpha[n]=\omega^{\beta+1}\cdot\gamma+\omega^{\beta}\cdot n</math>。
* {{Math|''α''}} が <math>\alpha=\omega^{\beta}\cdot(\gamma+1)</math> （{{Math|''β''}} は極限順序数）と書ける場合、<math>\alpha[n]=\omega^{\beta}\cdot\gamma+\omega^{\beta[n]}</math>。
* {{Math|1=''α'' = ''ε''<sub>0</sub>}} の場合、<math>\alpha[0]=1,\ \alpha[n+1]=\omega^{\alpha[n]}</math>。

順序数 {{Math|''α'' (≦ ''ε''<sub>0</sub>)}} に対して、自然数上の関数 <math>f_{\alpha}:\mathbb{N}\to \mathbb{N}</math> を次のように定義する：

* <math>f_{0}(n)=n+1</math>
* <math>f_{\alpha+1}(n)=f_{\alpha}^{1+n}(n)</math>
* <math>f_{\alpha}(n)=f_{\alpha[n]}(n)</math>　（{{Math|''α''}} が極限順序数の場合）

ただし {{Math|''n'' > 0}} に対して<math>f^n_\alpha(n)=\underbrace{ f_\alpha(f_\alpha(\dots(f_\alpha(n))\dots)) }_{n}</math>とする。

計算可能関数の集合 <math>\mathcal{F}_{\alpha}</math>は、{{Math|''f''<sub>''α''</sub>}} を含み、ゼロ関数・[[後者関数]]・射影関数・[[関数の合成]]・限定再帰で閉じた最小の集合として定義される（[[グジェゴルチク階層]]も参照）。

== 他の巨大数の表記法との比較 ==
* ''f<sub>0</sub>''(n)=n+1
*''f<sub>1</sub>''(n)=''f<sub>0</sub><sup>n</sup>''(n)=n+(1·n)=2n
*''f<sub>2</sub>''(n)=''f<sub>1</sub><sup>n</sup>''(n)=2(2(...2(n)...))=2<sup>n</sup>n>2↑n ([[クヌースの矢印表記]] を参照)
*''f<sub>3</sub>''(n)=''f<sub>2</sub><sup>n</sup>''(n)>2↑↑n
*''f<sub>ω</sub>''(n)=''f<sub>n-1</sub><sup>n</sup>''(n)>2 ↑<sup>n-1</sup> n ≒ {n,n,n-1} ([[配列表記]]・[[BEAF]] を参照)

== 関連項目 ==
* [[巨大数]]
* [[順序数]]
* [[ハーディ階層]]
* [[緩成長階層]]

== 参考文献 ==
<references />
{{Math-stub}}
{{巨大数}}
[[Category:巨大数]]
[[Category:計算可能性理論]]
[[Category:証明論]]
[[Category:数学に関する記事]]
{{DEFAULTSORT:きゆうせいちようかいそう}}