クリーネの再帰定理
φ F ( e , 0 , y ) ≃ g ( y ) , {\displaystyle \varphi _{F}(e,0,y)\simeq g(y),\,}
φ F ( e , x + 1 , y ) ≃ h ( φ e ( x , y ) , x , y ) . {\displaystyle \varphi _{F}(e,x+1,y)\simeq h(\varphi _{e}(x,y),x,y).\,}
再帰定理は φ f ( x , y ) ≃ φ F ( f , x , y ) {\displaystyle \varphi _{f}(x,y)\simeq \varphi _{F}(f,x,y)} なる計算可能関数 φ f {\displaystyle \varphi _{f}} の存在を確立する。すると φ f {\displaystyle \varphi _{f}} は与えられた帰納的定義を満たす。