クリーネの再帰定理
第二再帰定理と比較すると、第一再帰定理は狭い前提条件を満たす場合に限りより強い帰結を与える。ロジャース[1967]では第一再帰定理を弱再帰定理(英: weak recursion theorem)、第二再帰定理を強再帰定理(英: strong recursion theorem)と表現している。
ひとつの相違は、第一再帰定理は最小不動点を与えるものであるが、第二再帰定理は最小不動点に限らないということである。いまひとつの相違は、第一再帰定理は再帰方程式を帰納作用素に書き換えられる再帰方程式系に対してのみ適用できるが、第二再帰定理は任意の全域帰納的関数に適用できるということである。この制限はクリーネの不動点定理の連続写像という制限と類似している。
いま g {\displaystyle g} と h {\displaystyle h} を全域計算可能関数とする。これらを用いて関数 f {\displaystyle f} を帰納的に次のように定義する:
f ( 0 , y ) ≃ g ( y ) , {\displaystyle f(0,y)\simeq g(y),\,}
f ( x + 1 , y ) ≃ h ( f ( x , y ) , x , y ) , {\displaystyle f(x+1,y)\simeq h(f(x,y),x,y),\,}
第二再帰定理をこの等式が計算可能関数を定義することを示すことに利用できる。それには考えている計算模型にア・プリオリに帰納的定義が備わっている必要はない。したがって第二再帰定理(と万能関数の存在)が成立する計算模型であればμ-再帰的関数でもチューリング機械でも成り立つ。
この帰納的定義は次の計算可能関数 ( x , y ) ↦ φ F ( e , x , y ) {\displaystyle (x,y)\mapsto \varphi _{F}(e,x,y)} の指標が e {\displaystyle e} 自身となるような e {\displaystyle e} を求めることに帰着できる:
クリーネの第二再帰定理とロジャースの定理は一方から他方を簡単に証明できる(Jones, 1997: p. 229-230)。ところが、クリーネの定理の直接証明(Kleene 1952: p. 352-353)は万能関数を使用しない。その意味するところは、万能関数を持たない幾つかの弱い計算模型に於いても同様の定理が成り立つということである。