コンテンツにスキップ

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

m
(脚注を生成)
 
== 注意 ==
[[チャーチ=チューリングのテーゼ]]によれば、に計算可能な関数は全て[[チューリングマシン]]で計算可能であり、従って集合 ''S'' が帰納的可算である必要十分条件は、何らかの[[アルゴリズム]]で ''S'' の枚挙ができることである。しかしこれを形式的な定義とすることはできない。何故ならチャーチ=チューリングのテーゼは形式的な公理ではなく、非形式的な予想だからである。
 
最近の文献では、帰納的可算集合を全体再帰関数の「値域」ではなく、部分関数の「定義域」として定義する方が一般的である。この理由は、例えば[[α-再帰理論]]([[:en:Alpha recursion theory|en]])のような一般化された再帰理論では、定義域を用いた定義の方が自然だと判ったためである。他の文献では枚挙を使った定義がよく使われるが、これも帰納的可算集合に同値である。