クリーネの再帰定理
この文脈での関数 F {\displaystyle F} の不動点とは、指標 e {\displaystyle e} で φ e ≃ φ F ( e ) {\displaystyle \varphi _{e}\simeq \varphi _{F(e)}} を満たすものをいう。プログラミングの言葉を用いれば e {\displaystyle e} は F ( e ) {\displaystyle F(e)} と意味論的に同値である.
ロジャースの不動点定理. F {\displaystyle F} が(全域)計算可能ならば不動点を持つ。
この定理は (Rogers, 1967: §11.2) のTheorem Iであり、クリーネの(第二)再帰定理の簡易版として記述されている。
これは f ( n ) = m {\displaystyle f(n)=m} ならば f ( n + 1 ) = ( n + 1 ) ⋅ m {\displaystyle f(n+1)=(n+1)\cdot m} であることを示す。
第一再帰定理より帰納的可算集合 F {\displaystyle F} で Φ ( F ) = F {\displaystyle \Phi (F)=F} なる最小なものが存在する。この集合 F {\displaystyle F} は自然数の対だけからなり、ちょうど所望の階乗関数 f {\displaystyle f} のグラフとなっている。
上のようにして再帰方程式系の解が必ず得られるとは限らない。次のような解を持たない再帰方程式系が考える:
g ( 0 ) = 1 , {\displaystyle g(0)=1,}
g ( n + 1 ) = 1 , {\displaystyle g(n+1)=1,}
g ( 2 n ) = 0. {\displaystyle g(2n)=0.}
この方程式をもとに枚挙作用素 Ψ {\displaystyle \Psi } を作る。第一再帰定理より Ψ {\displaystyle \Psi } は(帰納的可算な)不動点を持つ。ところがいかなる部分(帰納的)関数も上の方程式系を満足しえない。この再帰方程式に対応する作用素は帰納作用素ではないからである。
これは φ h ( x ) ≃ φ φ x ( x ) {\displaystyle \varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}} と書ける。関数 h {\displaystyle h} は部分計算可能関数 g ( x , y ) = φ φ x ( x ) ( y ) {\displaystyle g(x,y)=\varphi _{\varphi _{x}(x)}(y)} からSmn定理を用いて構成できる: 各 x {\displaystyle x} に対して、 h ( x ) {\displaystyle h(x)} はプログラム y ↦ g ( x , y ) {\displaystyle y\mapsto g(x,y)} の指標である。
証明を完成させる為に、 F {\displaystyle F} を任意の全域計算可能関数とする。また h {\displaystyle h} を上で構成した関数とする。いま e {\displaystyle e} を合成 F ∘ h {\displaystyle F\circ h} の指標とする。これは全域計算可能関数である。