帰納的関数

(サイエンス)

【きのうてきかんすう】

自然数から自然数への関数で、具体的に値を計算するアルゴリズムが存在するもの。
λ記法を使って書くと、

初期関数
- ゼロ関数: $Z = \lambda x[0]$
- 後者関数: $S = \lambda x[x+1]$
- 射影関数 $U_{i}^{n} = \lambda x_1 x_2...x_n [x_i] (1 \leq i \leq n)$
関数の合成
- $f$ :n変数関数、 $g_1,...,g_n$ :m変数関数とする。
- 合成 $f(g_1,...,g_n)$ : $N^m \rightarrow N$ は
- $f(g_1,...,g_n) = \lambda x_1...x_m[f(g_1(x_1,...,x_m),...,g_n(x_1,...,x_m))]$
原始帰納法
- :n変数関数、:n+2変数関数とする。
  - $f(x_1,...,x_n,0) = g(x_1,...,x_n)$
  - $f(x_1,...,x_n,y+1) = h(x_1,...s,x_n,y,f(x_1,...,x_n,y))$
- と再帰的に定義される $f:N^{n+1} \rightarrow N$ をg,hから原始帰納法により定義されたという。
最小化
- $g$ :n+1変数関数とする。
- $f=\lambda x_1,...,x_n[\min \{y \in N|g(x_1,...,x_n,y)=0\}]$
- $m=\min \{y \in N|g(x_1,\ldots,x_n,y)=0\}$ が存在し、尚且つ任意の $y\leq m$ に対して $g(x_1,\ldots,x_n,y)\downarrow$ のとき、そのときに限り $f(x_1,\ldots,x_n)\downarrow$
- によって定義される関数fを、gから最小化により定義されたといい、 $\mu y.g(x_1,\ldots,x_n,y)$ と書く。

1,2,3,4を適用して作られた関数を帰納的関数といい、その中で4の適用が無かったものを原始帰納的関数と呼ぶ。
帰納的関数であれば、whileのみを使ったプログラムで計算が可能である。また、原始帰納的関数であれば、loop(for)のみを使ったプログラムで計算が可能である。
全域帰納的だが原始帰納的でない関数としてアッカーマン関数が例としてしばしば挙げられる。

なお条件3を除いた最小化は一般に帰納的ではない。1-変数帰納的関数 $f(x)$ を考える。ここで次のような関数を考えよう： $g(N,x)=\begin{cases} &1& &\text{if $x\lt N$}& \\ &f(x)-f(x)& &\text{if $x=N$}& \\ &0& &\text{otherwise}& \end{cases}$ これは帰納的関数である。条件3を除いた最小化 $\mu x.g(N,x)$ が帰納的関数だと仮定しよう。もし $\mu x.g(N,x)\neq N$ ならばそのときに限り $f(N)\uparrow$ であるから、これは``停止問題の補問題の半決定手続きが存在する"ことを意味する。停止問題は半決定可能であったから、したがって停止問題は決定可能となるが、これは停止問題の決定不可能性と矛盾する。したがって条件3を除いた最小化 $\mu x.g(N,x)$ は帰納的関数ではない。条件3が上の証明を破綻させることを確認しておこう。もし条件3に従えば、 $f(N)\uparrow$ ならば $\mu x.g(N,x)\uparrow$ であるからそもそも $\mu x.g(N,x)\neq N$ が停止せず、したがって停止問題の補問題も半決定できない。