クリーネの再帰定理

クリーネの再帰定理

クリーネの再帰定理は、計算可能性に関する基本的な理論であり、特に計算可能関数が自身を用いて記述できることを示しています。この重要な理論は、スティーブン・コール・クリーネによって1938年に初めて証明され、その後1952年に彼の著作『Introduction to Metamathematics』の中で詳述されています。

この定理には、計算可能関数の不動点を生成するための実用的な応用があり、クワインや関数の帰納的定義などに利用されています。また、任意の再帰的関数の不動点構築に対する応用は「ロジャースの定理」として知られ、これはハートレイ・ロジャースによって1950年代に提唱されました。

理論的な背景

この定理の記述にあたっては、部分帰納的関数の可接受ナンバリングを使用し、特定のインデックスに対応する帰納的関数に関する記法が導入されます。例えば、インデックスを`e`とし、それに関連する帰納的関数は`φ_e`と書きます。これにより、プログラミングの視点からも、`e`はプログラムそのものであり、`φ_e`はその意味を持つことが理解されます。

ロジャースの不動点定理

ロジャースの不動点定理は、任意の全域計算可能関数`F`が不動点を持つことを述べています。これは、インデックス`e`に対して、`φ_e ≅ φ_{F(e)}`という関係が成り立つ場合です。言い換えれば、`e`は`F(e)`と意味的に同一であるということを示しています。この定理はクリーネの第二再帰定理の簡略版と見なされます。

不動点定理の証明

クリーネの再帰定理の証明において、特定の計算可能関数`h`が使用されます。この関数は、与えられた自然数`x`に対し、`φ_x(x)`の出力を試み、その結果が自然数`e`を返すと、次に`φ_e(y)`を計算して返します。このプロセスは、決して停止しない場合にも適用されます。この`h`は、Smn定理に基づいて形成された部分計算可能関数から構成されます。

その後、全域計算可能関数`F`を任意に選び、`h`の幾何学的特性を利用することで不動点を見つけることに成功します。

不動点を持たない関数

計算可能な不動点を持たない関数は、いかなる指数`e`に対しても、`φ_e ≄ φ_{F(e)}`を満たすと定義されます。不動点定理によると、計算可能な不動点を持たない関数は存在し得ませんが、計算できない不動点を持たない関数は複数存在します。

クリーネの第二再帰定理

第二再帰定理においては、任意の部分帰納的関数`Q(x,y)`に対して、不動点を持つ指標`p`が存在することが示されます。これは自己参照的なプログラムの構成を可能にし、実際に計算可能な関数がどのように自己参照的に適用できるかを表現します。第二再帰定理は、このような自己参照的なプログラムの生成を可能にする理論的基盤を提供します。

第一次と第二次の再帰定理の比較

第一再帰定理は、計算可能な枚挙作用素が不動点を持つことを示しますが、第二再帰定理はより強い結論を持つ場合があります。第一再帰定理は明確に最小不動点を提供するのに対し、第二再帰定理は最小不動点に制限されません。これにより、第一再帰定理は非常に特定の条件下でのみ適用されることが明確です。

一般化された定理

アナトリー・マルツェフによって示された一般化された再帰定理は、プリコンプリート・ナンバリングを持つ任意の集合に適用される広範な理論です。これによりクリーネの再帰定理は、より強力な理論の特別な場合として位置付けられています。

このように、クリーネの再帰定理とその関連する概念は、計算可能性理論において非常に重要であり、自己参照や不動点の存在に関する理解を深めるための基礎を築いています。

もう一度検索