『C言語による計算の理論』に出てくる関数一覧

p. 40

p.47

入力: 一つの自然数n

出力

nがジャンププログラムのコードなら1

そうでないなら0

計算可能

p.47

pをxに適用できるかどうかを判定する

引数

p: コード

x: コードpの入力

出力

1: pをk入力プログラムのコード、かつ、xは長さkのコード

0: それ以外

pはコードでない

xがpの入力にマッチしていない

計算可能

実装の内部に isCode を用いる

p. 87

引数

プログラムのコード p

その引数 x

出力

1

ある自然数kが存在して、pはあるk入力限定反復プログラムのコードであり、xは長さkの自然数列のコードであるとき

0

それ以外

pが限定反復プログラムのコードでない場合や、

xがpの入力の個数に合った長さの自然数列のコードでないとき

全域帰納的関数であり、原始帰納的関数ではない関数である

アッカーマン関数と同じクラス

p.49

引数

p: ジャンププログラムのコード

x: コードpの入力

出力

p(x)

executable(p,x) == 1 であり

p(x) が有限時間で実行が終了するとき

未定義

それ以外

executable(p,x) == 0 のとき

p(x) が有限時間で停止しないとき

計算可能

p.54

万能関数 comp(p,x) が未定義の場合は0を返す

そうでない場合は comp(p,x) の値を返す

計算不可能

対角線論法で示す

p. 87

引数

プログラムのコード p

その引数 x

出力

y

executable'(x,p)=1 であり、pが表す限定反復プログラムの入力変数にxが表す自然数列の各要素の値をセットして実行開始するとyを戻り値として実行が終了するとき

0

それ以外

executable'(p,x)=0 であるとき

全域帰納的関数であり、原始帰納的関数ではない関数である

アッカーマン関数と同じクラス

p.57

p.58

プログラム p を引数に取る

出力

1

引数 p が何かしらのプログラムのコード(一つの自然数)であり、

かつ、 p が有限時間で終了するような全域関数であるとき

0

それ以外

p がプログラムのコードでないとき

p が真部分関数であるとき

計算不可能

\mathrm{Total}(p)\iff\mathrm{IsCode}(p)\land(\forall x\in\mathbb{N})(\mathrm{Executable}(p,x)\Rightarrow(\exist t\in\mathbb{N})\mathrm{HaltBefore}(p,x,t))

p.58

プログラム p を引数に取る

確実に動くことがわかっているプログラムQと全く同等の挙動をするかどうか

出力

1

引数 p が何かしらのプログラムのコード(一つの自然数)であり、

かつ、任意に固定されたプログラムQが計算する部分関数と、 p が計算する部分関数が等しいとき

0

それ以外

p がプログラムのコードでないとき

p とQが異なる部分関数を計算するとき

計算不可能

p.66

引数

p: ジャンププログラム

x: pの引数

t: ステップ数

返り値

1

かつ、実際に p(x) を実行する

かつ、t回以内の実行で終わる場合

0

otherwise

計算可能

p.107

出力

1: p,qともにジャンププログラムのコードであり、それらが計算する関数が等しい

0: それ以外

計算不可能