原始帰納的関数
定義
次の関数を原始帰納的関数という
いくつかの決められた関数は原始帰納的関数である
定数関数$ zero : N^0 \rightarrow N, $ zero() = 0
後者関数$ suc : N \rightarrow N, $ suc(x) = x + 1(xの次の数を返す)
写影関数$ \pi^n_i : N^n \rightarrow N, $ \pi^n_i(x_1, x_2, ..., x_n) = x_i (セレクタ)
原始帰納的関数の合成は原始帰納的関数である
$ g : N^m \rightarrow Nと$ h_i : N^n \rightarrow N (i = 1, 2, ..., m)が原始帰納的関数のとき、$ f : N^n \rightarrow N, f(x_1, x_2, ..., x_n) = g(h_1(x_1, x_2, ..., x_n), ..., h_m(x_1, x_2, ..., x_n))も原始帰納的関数である
原始帰納法による関数の定義
$ g: N^n \rightarrow Nと$ h : N^{n+2} \rightarrow Nが原始帰納的関数のとき、次のように定義した$ f : N^{n+1} \rightarrow Nも原始帰納的関数である
$ f(x_1, x_2, ..., x_n, 0) = g(x_1, x_2, ..., x_n)
$ f(x_1, x_2, ..., x_n, suc(y)) = h(x_1, x_2, ..., x_n, y, f(x_1, x_2, ..., x_n, y))
例
イデアル関数: id(x) = x
定数関数: one() = 1
add2(x) = suc(suc(x)) ←合成
2倍
インクリメント(suc)を2x回すればいい
double(0) = 0
double(suc(x)) = suc(suc(double(x)))
前者関数: pred(suc(y)) = y, pred(0) = 0
足し算
yの数だけ、xをインクリメント(suc)すればいい
add(x, suc(y)) = suc(add(x, y)), add(x, 0) = x
引き算
足し算の逆
sub(x, 0) = x, sub(x, suc(y)) = pred(sub(x, y))
掛け算
mul(x, 0) = 0, mul(x, suc(y)) = add(x, mul(x, y))
max:
max(x, y) = add(sub(x, y), x)
別の方法
max(x, y) = tmp(x, y, sub(x, y)), tmp(x, y, 0) = y, tmp(x, y, d) = x
証明
$ zero, suc, \pi^n_iは計算可能である
計算可能であるということはフローチャートで書ける or whileで表現できるということだから、フローチャートを書いてあげればいい
フローチャートに起こせれば計算可能、ということの意味がよくわかってないkekeho.icon
原始帰納的関数の合成は計算可能である
$ f(x_1, x_2, ..., x_n) = g(h_1(x_1, x_2, ..., x_n), ..., h_m(x_1, x_2, ..., x_n))
これもフローチャートを書いてあげればいい
原始帰納法は計算可能である
$ f(x_1, x_2, ..., x_n, 0) = g(x_1, x_2, ..., x_n)
$ f(x_1, x_2, ..., x_n, suc(y)) = h(x_1, x_2, ..., x_n, y, f(x_1, x_2, ..., x_n, y))
これもフローチャートを書いてあげればいい
その他
原始帰納的関数 $ \sub 計算可能関数 $ \sub 関数
全域的: 入力に対して出力が必ずある
コンピュータが計算する関数は全域的関数とは限らない
部分的: 入力に対して出力がないこともある
https://scrapbox.io/files/6627098218e9e200256d3aea.png
奇数のときには止まらない
全域的で計算可能だが、原始帰納的でない関数もある
$ A(0, y) = suc(y)
$ A(suc(x), 0) = A(x, suc(0))
$ A(suc(x), suc(y)) = A(x, A(suc(x), y))
原始帰納的関数よりかなり計算量を食う
資料
https://www.youtube.com/watch?v=hFivqlna0Xw&t=1s