グジェゴルチク階層

グジェゴルチク階層（/ ɡ r ɛ ˈ ɡ ɔːr tʃ ə k /、ポーランド語発音: [ɡʐɛˈɡɔrt͡ʂɨk]）は、ポーランドの論理学者アンジェイ・グジェゴルチクにちなんで名付けられ、計算可能性理論で用いられる関数の階層である。^[1]グジェゴルチク階層のすべての関数は原始再帰関数であり、すべての原始再帰関数は階層のどこかのレベルに現れる。この階層は関数の値の増加率を扱う。直感的には、階層の下位レベルの関数は上位レベルの関数よりもゆっくりと増加していく。

意味

まず、ある自然数iに対してE _iと表記される関数の無限集合を導入する。

${\displaystyle {\begin{array}{lcl}E_{0}(x,y)&=&x+y\\E_{1}(x)&=&x^{2}+2\\E_{n+2}(0)&=&2\\E_{n+2}(x+1)&=&E_{n+1}(E_{n+2}(x))\\\end{array}}}$

${\displaystyle E_{0}}$ は加算関数であり、は引数を2乗して2を加算する単項関数です。そして、1より大きい各nについて、つまりのx回目の反復は2で評価されます。 ${\displaystyle E_{1}}$ ${\displaystyle E_{n}(x)=E_{n-1}^{x}(2)}$ ${\displaystyle E_{n-1}}$

これらの関数から、Grzegorczyk 階層を定義します。階層の n番目のセットには、次の関数が含まれます。${\displaystyle {\mathcal {E}}^{n}}$

1. k < nの場合、E _k
2. ゼロ関数（Z（x）= 0）
3. 後継関数（S（x）= x + 1）
4. 投影関数（）${\displaystyle p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}}$
5. 集合内の関数の（一般化された）合成（ h、g ₁、g ₂、 ... 、g _m が に含まれる場合、 も同様である）^{[注 1]}および${\displaystyle {\mathcal {E}}^{n}}$ ${\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))}$
6. 集合内の関数に限定された（原始的な）再帰を適用した結果（もしg、h、jがに含まれ、かつすべてのtとに対して含まれ、さらにおよび であれば、fも に含まれる）。^{[注 1]}${\displaystyle {\mathcal {E}}^{n}}$ ${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$ ${\displaystyle {\bar {u}}}$ ${\displaystyle f(0,{\bar {u}})=g({\bar {u}})}$ ${\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}$ ${\displaystyle {\mathcal {E}}^{n}}$

言い換えれば、関数合成と限定再帰（上記で定義）に関する 集合の閉包です。${\displaystyle {\mathcal {E}}^{n}}$ ${\displaystyle B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}}$

プロパティ

これらのセットは明らかに階層を形成している

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

これらはおよび の閉包であるためです。 ${\displaystyle B_{n}}$ ${\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots }$

これらは厳密な部分集合である。^{[2] [3]}言い換えれば

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

なぜなら、ハイパー演算は にはあるが にはないからです。 ${\displaystyle H_{n}}$ ${\displaystyle {\mathcal {E}}^{n}}$ ${\displaystyle {\mathcal {E}}^{n-1}}$

• ${\displaystyle {\mathcal {E}}^{0}}$ 次のような機能が含まれます${\displaystyle x+1,\;x+2,\;\ldots }$

のすべての単項関数は、何らかの によって上限が制限されます。${\displaystyle f(x)}$ ${\displaystyle {\mathcal {E}}^{0}}$ ${\displaystyle x+n}$

しかし、より複雑な関数も含まれており、^[4]、^[4]${\displaystyle {\mathcal {E}}^{0}}$ ${\displaystyle x\mathbin {\dot {-}} 1}$ ${\displaystyle x\mathbin {\dot {-}} y}$ ${\displaystyle x{\bmod {y}},\;\ldots }$

• ${\displaystyle {\mathcal {E}}^{1}}$ 次のようなすべての追加機能を提供します。${\displaystyle x+y,\;4x,\;\ldots }$
• ${\displaystyle {\mathcal {E}}^{2}}$ 次のようなすべての乗算関数を提供します。${\displaystyle xy,\;x^{4},\;\ldots }$
• ${\displaystyle {\mathcal {E}}^{3}}$ は、などのすべての指数関数を提供し、 はまさに基本的な再帰関数です。${\displaystyle x^{y},\;2^{2^{2^{x}}}}$
• ${\displaystyle {\mathcal {E}}^{4}}$ すべてのテトレーション関数などを提供します。

注目すべきことに、クリーネ正規形定理の述語の関数と特性関数はどちらも、グジェゴルチク階層のレベルに位置するように定義可能である。これは特に、任意の計算可能列挙可能集合が何らかの -関数によって列挙可能であることを意味する。 ${\displaystyle U}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {E}}^{0}}$ ${\displaystyle {\mathcal {E}}^{0}}$

原始再帰関数との関係

の定義は、原始再帰関数PRの定義と同じですが、再帰が制限され（内の何らかのjに対して）、関数がに明示的に含まれる点が異なります。したがって、Grzegorczyk 階層は、原始再帰の能力を異なるレベルに 制限する方法と見なすことができます。${\displaystyle {\mathcal {E}}^{n}}$ ${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$ ${\displaystyle {\mathcal {E}}^{n}}$ ${\displaystyle (E_{k})_{k<n}}$ ${\displaystyle {\mathcal {E}}^{n}}$

この事実から、Grzegorczyk 階層のどのレベルでもすべての関数は原始再帰関数 (つまり) であり、したがって次の式が成り立つこと がわかります。${\displaystyle {\mathcal {E}}^{n}\subseteq {\mathsf {PR}}}$

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}\subseteq {\mathsf {PR}}}$

