クリーネの第二再帰定理の簡易版

関数Fが計算可能ならば不動点を持つ

定理 ref p.61

どんな計算可能1変数全域関数fに対してもk入力プログラムRが存在して以下が成り立つ

Rのコードをrとすると、rとf(r)はk変数部分関数に解釈すれば同じである

さくっというと

任意の1変数関数fについて、

そのコードrと、f(r)は同じである

証明

目的はS^1_k(v,v)とf(S^1_k(v,v))が等しいということをいいたい

ここでvは定数的なもの #??

f(S^1_k(v,v))は

S-m-n定理のもので、

「k引数関数」のコード

第一引数のvもコードで、第2引数は「vに渡す末尾の引数」

g(x_1,x_2,\cdots,x_k,v):=\mathrm{comp}(f(S^1_k(v,v)),\lang x_1,\cdots,x_k\rang)

というふうに関数gを定義する(右から左に読む)

fは任意の1変数全域関数

S^1_k(v,v)は不動点になる

具体的にはr=S^1_k(\mathrm{g},\mathrm{g})が不動点

参考