グジェゴルチク階層

グジェゴルチク階層（Grzegorczyk hierarchy）とは、グジェゴルチクによって1953年に定義された関数の階層である。この階層は関数の集合の無限拡大列 \(\mathcal{F}_0 \subset \mathcal{F}_1 \subset \mathcal{F}_2\subset \cdots \) を成し、それらの和集合 \( \bigcup_{j} \mathcal{F}_j \) は原始再帰関数全体の集合に一致する。グジェゴルチク階層を用いると、原始再帰関数の全体が「部屋分け」されるため、関数の増加速度を見積もるのに役立つことが期待される。 本記事では、グジェゴルチクのオリジナルの定義 \(\{ \mathcal{E}_j\}\) ではなく、『コンピュータと数学』の定義 \( \{\mathcal{F}_j\} \) を中心に解説する。

定義

自然数とは0以上の整数のこととする。n変数関数とはn個の自然数の組 \((x_1,\ldots,x_n)\) に対して自然数 \(f(x_1,\ldots,x_n)\) を返す対応（写像） \(f\) のことであるとする。各自然数 \(j\) に対して、関数の集合 \(\mathcal{F}_j \) を以下で帰納的に定義し、集合列 \(\mathcal{F}_0, \mathcal{F}_1, \mathcal{F}_2,\ldots \) を \( \{\mathcal{F}_j\} \) で表す。

1. ゼロ関数 \(\mathrm{zero}_n(x_1, \ldots, x_n) =0 \), 後者関数 \(\mathrm{suc}(x) = x+1\), 射影関数 \( p_{n,i}(x_1, \ldots, x_n) = x_i \) \( (1\le i \le n) \) は \( \mathcal{F}_j \) に属する。
2. \(f_j(x)\) を急増加関数とするとき、\(f_j^*(n,x)\) は \(\mathcal{F}_{j+1}\) に属する。ただし \(f_j^*(n,x)\) は \(f_j(x)\) の反復関数と呼ばれ、\(f_j^*(n,x) = f_j^{n}(x)\) で定義される。
3. m変数関数 \(g\) とm個のn変数関数 \(g_1, \dots, g_m\) が \(\mathcal{F}_j\) に属するとき、それらの合成関数 \(g \circ (g_1,\ldots, g_m)\) も \(\mathcal{F}_j\) に属する。ただし \(g \circ (g_1,\ldots, g_m)\) はn変数関数であり、\( \big( g \circ (g_1,\ldots, g_m) \big)(x_1,\ldots,x_n)\) \( =g\big(g_1(x_1,\ldots,x_n), \ldots, g_m(x_1,\ldots,x_n)\big) \) で定義される。
4. n変数関数 \(g\), (n+2)変数関数 \(g'\), (n+1)変数関数 \( g' ' \) が \(\mathcal{F}_j\) に属すとき、\(g,g',g' '\) から限定原始再帰法

\(\begin{cases}f(\vec{x}, 0) = g(\vec{x}) \\ f(\vec{x}, y+1) = g'(\vec{x}, y, f(\vec{x},y)) \\ f(\vec{x}, y) \le g' '(\vec{x},y) \end{cases}\) で得られる (n+1)変数関数 \(f\) も \(\mathcal{F}_j\) に属する。ただし、\(\vec{x}=(x_1,\ldots,x_n)\) と表記した。 また上記の1,2,3,4.以外で \(\mathcal{F}_j\) 属すことが分かるもの以外は \(\mathcal{F}_j\) に属さない。

性質

• 各 \(j\) について \(\mathcal{F}_j \subset \mathcal{F}_{j+1}\).
• 各 \(j\) について \(f_{j+1} \in \mathcal{F}_{j+1} \setminus \mathcal{F}_{j} \). よって \( \mathcal{F}_{j+1}\) は \( \mathcal{F}_{j}\) より真に大きい。
• \(\mathcal{F}_j\) の任意の元は原始再帰関数である。逆に、任意の原始再帰関数はある \(\mathcal{F}_j\) に属する。よって、\(\bigcup_j \mathcal{F}_j\) は原始再帰関数全体の集合と一致する。

例

• \(\mathrm{add}(x,y) =x+y\), \(\max(x,y)\) は \(\mathcal{F}_{1} \setminus \mathcal{F}_{0}\) に属する。
• \(\mathrm{mult}(x,y) =xy\), \(\exp(x,y) =x^y\) は \(\mathcal{F}_{2} \setminus \mathcal{F}_{1}\) に属する。
• \(A(n,x)\) をアッカーマン関数とし、\(A_n(x) =A(n,x)\) とおくと、全ての \(j\) について \(A_{j+2}\) は \(\mathcal{F}_{j+1} \setminus \mathcal{F}_{j}\) に属する。

グジェゴルチクのオリジナルの定義

まず、関数の族 \(E_0, E_1, E_2,\ldots \) を次で定める:

\(E_0(x,y)=x+y, \quad E_1(x)=x^2+2, \quad E_n(x)=E^{x}_{n-1}(2) \ (n\ge 2).\)

各自然数 \(j\) に対して、関数の集合 \(\mathcal{E}_j \) を以下で帰納的に定義し、集合列 \(\mathcal{E}_0, \mathcal{E}_1, \mathcal{E}_2,\ldots \) を \( \{\mathcal{E}_j\} \) で表す。

1. ゼロ関数 \(\mathrm{zero}_n(x_1, \ldots, x_n) =0 \), 後者関数 \(\mathrm{suc}(x) = x+1\), 射影関数 \( p_{n,i}(x_1, \ldots, x_n) = x_i \) \( (1\le i \le n) \) は \( \mathcal{E}_j \) に属する。
2. \(E_i\) (\(i<j\)) は全て \(\mathcal{E}_j\) に属する。
3. m変数関数 \(g\) とm個のn変数関数 \(g_1, \dots, g_m\) が \(\mathcal{E}_j\) に属するとき、それらの合成関数 \(g \circ (g_1,\ldots, g_m)\) も \(\mathcal{E}_j\) に属する。
4. n変数関数 \(g\), (n+2)変数関数 \(g'\), (n+1)変数関数 \( g' ' \) が \(\mathcal{E}_j\) に属すとき、\(g,g',g' '\) から限定原始再帰法\(\begin{cases}f(\vec{x}, 0) = g(\vec{x}) \\ f(\vec{x}, y+1) = g'(\vec{x}, y, f(\vec{x},y)) \\ f(\vec{x}, y) \le g' '(\vec{x},y)\end{cases}\)で得られる (n+1)変数関数 \(f\) も \(\mathcal{E}_j\) に属する。
5. 上記以外は \(\mathcal{E}_j\) に属さない。

動画

自然数上の関数を作ろう！ 原始再帰法とグジェゴルチク階層

関連項目

• 急増加関数
• ハーディ階層
• グジェゴルチク数列