『C言語による計算の理論』に出てくる関数一覧
p. 40
isCode(n)
p.47
入力: 一つの自然数n
出力
nがジャンププログラムのコードなら1
そうでないなら0
計算可能
executable(p,x)
p.47
$ pを$ xに適用できるかどうかを判定する
引数
p: コード
x: コードpの入力
出力
1: $ pを$ k入力プログラムのコード、かつ、$ xは長さ$ kのコード
0: それ以外
$ pはコードでない
$ xが$ pの入力にマッチしていない
計算可能
実装の内部にisCodeを用いる
executable'(p, x)
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)が有限時間で停止しないとき
計算可能
compPlus(p,x)
p.54
万能関数comp(p,x)が未定義の場合は0を返す そうでない場合はcomp(p,x)の値を返す
計算不可能
対角線論法で示す
comp'(p, x)
p. 87
引数
プログラムのコードp
その引数x
出力
y
executable'(x,p)=1であり、$ pが表す限定反復プログラムの入力変数に$ xが表す自然数列の各要素の値をセットして実行開始すると$ yを戻り値として実行が終了するとき
0
それ以外
executable'(p,x)=0であるとき
全域帰納的関数であり、原始帰納的関数ではない関数である
p.57
total(p)
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))
equalQ(p)
p.58
プログラムpを引数に取る
確実に動くことがわかっているプログラムQと全く同等の挙動をするかどうか
出力
1
引数pが何かしらのプログラムのコード(一つの自然数)であり、
かつ、任意に固定されたプログラム$ Qが計算する部分関数と、pが計算する部分関数が等しいとき
0
それ以外
pがプログラムのコードでないとき
pと$ Qが異なる部分関数を計算するとき
計算不可能
halt_before(p,x,t)
p.66
引数
p: ジャンププログラム
x: pの引数
t: ステップ数
返り値
1
executable(p,x)==1
かつ、実際にp(x)を実行する
かつ、t回以内の実行で終わる場合
0
otherwise
計算可能
p.107
equal(p,q)
出力
1: p,qともにジャンププログラムのコードであり、それらが計算する関数が等しい
0: それ以外
計算不可能