クリーネの再帰定理
第二再帰定理と同様に、第一再帰定理は再帰方程式を満たす関数を構成する為に使える。第一再帰定理を使うためには再帰方程式系を帰納作用素を使って書き換える必要がある。
階乗関数 f {\displaystyle f} の再帰方程式系を考える:
f ( 0 ) = 1 , {\displaystyle f(0)=1,}
f ( n + 1 ) = ( n + 1 ) ⋅ f ( n ) . {\displaystyle f(n+1)=(n+1)\cdot f(n).}
対応する帰納作用素 Φ {\displaystyle \Phi } は f {\displaystyle f} の前の値から次の値をどのように得るかを記述することで得られる。直感的にいうと f {\displaystyle f} の有限近似を Φ {\displaystyle \Phi } で写すとよりよい(定義域が拡大された)有限近似が得られるように Φ {\displaystyle \Phi } を定義すればよい。まず Φ {\displaystyle \Phi } に対 ( ∅ , ( 0 , 1 ) ) {\displaystyle (\varnothing ,(0,1))} を置く。これは f ( 0 ) = 1 {\displaystyle f(0)=1} であることを示す。次に任意の ( n , m ) {\displaystyle (n,m)} について Φ {\displaystyle \Phi } に対 ( { ( n , m ) } , ( n + 1 , ( n + 1 ) ⋅ m ) {\displaystyle (\{(n,m)\},(n+1,(n+1)\cdot m)} を置く。
第二再帰定理は直観的には自己参照的プログラムが可能であるということである。
第二再帰定理. 任意の部分帰納的関数 Q ( x , y ) {\displaystyle Q(x,y)} に対して指標 p {\displaystyle p} が存在して φ p ≃ λ y . Q ( p , y ) {\displaystyle \varphi _{p}\simeq \lambda y.Q(p,y)} が成り立つ。
これは次のように使用される。いま次のような自己参照的プログラムを考える: 計算可能関数 Q ( x , y ) {\displaystyle Q(x,y)} の第1変数に自分自身の指標を、第2変数に入力を渡して計算する。第二再帰定理はこのような自己参照的プログラム p {\displaystyle p} が構成できることを示している。