A.I. Maltsevによる一般化された定理
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/10/03 01:23 UTC 版)
「クリーネの再帰定理」の記事における「A.I. Maltsevによる一般化された定理」の解説
アナトリー・マルツェフはプリコンプリート・ナンバリングを持つ任意の集合に対する一般化された再帰定理を示した[要出典]。アクセプタブル・ナンバリングは計算可能関数の集合に対するプリコンプリート・ナンバリングであるから、クリーネの再帰定理は一般化された定理の特別な場合として得られる。 プリコンプリート・ナンバリング ν {\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).}
※この「A.I. Maltsevによる一般化された定理」の解説は、「クリーネの再帰定理」の解説の一部です。
「A.I. Maltsevによる一般化された定理」を含む「クリーネの再帰定理」の記事については、「クリーネの再帰定理」の概要を参照ください。
- A.I. Maltsevによる一般化された定理のページへのリンク