递归集合

在可计算性理论中，一个可数集合被称为递归的、可计算的或可判定的，如果我们可以构造在有限数量的时间之后终止并判定一个给定元素是否属于这个集合的算法。更一般的集合的类叫做递归可枚举集合。这些集合包括可判定集合，但只要求它们在有限时间内停止于是或否(或二者，这使集合可判定)。

定义

f为S到N的映射关系

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

使得

若x属于S则f(x)等于0

若x不属于S则f(x)不等于0

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

例子

空集

自然数

自然数的所有有限子集

素数的集合

递归语言是在形式语言字母表之上所有可能词的集合中的递归集合。

性质

如果 A 是递归集合，则 A 的补集是递归集合。 如果 A 和 B 是递归集合，则 A ∩ B、A ∪ B 和 A × B 是递归集合。集合 A 是递归集合，当且仅当 A 和 A 的补集是递归可枚举集合。一个递归集合在全可计算函数下的原像(preimage)是递归集合。