|
帰納的可算集合（きのうてきかさんしゅうごう、）は、計算理論または再帰理論におけるある種の集合に付与された名前。自然数の集合 ''S'' について以下が成り立つ場合、その集合を指して帰納的可算、計算可枚挙、半決定可能、証明可能、チューリング-認識可能などと称する。 * あるアルゴリズムに入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が ''S'' の元であることである。 あるいは、これと同値だが、 * ''S'' の元を枚挙するアルゴリズムが存在する。つまり、その出力は ''S'' の元のリスト ''s''1, ''s''2, ''s''3, ... である。このアルゴリズムは必要ならば無限に動作する。 これが半決定可能集合 (semidecidable set) と時に呼ばれるのは前者の条件に由来する。また、計算可枚挙集合（computably enumerable set）という用語は後者の条件に由来する。略して r.e. あるいは c.e. と書くが、これは出版物にもよく出現する。 計算複雑性理論において、全ての帰納的可算集合を包含する複雑性クラスを RE と呼ぶ。再帰理論においては、 包含関係に基づく r.e. 集合の束 (lattice) を と書く。 == 形式的定義 == 自然数の集合 ''S'' について、定義域が ''S'' と正確に一致するような何らかの部分再帰関数（部分計算可能関数）''f'' が存在するとき、''S'' は帰納的可算であると言う。つまり ''f'' が定義される必要十分条件は、''f'' への入力が ''S'' の元であることである。 この定義は任意の可算集合 A に拡張できる。そのためには、A の元をゲーデル数で表し、もし対応するゲーデル数の集合が帰納的可算ならば A の何らかの部分集合が帰納的可算になることを言えば良い。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「帰納的可算集合」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Recursively enumerable set 」があります。 スポンサード リンク
|