クリーネの再帰定理
クリーネの再帰定理（クリーネのさいきていり、）は再帰理論における2つの基本的な結果である。この定理によれば計算可能関数をそれ自身を用いて記述することができる。この定理は1938年にスティーブン・コール・クリーネによって最初に証明された。1952年の彼の著作 "Introduction to Metamathematics" において見られる。
2つの再帰定理は幾つかの計算可能関数の不動点の構成に利用できる。例えばクワインの生成や関数の帰納的定義などである。任意の再帰的関数の不動点構成への応用はロジャースの定理として知られる。これは (Rogers, 1967) による。
部分帰納的関数のアクセプタブル・ナンバリングを formula_1 とする。指標 formula_2 に対応する帰納的関数を formula_3 と書く。プログラミングの言葉を用いれば、formula_2 はプログラムで formula_3 は表示的意味である。
この文脈での関数 formula_6 の不動点とは、指標 formula_2 で formula_8 を満たすものをいう。プログラミングの言葉を用いれば formula_2 は formula_10 と"意味論的に同値"である.
この定理は (Rogers, 1967: §11.2) のTheorem Iであり、クリーネの（第二）再帰定理の簡易版として記述されている。
この証明では以下で定義される計算可能関数 formula_12 を利用する。 自然数 formula_13 が与えられたとき、関数 formula_12 は次のような計算を行う部分計算可能関数の指標を出力する：
任意の formula_13 について、 formula_20 が停止するならば formula_21 であり、停止しないならば formula_22 は停止しない。これは formula_23 と書ける。関数 formula_12 は部分計算可能関数 formula_25 からSmn定理を用いて構成できる： 各 formula_13 に対して、formula_27 はプログラム formula_28 の指標である。
証明を完成させる為に、formula_6 を任意の全域計算可能関数とする。また formula_12 を上で構成した関数とする。いま formula_2 を合成 formula_32 の指標とする。これは全域計算可能関数である。すると formula_12 の定義より formula_34 が成り立つ。
ところが formula_2 は formula_32 の指標だったから、formula_37 であり、formula_38。 formula_39 の推移性により、これは formula_40 を意味する。すなわち formula_41 について formula_42 が成り立つ。
関数 formula_6 が任意の formula_2 に対して formula_45 を満たすときfixed point freeという。不動点定理によれば計算可能なfixed-point free関数は存在しない。しかし計算可能でないfixed-point free関数は幾つも存在する。アースラノフの完全性条件は、帰納的可算集合 formula_46 に関する次の条件が同値であることを述べる：
第二再帰定理は直観的には自己参照的プログラムが可能であるということである。
これは次のように使用される。いま次のような自己参照的プログラムを考える： 計算可能関数 formula_53 の第1変数に自分自身の指標を、第2変数に入力を渡して計算する。第二再帰定理はこのような自己参照的プログラム formula_51 が構成できることを示している。ここで formula_51 は formula_15 だけを入力とする。formula_51 の自身の指標は入力に与えられないが、構成より自己参照的な方程式を満たす。
この定理は formula_58 を formula_59 を満たす関数（この構成にはSmn定理を用いる）とすることでロジャースの定理から証明できる。この関数の不動点が所望の formula_51 であることが確かめられる。
この定理は "Q" から "p" が帰納的に計算できるという意味で構成的である。例えばロジャースの定理の証明をラムダ計算で再現すれば不動点を計算するラムダ項（不動点コンビネータ）が得られる。
クリーネの第二再帰定理とロジャースの定理は一方から他方を簡単に証明できる（Jones, 1997: p. 229-230）。ところが、クリーネの定理の直接証明（Kleene 1952: p. 352-353）は万能関数を使用しない。その意味するところは、万能関数を持たない幾つかの弱い計算模型に於いても同様の定理が成り立つということである。
いま formula_61 と formula_12 を全域計算可能関数とする。これらを用いて関数 formula_63 を帰納的に次のように定義する：
第二再帰定理をこの等式が計算可能関数を定義することを示すことに利用できる。それには考えている計算模型にア・プリオリに帰納的定義が備わっている必要はない。したがって第二再帰定理（と万能関数の存在）が成立する計算模型であればμ-再帰的関数でもチューリング機械でも成り立つ。
この帰納的定義は次の計算可能関数 formula_66 の指標が formula_2 自身となるような formula_2 を求めることに帰着できる：
再帰定理は formula_71 なる計算可能関数 formula_72 の存在を確立する。すると formula_72 は与えられた帰納的定義を満たす。
再帰定理の使用の古典的な例は formula_74 に対するものである。この場合に対応する指標 formula_51 は任意に値を入力すると出力が自分自身に一致する計算可能関数である(Cutland 1980: p. 204)。プログラミングの言葉を用いれば、これはクワインとして知られるプログラムの指標に他ならない。
以下ではLispを用いて指標 formula_51 が関数 formula_77 からどのように実効的に得られるかを見る。関数 codice_1 はSmn定理に対応するLispコードである。
codice_2 は任意の2引数の関数のLispコードに置き換えられる。
次の2つの式の結果は等しくなる。codice_3 codice_4
自己反映計算は自己参照を用いたプログラミングである。Jones (1997) は自己反映言語に基づいた第二再帰定理の見方を示した。
それは自己反映言語の計算能力は自己反映を持たない言語の計算能力よりも強くはないということである。（何故なら自己反映言語のインタプリタは自己反映を持たない言語によって実装できる）； 再帰定理は自己反映言語において明らかに実現できる。したがって自己反映を持たない言語（帰納的関数やチューリング機械などの計算模型）でも成り立つ。
第一再帰定理は帰納的な枚挙作用素の不動点に関するものである。枚挙作用素とは対 formula_78 の集合であって、 formula_46 はコード化された有限集合、 formula_80 は自然数である。 関数が枚挙作用素を通じて定義される場合など formula_80 は自然数の対のコードと見做されることがある。枚挙作用素は枚挙還元性の研究で最も重要な概念のひとつである。
枚挙作用素 Φ は自然数の集合から自然数の集合への関数を定める：
帰納作用素とは部分帰納的関数のグラフ（正確には部分関数のグラフを対のコードの集合と見做したもの）を常に部分帰納的関数（同様）に写すものをいう。このとき帰納作用素は部分帰納的関数から部分帰納的関数への関数を定めるものと考えられる。
枚挙作用素 formula_83 の不動点とは formula_84 なる集合 formula_6 をいう。同様に帰納作用素 formula_86 の不動点とは formula_87 なる部分関数 formula_63 をいう。第一再帰定理は枚挙作用素が計算可能ならば不動点が実効的に得られることを示す。
第二再帰定理と同様に、第一再帰定理は再帰方程式を満たす関数を構成する為に使える。第一再帰定理を使うためには再帰方程式系を帰納作用素を使って書き換える必要がある。
階乗関数 formula_63 の再帰方程式系を考える：
対応する帰納作用素 formula_83 は formula_63 の前の値から次の値をどのように得るかを記述することで得られる。直感的にいうと formula_63 の有限近似を formula_83 で写すとよりよい（定義域が拡大された）有限近似が得られるように formula_83 を定義すればよい。まず formula_83 に対 formula_98 を置く。これは formula_99 であることを示す。次に任意の formula_100 について formula_83 に対 formula_102 を置く。これは formula_103 ならば formula_104 であることを示す。
第一再帰定理より帰納的可算集合 formula_6 で formula_84 なる最小なものが存在する。この集合 formula_6 は自然数の対だけからなり、ちょうど所望の階乗関数 formula_63 のグラフとなっている。
上のようにして再帰方程式系の解が必ず得られるとは限らない。次のような解を持たない再帰方程式系が考える：
この方程式をもとに枚挙作用素 formula_86 を作る。第一再帰定理より formula_86 は（帰納的可算な）不動点を持つ。ところがいかなる部分（帰納的）関数も上の方程式系を満足しえない。この再帰方程式に対応する作用素は帰納作用素ではないからである。
第一再帰定理の前半の証明は、空集合から始めて枚挙演算子 formula_83 の反復によって得られる。まず集合列 formula_115 を次のように帰納的に定義する：
次に formula_118 とおく。formula_115 は一様に帰納的な増大列であるので formula_6 は帰納的可算である。さらに formula_6 は formula_83 の最小不動点である。ここで構成した formula_115 は完備半順序で定義された単調関数の不動点の存在を述べるクリーネの不動点定理のクリーネ鎖に対応している。
定理の後半は前半から従う。実際 formula_83 を帰納作用素とすると上の証明の formula_6 が部分関数のグラフになることが formula_126 に関する帰納法で確かめられる。
第二再帰定理と比較すると、第一再帰定理は狭い前提条件を満たす場合に限りより強い帰結を与える。ロジャース[1967]では第一再帰定理を弱再帰定理（）、第二再帰定理を強再帰定理（）と表現している。
ひとつの相違は、第一再帰定理は最小不動点を与えるものであるが、第二再帰定理は最小不動点に限らないということである。いまひとつの相違は、第一再帰定理は再帰方程式を帰納作用素に書き換えられる再帰方程式系に対してのみ適用できるが、第二再帰定理は任意の全域帰納的関数に適用できるということである。この制限はクリーネの不動点定理の連続写像という制限と類似している。
アナトリー・マルツェフはプリコンプリート・ナンバリングを持つ任意の集合に対する一般化された再帰定理を示した。アクセプタブル・ナンバリングは計算可能関数の集合に対するプリコンプリート・ナンバリングであるから、クリーネの再帰定理は一般化された定理の特別な場合として得られる。
プリコンプリート・ナンバリング formula_127 を所与とすると、任意の部分計算可能関数 formula_128 に対して、全域計算可能関数 formula_129 が存在して、次を満たす：