グジェゴルチク階層

グジェゴルチク階層（ぐじぇごるちくかいそう、英: Grzegorczyk hierarchy、発音：[ɡʐɛˈɡɔrt͡ʂɨk]）は計算可能性理論に基づく関数の階層である。（Wagner and Wechsung 1986:43）。名称はポーランドの論理学者アンジェイ・グジェゴルチク（英語版）に因む。グジェゴルチク階層に属す任意の関数は原始帰納的関数であり、逆に任意の原始帰納的関数はこの階層のあるレベルに現れる。この階層は関数値の増大の度合いを扱う。直観的にいえば、低い階層の関数はより高い階層の関数よりも緩やかに増加する。

定義

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

E 0 ( x , y ) = x + y {\displaystyle E_{0}(x,y)=x+y}
E 1 ( x ) = x 2 + 2 {\displaystyle E_{1}(x)=x^{2}+2}
E n ( x ) = E n − 1 x ( 2 ) {\displaystyle E_{n}(x)=E_{n-1}^{x}(2)} （ただし n > 1）

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

  1. Ek （ただし k < n）
  2. ゼロ関数 (Z(x) = 0);
  3. 後者関数 (S(x) = x + 1);
  4. 射影関数 ( p i m ( t 1 , t 2 , … , t m ) = t i {\displaystyle p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}} );
  5. （一般）合成関数 （もし h, g1, g2, ... と gm が E n {\displaystyle {\mathcal {E}}^{n}} に属すならば f ( u ¯ ) = h ( g 1 ( u ¯ ) , g 2 ( u ¯ ) , … , g m ( u ¯ ) ) {\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))} も同様）[note 1]; および
  6. 限定（原始）再帰 （もし g, h と j が E n {\displaystyle {\mathcal {E}}^{n}} に属し f ( t , u ¯ ) ≤ j ( t , u ¯ ) {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})} , f ( 0 , u ¯ ) = g ( u ¯ ) {\displaystyle f(0,{\bar {u}})=g({\bar {u}})} , f ( t + 1 , u ¯ ) = h ( t , u ¯ , f ( t , u ¯ ) ) {\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))} ならば、 f もまた E n {\displaystyle {\mathcal {E}}^{n}} に属す)[note 1]

換言すれば E n {\displaystyle {\mathcal {E}}^{n}} は B n = { Z , S , ( p i m ) i ≤ m , E k : k < n } {\displaystyle B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}} を含み関数合成と限定原始再帰で閉じた最小の集合（閉包）である。

性質

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

E 0 ⊆ E 1 ⊆ E 2 ⊆ ⋯ {\displaystyle {\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots }

実際これらは B n {\displaystyle B_{n}} の閉包であって B 0 ⊆ B 1 ⊆ B 2 ⊆ ⋯ {\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots } となっているからである。

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

E 0 ⊊ E 1 ⊊ E 2 ⊊ ⋯ {\displaystyle {\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots }

というのも、ハイパー演算子 H n {\displaystyle H_{n}} は E n {\displaystyle {\mathcal {E}}^{n}} に属すが E n − 1 {\displaystyle {\mathcal {E}}^{n-1}} には属さないからである。

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

原始帰納的関数との関係

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

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

⋃ n E n ⊆ P R {\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}\subseteq PR}

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

⋃ n E n = P R {\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}=PR}

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

拡張

詳細は「急成長階層」を参照

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

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

関連項目

注釈

  1. ^ a b Note: ここで u ¯ {\displaystyle {\bar {u}}} は f への入力のタプルを表す。記法 f ( u ¯ ) {\displaystyle f({\bar {u}})} は f は何らかの任意なアリティを持つ関数であって、 u ¯ = ( x , y , z ) {\displaystyle {\bar {u}}=(x,y,z)} のとき f ( u ¯ ) = f ( x , y , z ) {\displaystyle f({\bar {u}})=f(x,y,z)} を意味する。記法 f ( t , u ¯ ) {\displaystyle f(t,{\bar {u}})} のなかの最初の引数 t は特定の明示的な引数、タプル u ¯ {\displaystyle {\bar {u}}} はその余りであり、 u ¯ = ( x , y , z ) {\displaystyle {\bar {u}}=(x,y,z)} のとき f ( t , u ¯ ) = f ( t , x , y , z ) {\displaystyle f(t,{\bar {u}})=f(t,x,y,z)} を意味する。この記法は関数合成や限定原始再帰で任意のアリティの関数を定義できることを許す。

参考文献

  • Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0
  • Cichon, E. A.; Wainer, S. S. (1983), “The slow-growing and the Grzegorczyk hierarchies”, The Journal of Symbolic Logic 48 (2): 399–408, doi:10.2307/2273557, ISSN 0022-4812, MR704094 
  • 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
  • 表
  • 話
  • 編
  • 歴
実用的な時間で解けるクラス
  • DLOGTIME
  • AC0
  • ACC0
  • TC0
  • L
  • SL
  • RL
  • NL
  • NC
  • SC
  • CC
  • P
    • P完全
  • ZPP
  • RP
  • BPP
  • BQP
  • APX
実用的な時間で解けないと疑われているクラス
実用的な時間では解けないクラス
クラス階層
クラスの族
一覧記事 一覧・カテゴリ カテゴリ