クリーネの再帰定理
ここで p {\displaystyle p} は y {\displaystyle y} だけを入力とする。 p {\displaystyle p} の自身の指標は入力に与えられないが、構成より自己参照的な方程式を満たす。
この定理は F ( p ) {\displaystyle F(p)} を φ F ( p ) ( y ) = Q ( p , y ) {\displaystyle \varphi _{F(p)}(y)=Q(p,y)} を満たす関数(この構成にはSmn定理を用いる)とすることでロジャースの定理から証明できる。この関数の不動点が所望の p {\displaystyle p} であることが確かめられる。
この定理は Q から p が帰納的に計算できるという意味で構成的である。例えばロジャースの定理の証明をラムダ計算で再現すれば不動点を計算するラムダ項(不動点コンビネータ)が得られる。
すると h {\displaystyle h} の定義より φ h ( e ) ≃ φ φ e ( e ) {\displaystyle \varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}} が成り立つ。 ところが e {\displaystyle e} は F ∘ h {\displaystyle F\circ h} の指標だったから、 φ e ( e ) = ( F ∘ h ) ( e ) {\displaystyle \varphi _{e}(e)=(F\circ h)(e)} であり、 φ φ e ( e ) ≃ φ F ( h ( e ) ) {\displaystyle \varphi _{\varphi _{e}(e)}\simeq \varphi _{F(h(e))}} 。 ≃ {\displaystyle \simeq } の推移性により、これは φ h ( e ) ≃ φ F ( h ( e ) ) {\displaystyle \varphi _{h(e)}\simeq \varphi _{F(h(e))}} を意味する。すなわち n = h ( e ) {\displaystyle n=h(e)} について φ n ≃ φ F ( n ) {\displaystyle \varphi _{n}\simeq \varphi _{F(n)}} が成り立つ。