递归集合

在可计算性理论中，一组自然数被称为可计算的、递归的或可判定的，如果有一种算法将一个数字作为输入，在有限的时间（可能取决于给定的数字）后终止并正确地决定数字是否 是否属于集合。

不可计算的集合称为不可计算的或不可判定的。

比可计算集合更一般的集合类包括可计算可枚举 (c.e.) 集合，也称为半可判定集合。 对于这些集合，只需要有一个算法可以正确判断一个数何时在集合中； 对于不在集合中的数字，该算法可能不会给出答案（但不会给出错误答案）。

例子：

• 自然数的每个有限或余有限子集都是可计算的。 这包括这些特殊情况：
  • 空集是可计算的。
  • 整个自然数集都是可计算的。
  • 每个自然数（如标准集合论中所定义）都是可计算的； 也就是说，小于给定自然数的自然数集是可计算的。
• 素数的子集是可计算的。
• 递归语言是形式语言的可计算子集。
• Kurt Gödel 的论文 On Formally undecidable propositions of Principia Mathematica and related systems I 中描述的算术证明的哥德尔数集是可计算的； 参见哥德尔不完备性定理。

非示例：

• 停止的图灵机集合不可计算。
• 两个有限单纯复形的同构类不可计算。
• 忙碌的海狸冠军集是不可计算的。
• 希尔伯特第十问题不可计算。

如果 A 是可计算集，则 A 的补集是可计算集。 如果A和B是可计算集，则A∩B、A∪B和A×B在康托配对函数下的像是可计算集。

A 是可计算集当且仅当 A 和 A 的补集都是可计算可枚举的 (c.e.)。 可计算集在全可计算函数下的原像是可计算集。

在全可计算双射下的可计算集的图像是可计算的。 （通常，可计算函数下的可计算集的图像是 c.e.，但可能不可计算）。

A 是可计算集当且仅当它处于算术层次的 Δ 1 0 {\displaystyle \Delta _{1}{0}} 层。

A 是可计算集当且仅当它是非递减总可计算函数的范围或空集。 在非递减总可计算函数下的可计算集的图像是可计算的。