複数の初期関数を、合成と原始帰納の操作を0回以上適用して得られる全域関数のこと

つまりただの初期関数も原始帰納関数であるし、

初期関数どうしを合成や原始帰納などで組み合わせたものも原始帰納関数である

定義

3つの初期関数は、原始帰納関数である

原始帰納関数から合成で得られるものも原始帰納関数である

原始帰納関数から原始帰納により得られるものは原始帰納関数である

以上から得られるものだけが原始帰納関数である

定理

原始帰納関数は、基本プログラムで計算可能

逆は成り立たない

すなわち、基本プログラムでは計算可能だが、原始帰納的ではない関数が存在する

原始帰納的関数の組み合わせで実用的な関数を作っていく

原始帰納的函数とアッカーマン函数の2章に色々載っている

チャーチ数のようなノリ

原始帰納関数ではないものの例

whileループのようなものを含む関数

forループのようにループ数の指定があるなら表現できる

原始帰納関数はアッカーマン関数より厳密に小さい

参考

『計算論 計算可能性とラムダ計算』 p.14~