递归可枚举集合

递归可枚举集合（英语：Recursively enumerable set）是可计算性理论或更狭义的递归论中的一个概念。可数集合S被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果或者等价的说，包含所有可递归枚举集合的复杂性类是 RE。共同的编程意义会暗示出如何转换一种算法到等价的另一种算法。第一种情况说明了为什么有时说半可判定的，而第二种情况说明了为什么叫计算可枚举的。可数集合 S {displaystyle S} 是递归可枚举的，如果存在一个偏可计算函数 f {displaystyle f} 使得换句话说， S {displaystyle S} 是 f {displaystyle f} 的域:(注意这是偏函数的域的两种可能意义之一，是在递归论中所偏好的定义域。参见在偏函数中的讨论。)集合 S {displaystyle S} 被成为 co-递归可枚举的或 co-r.e.，如果 S {displaystyle S} 的补集是递归可枚举的。可数集合 S {displaystyle S} 被叫做递归可枚举的，如果存在着一个偏可计算函数 f :⊆ N → S {displaystyle f:subseteq mathbb {N} to S} ，使得 S {displaystyle S} 是 f {displaystyle f} 的值域:f {displaystyle f} 被称为枚举函数，因为它关联上一个枚举上的次序(rank)到 S {displaystyle S} 的每个元素。因为邱奇-图灵论题声称可计算函数被图灵机和其他计算模型等价的定义，我们陈述定义为这也是递归可枚举集合的常见定义。如果 A 和 B 是递归可枚举集合，则 A ∩ B、A ∪ B 和 A × B 是递归可枚举集合。集合 A 是递归集合，当且仅当 A 和 A 补集二者是递归可枚举集合。递归可枚举集合一个可计算函数下的原像是递归可枚举集合。