インタプリタ的なやつ

普段、プログラムごとに計算機が必要ないのは、万能関数のように計算をシミュレートするものがあるから

計算可能である

任意の計算可能部分関数fに対して自然数pが存在して以下が成り立つ

f(\vec{x})=\mathrm{comp}(p,\lang\vec{x}\rang)

fを見たときは任意個の引数を取るので\vec{x}になっている

ex. f(1,2,3,\cdots,10)

\mathrm{comp}は、2つの引数しか取らないので、xはコード化されて一つの自然数なので\lang\vec{x}\rang

ex. \mathrm{comp}(16, 100)

の話

引数

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

x: コードpの入力

出力

p(x)

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

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

未定義

それ以外

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

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