クリーネの再帰定理
クリーネの再帰定理(クリーネのさいきていり、英: Kleene's recursion theorem)は、再帰理論における2つの基本的な結果である。この定理によれば計算可能関数をそれ自身を用いて記述することができる。この定理は1938年にスティーブン・コール・クリーネによって最初に証明された。1952年の彼の著作 Introduction to Metamathematics において見られる。
2つの再帰定理は幾つかの計算可能関数の不動点の構成に利用できる。例えばクワインの生成や関数の帰納的定義などである。任意の再帰的関数の不動点構成への応用はロジャースの定理として知られる。これはハートレイ・ロジャース(英語版) (Rogers, 1967) による。
アナトリー・マルツェフはプリコンプリート・ナンバリングを持つ任意の集合に対する一般化された再帰定理を示した。アクセプタブル・ナンバリングは計算可能関数の集合に対するプリコンプリート・ナンバリングであるから、クリーネの再帰定理は一般化された定理の特別な場合として得られる。
プリコンプリート・ナンバリング ν {\displaystyle \nu } を所与とすると、任意の部分計算可能関数 f : N 2 → N {\displaystyle f:\mathbb {N} ^{2}\to \mathbb {N} } に対して、全域計算可能関数 t : N → N {\displaystyle t:\mathbb {N} \to \mathbb {N} } が存在して、次を満たす:
ν ∘ f ( n , t ( n ) ) = ν ∘ t ( n ) . {\displaystyle \nu \circ f(n,t(n))=\nu \circ t(n).}