递归集合
维基百科,自由的百科全书
在可计算性理论中,一个可数集合被称为递归的、可计算的或具可判定性,如果我们可以构造在有限数量的时间之后终止并判定一个给定元素是否属于这个集合的算法。更一般的集合的类叫做递归可枚举集合。这些集合包括可判定集合,对于这种集合, 只需要存在这样的算法, 当元素位于这个集合中时, 算法能正确判断, 但是当元素不在这个集合中时, 算法可能没有答案(但不会给出错误答案).
目录 |
[编辑] 定义
使得
换句话说,集合 S 是递归的,当且仅当指示函数
是可计算的。
[编辑] 例子
[编辑] 性质
如果 A 是递归集合,则 A 的补集是递归集合。 如果 A 和 B 是递归集合,则 A ∩ B、A ∪ B 和 A × B 是递归集合。集合 A 是递归集合,当且仅当 A 和 A 的补集是递归可枚举集合。一个递归集合在全可计算函数下的原像(preimage)是递归集合。

