万能関数 - mrsekut-p

万能関数

universal function

インタプリタ的なやつ

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

計算可能である

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

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

code:hs

f :: Code -> Int

f = comp p

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

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

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

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

『C言語による計算の理論』.iconの話

引数

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

x: コードpの入力

出力

p(x)

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

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

未定義

それ以外

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

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