また、すべての原始再帰関数は階層構造のどこかのレベルにあることも示されており、^{[2] [3]}したがって

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}={\mathsf {PR}}}$

そして、これらの集合は原始再帰関数の集合PRを分割します。 ${\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 }$

マイヤーとリッチーは、関数を計算するLOOPプログラムを書くために必要なループのネストの深さに基づいて、原始再帰関数を細分化する別の階層を導入した。自然数 に対して、とコマンドがレベル以下のネストを持つLOOPプログラムで計算可能な関数の集合を と表すものとする。 ^[5]ファチーニとマジョーロ＝シェッティーニは、すべての整数に対して が と一致することを示した。^[6]${\displaystyle i}$ ${\displaystyle {\mathcal {L}}_{i}}$ LOOPEND${\displaystyle i}$ ${\displaystyle {\mathcal {L}}_{i}}$ ${\displaystyle {\mathcal {E}}_{i+1}}$ ${\displaystyle i>1}$

拡張機能

Grzegorczyk階層は超限 順序数に拡張できます。このような拡張は急成長階層を定義します。これを行うには、生成関数を極限順序数に対して再帰的に定義する必要があります（関係 によって後続順序数に対して既に再帰的に定義されていることに注意してください）。極限順序数が である基本列を定義する標準的な方法がある場合、生成関数を で定義できます。ただし、この定義は基本列を定義する標準的な方法に依存します。Rose (1984) は、すべての順序数α < ε ₀に対して標準的な方法を提案しています。 ${\displaystyle E_{\alpha }}$ ${\displaystyle E_{\alpha +1}(n)=E_{\alpha }^{n}(2)}$ ${\displaystyle \lambda _{m}}$ ${\displaystyle \lambda }$ ${\displaystyle E_{\lambda }(n)=E_{\lambda _{n}}(n)}$

元々の拡張はマーティン・レーブとスタン・S・ウェイナーによるもので、レーブ・ウェイナー階層と呼ばれることもあります。^[7]

参照

• 初等
• 急速に成長する階層
• 順序分析

注記

1. ここで、 はfへの入力のタプルを表します。 表記は、f が任意の数の引数を取り、 であれば となることを意味します。 表記では、最初の引数tが明示的に指定され、残りは任意のタプル として指定されます。したがって、であればとなります。この表記により、任意の数の引数を持つ関数fに対して、合成と限定再帰を定義できます。${\displaystyle {\bar {u}}}$ ${\displaystyle f({\bar {u}})}$ ${\displaystyle {\bar {u}}=(x,y,z)}$ ${\displaystyle f({\bar {u}})=f(x,y,z)}$ ${\displaystyle f(t,{\bar {u}})}$ ${\displaystyle {\bar {u}}}$ ${\displaystyle {\bar {u}}=(x,y,z)}$ ${\displaystyle f(t,{\bar {u}})=f(t,x,y,z)}$

参考文献

1. Wagner & Wechsung 1986、p. 43.
2. ローズ 1984より。
3. Gakwaya 1997より。
4. ここで、monus関数は次のように定義されます。${\displaystyle \mathbin {\dot {-}} }$ ${\displaystyle x\mathbin {\dot {-}} y=\max(x-y,\,0)}$
5. マイヤー＆リッチー 1967年。
6. ファッキーニとマッジョーロ＝スケッティーニ、1979年、p. 63.
7. ロブ＆ワイナー 1970.

参考文献

• ブレーナード, ウォルター・S.; ランドウェーバー, ローレンス・H. (1974).計算理論. ワイリー. ISBN 9780471095859。

• Cichon, EA; Wainer, SS (1983). 「緩やかな成長とグジェゴルチク階層」. Journal of Symbolic Logic . 48 (2): 399– 408. doi :10.2307/2273557. ISSN  0022-4812. JSTOR  2273557. MR  0704094. S2CID  1390729.

• ファキーニ、エマヌエラ。マッジョーロ＝スケッティーニ、アンドレア (1979)。 「プリミティブ再帰シーケンス関数の階層」(PDF)。RAIRO - Informatique Théorique - 理論情報学。13 (1): 49–67 .土井: 10.1051/ita/1979130100491。

• ジャン＝シルヴェストル・ガクワヤ (1997). 「グジェゴルチク階層の概観とBSS計算可能性モデルによるその拡張」CiteSeerX  10.1.1.69.4621 .

• グジェゴルチク、アンジェイ（1953）。 「再帰関数のいくつかのクラス」(PDF)。ロズプラウィ・マテマティチュネ。4：1～ 45。

• マーティン・ヒューゴ・ロブ;ウェイナー、スタン S. (1970)。 「数論関数の階層 I、II: 修正」。数学ロジックとグルンドラーゲンフォルシュングのアーカイブ。14 ( 3–4 ): 198–199 .土井:10.1007/bf01991855. S2CID  119830535。

• マイヤー、アルバート・R.；リッチー、デニス・マカリスター(1967). ループプログラムの計算量(PDF) . ACM '67: 1967年第22回全国会議議事録. pp.  465– 469. doi :10.1145/800196.806014.

• Rose, HE (1984).部分再帰：関数と階層構造.オックスフォード大学出版局. ISBN 0-19-853189-3。

• Wagner, K.; Wechsung, G. (1986). 「計算複雑性」.数学とその応用. 21. Springer. ISBN 978-90-277-2146-4。