急成長階層

急成長階層と拡張グジェゴルチク階層

概要

急成長階層（Fast-Growing Hierarchy）と拡張グジェゴルチク階層（Extended Grzegorczyk Hierarchy）は、計算可能関数の新たな分類を示す数学的構造です。1970年にマーティン・レーペとスタンリー・S・ウェイナーによって提唱され、最大のℵ1層からなる計算可能な関数の特性を詳述しています。この階層の定義は複数存在し、とりわけウェイナー自身が1972年に発表した文献の中でαがε0以下の範囲に基づいたものが重要です。また、ケトネンとソロヴェイによる簡略版はウェイナー階層と呼ばれています。

定義と構造

急成長階層では、可算無限個の順序数でラベル付けされた計算可能な関数の集合が基本となります。これらの関数は急増加関数と総称され、次のように表現されます：

{fα} (α < τ)

ここでτは適当な極限順序数を示します。定義には、極限順序数αに基づく基本列の概念が用いられ、これは自然数で添え字された順序数の単調増加列であり、αに収束します。

極限順序数の定義

極限順序数α(≦ ε0)と任意の自然数nに関して、α[n]は次のように定義されます：

1. αがω^β + 1・(γ + 1)と表される場合は、
α[n] = ω^(β+1)・γ + ω^β・n
2. αがω^β・(γ + 1)と表される場合は、
α[n] = ω^β・γ + ω^β[n]
3. α = ε0の場合は、
α[0] = 1,
α[n + 1] = ω^(α[n])

このように定義された関数fαは、次のように計算されます：

• - f0(n) = n + 1
• - f(α + 1)(n) = fα^1 + n(n)
• - fα(n) = fαn (αが極限順序数の場合)

特に、n>0に対して、fα^n(n)はn回の反復に相当します。

計算可能関数の集合

計算可能関数の集合Fαは、関数fαを含み、ゼロ関数、後者関数、射影関数、関数の合成、制限帰納法について閉じている最小の集合として理解されます。拡張グジェゴルチク階層についても関連があります。

他の巨大数との比較

急成長階層における関数fαの具体例を見ると、次のような関係が成り立ちます：

• - f0(n) = n + 1
• - f1(n) = f0(n) = n + 1·n = 2n
• - f2(n) = f1(n) = 2(2(...2(n)...))
• - f3(n) = f2(n) > 2↑↑n
• - fω(n) = f(n - 1)(n) > 2↑(n - 1)

これにより、急成長階層の関数がどのように急速に増加するかを示しています。特にクヌースの矢印表記や配列表記との比較も行われます。

結論

急成長階層及び拡張グジェゴルチク階層は、計算可能関数の進化を考える上で不可欠な理論的枠組みです。これらの階層を理解することで、計算可能性の限界や巨大数に関する概念についてもより深く踏み込むことが可能となります。このような理論の探求は、数学の奥深さを感じさせてくれます。

もう一度検索