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

関数の再帰的定義

ここではある形の関数の再帰的定義について考えます。

$g: X \to X$ に対して $g^+: \mathbb{N} \times X \to \mathbb{N} \times X$ を $g^+(n, x) = (n+1, f(x))$ と定義します。

$\mathcal{S}(g^+, (n, x)) = \{ S \mid S \subseteq \mathbb{N} \times X, (n, x) \in S, g^+(S) \subseteq S \}$ 、 $\overline{g^+}(n, x) = \bigcap \mathcal{S}(g^+, (n, x))$ とおきます。

$\mathcal{S}_0 = \mathcal{S}(g^+, (0, a))$ 、 $R = \overline{g^+}(0, a) = \bigcap \mathcal{S}_0$ とおくと $R$ は
$\begin{cases} (0, a) \in R \\ (n, x) \in R \implies (n+1, g(x)) \in R \end{cases}$
を満たす最小の集合となります。

$S \subseteq \mathbb{N} \times X$ に対して $\pi_1(S) = \{ n \in \mathbb{N} \mid (n, x) \in S \ \text{を満たす} \ x \in X \ \text{が存在する}\}$ と定義します。

$R_1 = \pi_1(R)$ とおくと
$\begin{cases} 0 \in R_1 \\ n \in R_1 \implies n+1 \in R_1 \end{cases}$
が成り立つので、自然数の性質より $R_1 = \mathbb{N}$ となります。

計算可能性の議論にはこれだけでも良いとは思うのですが
$f(n) = x \iff (n, x) \in R$
によって関数 $f: \mathbb{N} \to X$ を定義するには、任意の $n \in \mathbb{N}$ と任意の $x, y \in X$ に対して $(n, x) \in R$ かつ $(n, y) \in R$ ならば $x = y$ が成り立つ必要があります。以下でこれを示します。

$\{(0, a)\} \cup \overline{g^+}(g^+(0, a)) \in \mathcal{S}_0$ となるので $R \subseteq \{(0, a)\} \cup \overline{g^+}(g^+(0, a))$ となります。

$(0, x) \in R$ とすると $(0, x) \notin \overline{g^+}(g^+(0, a))$ なので $(0, x) \in \{(0, a)\}$ となります。よって $x = a$ となります。

よって $n = 0$ のときには成り立ちます。

次に $n$ のときには成り立つと仮定します。 $(n, b) \in R$ とします。

$R_n = \{(k, x) \in R \mid k \le n\}$ 、 $c = g(b)$ とおくと $(n+1, c) \in R$ となります。

$R_n \cup \{(n+1, c)\} \cup \overline{g^+}(g^+(n+1, c)) \in \mathcal{S}_0$ となるので $R \subseteq R_n \cup \{(n+1, c)\} \cup \overline{g^+}(g^+(n+1, c))$ となります。

$(n+1, x) \in R$ とすると $(n+1, x) \notin R_n \cup \overline{g^+}(g^+(n+1, c))$ なので $(n+1, x) \in \{(n+1, c)\}$ となります。よって $x = c$ となって $n+1$ のときにも成り立ちます。

よって帰納法により任意の $n \in \mathbb{N}$ と任意の $x, y \in X$ に対して $(n, x) \in R$ かつ $(n, y) \in R$ ならば $x = y$ が成り立ちます。よって
$f(n) = x \iff (n, x) \in R$
によって関数 $f: \mathbb{N} \to X$ を定義することができます。