第一再帰定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/03 01:23 UTC 版)
第一再帰定理は帰納的な枚挙作用素の不動点に関するものである。枚挙作用素とは対 ( A , n ) {\displaystyle (A,n)} の集合であって、 A {\displaystyle A} はコード化された有限集合、 n {\displaystyle n} は自然数である。 関数が枚挙作用素を通じて定義される場合など n {\displaystyle n} は自然数の対のコードと見做されることがある。枚挙作用素は枚挙還元性の研究で最も重要な概念のひとつである。 枚挙作用素 Φ は自然数の集合から自然数の集合への関数を定める： Φ ( X ) = { n ∣ ∃ A ⊆ X [ ( A , n ) ∈ Φ ] } . {\displaystyle \Phi (X)=\{n\mid \exists A\subseteq X[(A,n)\in \Phi ]\}.} 帰納作用素とは部分帰納的関数のグラフ（正確には部分関数のグラフを対のコードの集合と見做したもの）を常に部分帰納的関数（同様）に写すものをいう。このとき帰納作用素は部分帰納的関数から部分帰納的関数への関数を定めるものと考えられる。 枚挙作用素 Φ {\displaystyle \Phi } の不動点とは Φ ( F ) = F {\displaystyle \Phi (F)=F} なる集合 F {\displaystyle F} をいう。同様に帰納作用素 Ψ {\displaystyle \Psi } の不動点とは Ψ ( f ) = f {\displaystyle \Psi (f)=f} なる部分関数 f {\displaystyle f} をいう。第一再帰定理は枚挙作用素が計算可能ならば不動点が実効的に得られることを示す。 第一再帰定理 次の言明が成り立つ:任意の計算可能な枚挙作用素は帰納的可算な最小不動点を持つ。 任意の帰納作用素は部分帰納的な最小不動点を持つ。
※この「第一再帰定理」の解説は、「クリーネの再帰定理」の解説の一部です。
「第一再帰定理」を含む「クリーネの再帰定理」の記事については、「クリーネの再帰定理」の概要を参照ください。
- 第一再帰定理のページへのリンク
