About: 帰納的可算集合

帰納的可算集合（きのうてきかさんしゅうごう、英: Recursively enumerable set）は、計算理論または再帰理論におけるある種の集合に付与された名前。自然数の集合 S について以下が成り立つ場合、その集合を指して帰納的可算、計算可枚挙、半決定可能、証明可能、チューリング-認識可能などと称する。 * あるアルゴリズムに入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が S の元であることである。 あるいは、これと同値だが、 * S の元を枚挙するアルゴリズムが存在する。つまり、その出力は S の元のリスト s1, s2, s3, ... である。このアルゴリズムは必要ならば無限に動作する。 これが半決定可能集合 (semidecidable set) と時に呼ばれるのは前者の条件に由来する。また、計算可枚挙集合（computably enumerable set）という用語は後者の条件に由来する。略して r.e. あるいは c.e. と書くが、これは出版物にもよく出現する。 計算複雑性理論において、全ての帰納的可算集合を包含する複雑性クラスを RE と呼ぶ。再帰理論においては、 包含関係に基づく r.e. 集合の束 (lattice) を と書く。