全域帰納的関数
定義1
②全域帰納的関数から、合成で得られるものは全域帰納的関数である ③全域帰納的関数から、原始帰納で得られるものは全域帰納的関数である ④$ gが全域帰納的関数で
$ (\forall\vec{x}\in\mathbb{N}^k)(\exist y\in\mathbb{N})(g(\vec{x},y)=0)を満たすとき
$ f(\vec{x})=\mu y[g(\vec{x},y)=0] という関数$ fは全域帰納的関数である
⑤ 以上から得られるものだけが全域帰納的関数である
定義2
定義1の方が定義2よりも厳しい
定義1ならば、定義2は成り立つ。逆は自明ではない
環ならば、群、と同じmrsekut.icon
全域帰納的関数であり、原始帰納的関数ではない関数の例
executable'(p, x)
2引数
プログラムのコードp
その引数x
出力
1
ある自然数$ kが存在して、$ pはある$ k入力限定反復プログラムのコードであり、$ xは長さ$ kの自然数列のコードであるとき 0
それ以外
$ pが限定反復プログラムのコードでない場合や、
$ xが$ pの入力の個数に合った長さの自然数列のコードでないとき
comp'(p, x)
2引数
プログラムのコードp
その引数x
出力
y
executable'(x,p)=1であり、$ pが表す限定反復プログラムの入力変数に$ xが表す自然数列の各要素の値をセットして実行開始すると$ yを戻り値として実行が終了するとき
0
それ以外
executable'(p,x)=0であるとき
参考