グジェゴルチク階層のソースを表示

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

== 定義 ==

まず自然数 ''i'' で添字付けられた関数族 ''E<sub>i</sub>'' を導入する。まず次のように定義する：
:<math>E_0(x,y)=x+y</math>
:<math>E_1(x)=x^2+2</math>
:<math>E_n(x)=E^{x}_{n-1}(2)</math> （ただし n > 1）

これらの関数からグジェゴルチク階層を定義する。<math>\mathcal{E}^n</math> は ''n''番目の階層であり、次の関数からなる：
# ''E<sub>k</sub>'' （ただし ''k'' < ''n''）
# ゼロ関数 (''Z''(''x'') = 0);
# 後者関数 (''S''(''x'') = ''x'' + 1);
# 射影関数 (<math> p_i^m(t_1, t_2, \dots, t_m) = t_i </math>);
# （一般）[[写像の合成|合成関数]] （もし ''h'', ''g''<sub>1</sub>, ''g''<sub>2</sub>, ... と ''g''<sub>m</sub> が<math>\mathcal{E}^n</math> に属すならば <math> f(\bar{u}) = h(g_1(\bar{u}), g_2(\bar{u}), \dots, g_m(\bar{u})) </math> も同様）<ref group=note name="tuple notation"/>; および
# 限定（原始）再帰 （もし ''g'', ''h'' と ''j'' が <math>\mathcal{E}^n</math> に属し <math>f(t, \bar{u}) \leq j(t, \bar{u})</math>, <math>f(0, \bar{u}) = g(\bar{u})</math>, <math>f(t+1, \bar{u}) = h(t,\bar{u},f(t,\bar{u}))</math> ならば、 ''f'' もまた <math>\mathcal{E}^n</math> に属す)<ref group=note name="tuple notation"/>

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

== 性質 ==

これらの集合は明らかに階層を成す。
:<math> \mathcal{E}^0 \subseteq \mathcal{E}^1 \subseteq \mathcal{E}^2 \subseteq \cdots </math>
実際これらは <math>B_n</math> の閉包であって <math> B_0 \subseteq B_1 \subseteq B_2 \subseteq \cdots</math> となっているからである。

これらは強い意味での包含関係が成り立つ（Rose 1984; Gakwaya 1997）。換言すれば
:<math> \mathcal{E}^0 \subsetneq \mathcal{E}^1 \subsetneq \mathcal{E}^2 \subsetneq \cdots </math>
というのも、[[ハイパー演算子]] <math>H_n</math> は <math>\mathcal{E}^n</math> に属すが <math>\mathcal{E}^{n-1}</math> には属さないからである。

*<math>\mathcal{E}^0</math> は次を含む： ''x''+1, ''x''+2, ... 
*<math>\mathcal{E}^1</math> は全ての加法関数を備える： ''x''+''y'', 4''x'', ...
*<math>\mathcal{E}^2</math> は全ての乗法関数を備える： ''xy'', ''x''<sup>4</sup>, ...
*<math>\mathcal{E}^3</math> は全ての指数関数を備える： ''x''<sup>''y''</sup>, 2<sup>2<sup>2<sup>''x''</sup></sup></sup> さらにこの階層は[[ELEMENTARY|初等帰納的関数]]のクラスや反復指数時間で計算可能な関数のクラスなどと一致する
*<math>\mathcal{E}^4</math> は全ての[[テトレーション]]関数を備える。

== 原始帰納的関数との関係 ==

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

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

さらに全ての原始帰納的関数が何れかの階層に属すことも示される（Rose 1984; Gakwaya 1997）。つまり
:<math> \bigcup_n{\mathcal{E}^n} = PR </math>
また <math> \mathcal{E}^0, \mathcal{E}^1 - \mathcal{E}^0, \mathcal{E}^2 - \mathcal{E}^1, \dots, \mathcal{E}^n - \mathcal{E}^{n-1}, \dots </math> は原始帰納的関数のクラス ''PR'' の[[集合の分割|分割]]となっている。さらに各々の領域は潰れていない。

== 拡張 ==
{{main|急成長階層}}

グジェゴルチク階層は[[順序数|超限順序数]]に一般化できる。そのような拡張として[[急成長階層]]が定義される。それには、極限順序数に対する生成関数 <math>E_\alpha</math> を帰納的に定義しなければならない（後続型順序数に対しては <math> E_{\alpha+1}(n) = E_\alpha^n(2) </math> とすればよい。) もし[[順序数#後続順序数と極限順序数|極限順序数]] <math>\lambda</math> の'''基本列''' <math>\lambda_m</math> を作る一般的な方法があれば、 生成関数は <math> E_\lambda(n) = E_{\lambda_n}(n) </math> と定義できる。ところがこの定義は基本列を作る方法に依存する。Rose（1984）は任意の順序数 &alpha; < [[エプシロン・ノート|&epsilon;<sub>0</sub>]] に対する基本列の一般的な構成法を提案した。

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

== 関連項目 ==
*[[原始帰納的関数]]
*[[ELEMENTARY|初等帰納的関数]]
*[[ループプログラム]]
*[[急成長階層]]

== 注釈 ==
{{reflist|group=note|refs=

<ref name="tuple notation">Note: ここで <math>\bar{u}</math> は ''f'' への入力の[[タプル]]を表す。記法 <math>f(\bar{u})</math> は ''f'' は何らかの任意な[[アリティ]]を持つ関数であって、<math>\bar{u} = (x, y, z)</math> のとき <math>f(\bar{u}) = f(x, y, z)</math> を意味する。記法 <math>f(t, \bar{u})</math> のなかの最初の引数 ''t'' は特定の明示的な引数、タプル <math>\bar{u}</math> はその余りであり、<math>\bar{u} = (x, y, z)</math> のとき <math>f(t, \bar{u}) = f(t, x, y, z)</math> を意味する。この記法は関数合成や限定原始再帰で任意のアリティの関数を定義できることを許す。</ref>

}}

== 参考文献 ==
{{reflist}}

* Brainerd, W.S., Landweber, L.H. (1974), ''Theory of Computation'', Wiley, ISBN 0-471-09585-0
*{{Citation | last1=Cichon | first1=E. A. | last2=Wainer | first2=S. S. | title=The slow-growing and the Grzegorczyk hierarchies | doi=10.2307/2273557 | id={{MathSciNet | id = 704094}} | year=1983 | journal=The Journal of Symbolic Logic | issn=0022-4812 | volume=48 | issue=2 | pages=399–408}}
* Gakwaya, J.–S. (1997), [http://citeseer.ist.psu.edu/gakwaya97survey.html ''A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability'']
* Grzegorczyk, A. (1953), [http://matwbn.icm.edu.pl/ksiazki/rm/rm04/rm0401.pdf ''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

{{複雑性クラス}}

{{デフォルトソート:くしえこるちくかいそう}}
[[Category:計算可能性理論]]
[[Category:計算複雑性理論]]
[[Category:数理論理学的階層]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]