クリーネの再帰定理
部分帰納的関数のアクセプタブル・ナンバリングを φ {\displaystyle \varphi } とする。指標 e {\displaystyle e} に対応する帰納的関数を φ e {\displaystyle \varphi _{e}} と書く。プログラミングの言葉を用いれば、 e {\displaystyle e} はプログラムで φ e {\displaystyle \varphi _{e}} は表示的意味である。
関数 F {\displaystyle F} が任意の e {\displaystyle e} に対して φ e ≄ φ F ( e ) {\displaystyle \varphi _{e}\not \simeq \varphi _{F(e)}} を満たすときfixed point freeという。不動点定理によれば計算可能なfixed-point free関数は存在しない。しかし計算可能でないfixed-point free関数は幾つも存在する。アースラノフの完全性条件は、帰納的可算集合 A {\displaystyle A} に関する次の条件が同値であることを述べる:
A {\displaystyle A} はチューリング次数 0 ′ {\displaystyle {\boldsymbol {0}}'} つまり停止性問題の次数を持つ。
Fixed-point free関数 f ≤ T A {\displaystyle f\leq _{T}A} が存在する。