グジェゴルチク階層

グジェゴルチク階層（ぐじぇごるちくかいそう、テンプレート:Lang-en-short、発音：テンプレート:IPAc-pl）は計算可能性理論に基づく関数の階層である。（Wagner and Wechsung 1986:43）。名称はポーランドの論理学者テンプレート:仮リンクに因む。グジェゴルチク階層に属す任意の関数は原始帰納的関数であり、逆に任意の原始帰納的関数はこの階層のあるレベルに現れる。この階層は関数値の増大の度合いを扱う。直観的にいえば、低い階層の関数はより高い階層の関数よりも緩やかに増加する。

定義

まず自然数 i で添字付けられた関数族 E_i を導入する。まず次のように定義する：

$E_0(x,y)=x+y$

$E_1(x)=x^2+2$

$E_n(x)=E_{n-1}^x(2)$ （ただし n > 1）

これらの関数からグジェゴルチク階層を定義する。${ℰ}^n$ は n番目の階層であり、次の関数からなる：

1. E_k （ただし k < n）
2. ゼロ関数 (Z(x) = 0);
3. 後者関数 (S(x) = x + 1);
4. 射影関数 ($p_i^m(t_1,t_2,\dots ,t_m)=t_i$);
5. （一般）合成関数 （もし h, g₁, g₂, ... と g_m が${ℰ}^n$ に属すならば $f(\overline{u})=h(g_1(\overline{u}),g_2(\overline{u}),\dots ,g_m(\overline{u}))$ も同様）; および
6. 限定（原始）再帰 （もし g, h と j が ${ℰ}^n$ に属し $f(t,\overline{u})\le j(t,\overline{u})$, $f(0,\overline{u})=g(\overline{u})$, $f(t+1,\overline{u})=h(t,\overline{u},f(t,\overline{u}))$ ならば、 f もまた ${ℰ}^n$ に属す)

換言すれば ${ℰ}^n$ は $B_n=\{Z,S,(p_i^m{)}_{i\le m},E_k:k<n\}$ を含み関数合成と限定原始再帰で閉じた最小の集合（閉包）である。

性質

これらの集合は明らかに階層を成す。

${ℰ}^0\subseteq {ℰ}^1\subseteq {ℰ}^2\subseteq \cdots$

実際これらは $B_n$ の閉包であって $B_0\subseteq B_1\subseteq B_2\subseteq \cdots$ となっているからである。

これらは強い意味での包含関係が成り立つ（Rose 1984; Gakwaya 1997）。換言すれば

${ℰ}^0⊊{ℰ}^1⊊{ℰ}^2⊊\cdots$

というのも、ハイパー演算子 $H_n$ は ${ℰ}^n$ に属すが ${ℰ}^{n-1}$ には属さないからである。

• ${ℰ}^0$ は次を含む： x+1, x+2, ...
• ${ℰ}^1$ は全ての加法関数を備える： x+y, 4x, ...
• ${ℰ}^2$ は全ての乗法関数を備える： xy, x⁴, ...
• ${ℰ}^3$ は全ての指数関数を備える： x^y, 2^22x さらにこの階層は初等帰納的関数のクラスや反復指数時間で計算可能な関数のクラスなどと一致する
• ${ℰ}^4$ は全てのテトレーション関数を備える。

原始帰納的関数との関係

${ℰ}^n$ の定義は再帰が限定 （ある j $\in {ℰ}^n$ に対して $f(t,\overline{u})\le j(t,\overline{u})$）されていることと、$(E_k{)}_{k<n}$ が明示的に導入されることを除けば 原始帰納的関数のクラス PR の定義に似ている。グジェゴルチク階層は原始再帰の強さを制限しているものと見ることができる。

この事実からグジェゴルチク階層に属す全ての関数は原始帰納的関数であること（すなわち ${ℰ}^n\subseteq PR$）が示される。したがって

$\bigcup _n{ℰ}^n\subseteq PR$

さらに全ての原始帰納的関数が何れかの階層に属すことも示される（Rose 1984; Gakwaya 1997）。つまり

$\bigcup _n{ℰ}^n=PR$

また ${ℰ}^0,{ℰ}^1-{ℰ}^0,{ℰ}^2-{ℰ}^1,\dots ,{ℰ}^n-{ℰ}^{n-1},\dots$ は原始帰納的関数のクラス PR の分割となっている。さらに各々の領域は潰れていない。

拡張

グジェゴルチク階層は超限順序数に一般化できる。そのような拡張として急成長階層が定義される。それには、極限順序数に対する生成関数 $E_{\alpha }$ を帰納的に定義しなければならない（後続型順序数に対しては $E_{\alpha +1}(n)=E_{\alpha }^n(2)$ とすればよい。) もし極限順序数 $\lambda$ の基本列 ${\lambda }_m$ を作る一般的な方法があれば、 生成関数は $E_{\lambda }(n)=E_{{\lambda }_n}(n)$ と定義できる。ところがこの定義は基本列を作る方法に依存する。Rose（1984）は任意の順序数 α < ε₀ に対する基本列の一般的な構成法を提案した。

独自の拡張としては Martin Löb と Stan S. Wainer（1970）による Löb–Wainer 階層がある。

関連項目

• 原始帰納的関数
• 初等帰納的関数
• ループプログラム
• 急成長階層

参考文献

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0
• テンプレート:Citation
• Gakwaya, J.–S. (1997), A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability
• Grzegorczyk, A. (1953), Some classes of recursive functions, Rozprawy matematyczne, Vol 4, pp. 1–45.
• Löb, M.H. and Wainer, S.S., "Hierarchies of Number Theoretic Functions I, II: A Correction," Arch. Math. Logik Grundlagenforschung 14, 1970 pp. 198–199.
• Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ISBN 0-19-853189-3
• Wagner, K. and Wechsung, G. (1986), Computational Complexity, Mathematics and its Applications v. 21. ISBN 978-90-277-2146-4

テンプレート:複雑性クラス