递归集合

在可计算性理论中，一个自然数的子集被称为递归的、可计算的或具可判定性，如果我们可以构造一个算法，使之能在有限时间内终止并判定一个给定元素是否属于这个集合。更一般的集合的类叫做递归可枚举集合。这些集合包括递归集合，对于这种集合，只需要存在一个算法，当某个元素位于这个集合中时，能够在有限时间内给出正确的判定结果，但是当元素不在这个集合中时，算法可能会永远运行下去（但不会给出错误答案）。

定义

自然数的子集 S 被称为递归的，如果存在一个全可计算函数

$f:S\to \mathbb {N}$

使得

$f(x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\\neq 0&{\mbox{if}}\ x\notin S\end{matrix}}\right.$

换句话说，集合 S 是递归的，当且仅当指示函数 $1_{S}$ 是可计算的。

例子

• 空集
• 自然数
• 自然数的所有有限子集（有限子集并非可数子集，后者可能有无限多的元素）
• 素数的集合
• 递归语言是在形式语言字母表之上所有可能词的集合中的递归集合。

性质

如果$A$是递归集合，则$A$的补集是递归集合。 如果$A$和$B$是递归集合，则$A\cap B$、$A\cup B$和$A\times B$ 是递归集合。集合$A$是递归集合，当且仅当$A$和$A$的补集是递归可枚举集合。一个递归集合在全可计算函数下的原像（preimage）是递归集合。

参见

• 递归可枚举集合
• 递归函数