再帰セット – 定義

計算可能性理論では、再帰集合または決定可能集合は、その特性関数が数学的論理の意味での再帰関数である整数 (または整数内の容易にコーディング可能な要素) の集合です。

換言すれば、それは、（現在達成可能なコンピュータのメモリや計算時間の制限を考慮せずに）常に停止しているコンピュータプログラムによってメンバーシップテストを実行できるセットである。

セットが再帰的であるのは、その補集合と同様に再帰的に列挙できる場合に限ります。

例

次のセットは再帰的です。

• 整数のセット、
• 空集合、
• 偶数の集合、
• 素数の集合、
• ディオファントス方程式の解の集合。