アッカーマン関数(2) - エレファント・コンピューティング調査報告

ハイパー演算子

『計算論計算可能性とラムダ計算 (コンピュータサイエンス大学講座)』の「問 1.3.17 (4)」が簡単にはできそうにないので、まず『コンピュータと数学 (現代基礎数学)』の第5章を見ていきます。第5章では「ハイパー演算子」(wikipedia:ハイパー演算子と同様ですが記法は異なります)から関数族の階層を定義しています。この階層は「グジェゴルチク階層」(wikipedia:グジェゴルチク階層、『数学基礎論の応用』*1参照)と同様のものと考えられます(定義は異なります)。この階層から「問 1.3.17 (4)」が得られると考えられます。

定義 5.2.1 自然数 $j$ に対して $h_j: \mathbb{N} \to \mathbb{N}$ を
$\begin{cases} h_0(x) = \mathrm{suc}(x) \\ h_{j+1}(x) = h_j^*(x, x) = h_j^x(x) \\ \end{cases}$
と定義します。ここで
$\mathrm{suc}(x) = x + 1$
$h_j^*(n, x) = h_j^n(x) = \underbrace{h_j(h_j(\cdots(h_j(}_{n 回}x))\cdots))$
を表しています。

補題 5.2.2 任意の自然数 $j, k, x$ に対して

$0 < x$ のとき $h_j^k(x) < h_j^{k+1}(x)$
$h_j^k(x) < h_j^{k}(x+1)$
$0 < x$ のとき $h_j^k(x) \le h_{j+1}^{k}(x)$
$h_j^{kx}(x) \le h_{j+1}^{k}(x)$

が成り立ちます。以下でこれを示します。

(1) $0 < x$ のとき $h_j^k(x) < h_j^{k+1}(x)$

「 $0 < x$ のとき $x < h_j(x)$ 」 (*)ならば主張が成り立ちます。

$j = 0$ のとき $h_0(x) = \mathrm{suc}(x) > x$ なので成り立っています。

$j$ のときに成り立つ(すなわち $x < h_j(x)$ )と仮定すると $x < h_j(x) < h_j^2(x) < h_j^3(x) < \cdots$ となるので
$x < h_j(x) < h_j^2(x) < \cdots < h_j^x(x) = h_{j+1}(x)$
となります。 $0 < x$ なので $x < h_{j+1}(x)$ となって $j + 1$ のときにも成り立ちます。

よって帰納法により(*)が成り立ちます。

(2) $h_j^k(x) < h_j^{k}(x+1)$

$h_0^k(x) = \mathrm{suc}^k(x) = x + k < (x + 1) + k = \mathrm{suc}^{k}(x+1) = h_0^{k}(x+1)$
となるので $j = 0$ のとき成り立ちます。

$h_j^k(x) < h_j^{k}(x+1)$ と仮定すると
$h_{j+1}(x) = h_j^x(x) < h_j^{x}(x+1) < h_j^{x+1}(x+1) = h_{j+1}(x+1)$
となります。よって任意の $x, y$ に対して $x < y$ ならば $h_{j+1}(x) < h_{j+1}(y)$ が成り立ちます。

$h_{j+1}^n(x) < h_{j+1}^n(y)$ と仮定すると $h_{j+1}^{n+1}(x) < h_{j+1}^{n+1}(y)$ が成り立つので任意の $n$ に対して $h_{j+1}^n(x) < h_{j+1}^n(y)$ となります。よって $h_{j+1}^k(x) < h_{j+1}^{k}(x+1)$ となって $j + 1$ のときも成り立ちます。

よって帰納法により主張が成り立ちます。

(3) $0 < x$ のとき $h_j^k(x) \le h_{j+1}^{k}(x)$

(1)より $x < h_j(x) < h_j^2(x) < \cdots < h_j^x(x) = h_{j+1}(x)$
であり $k = 0$ のときは成り立ちます。

$0 < h_j^k(x) \le h_{j+1}^{k}(x)$ と仮定すると $k = 0$ の結果と(2)から
$h_j^{k+1}(x) = h_j(h_j^k(x)) \le h_j(h_{j+1}^{k}(x)) \le h_{j+1}(h_{j+1}^{k}(x)) = h_{j+1}^{k+1}(x)$
となって $k + 1$ のときも成り立ちます。

よって帰納法により主張が成り立ちます。

(4) $h_j^{kx}(x) \le h_{j+1}^{k}(x)$

$k = 0$ のときは明らかに成り立ちます。

$x \le y \le z$ のとき(2)と(1)から
$h_j^{x}(y) \le h_j^{x}(z) \le h_{j}^z(z) = h_{j+1}(z)$
が成り立ちます。

$h_j^{kx}(x) \le h_{j+1}^{k}(x)$ と仮定します。
$h_j^{(k+1)x}(x) = h_j^{x}(h_j^{kx}(x)) \le h_{j+1}(h_{j+1}^{k}(x)) = h_{j+1}^{k+1}(x)$
となって $k + 1$ のときも成り立ち、帰納法により主張が成り立ちます。