コンテンツにスキップ

「帰納的可算集合」の版間の差分

m
編集の要約なし
m編集の要約なし
前者の条件から、これを'''半決定可能集合'''(semidecidable set)と呼ぶことがある。また、後者の条件から'''計算可枚挙集合'''(computably enumerable set)とも呼ぶ。略記法として '''r.e.''' あるいは '''c.e.''' とされることも多い。
 
[[計算複雑性理論]]において、全ての帰納的可算集合を包含する[[複雑性クラス]]を '''[[RE (計算複雑性理論)|RE]]''' と呼ぶ。
 
== 形式的定義 ==
 
== 注意 ==
[[チャーチ=チューリングのテーゼ]]によれば、率的に計算可能な関数は全て[[チューリングマシン]]で計算可能であり、従って集合 ''S'' は何らかの[[アルゴリズム]]で ''S'' の数え上げができる場合のみ帰納的可算である。なお、チャーチ=チューリングのテーゼが形式的な公理ではないため、これも形式的定義にできない。
 
帰納的可算集合を全体再帰関数の「値域」ではなく、部分関数の「定義域」として定義する方が最近では一般的である。これは最近の再帰理論でそのほうが自然であるためである。他の分野では数え上げを使った定義がよく使われる。