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