原始帰納的関数
primitive recursive function
つまりただの初期関数も原始帰納関数であるし、
初期関数どうしを合成や原始帰納などで組み合わせたものも原始帰納関数である
定義
原始帰納関数から合成で得られるものも原始帰納関数である 原始帰納関数から原始帰納により得られるものは原始帰納関数である 以上から得られるものだけが原始帰納関数である
定理
逆は成り立たない
すなわち、基本プログラムでは計算可能だが、原始帰納的ではない関数が存在する 原始帰納的関数の組み合わせで実用的な関数を作っていく
チャーチ数のようなノリ
whileループのようなものを含む関数
forループのようにループ数の指定があるなら表現できる
参考