递归可枚举集合
维基百科,自由的 encyclopedia
递归可枚举集合(英语:Recursively enumerable set)是可计算性理论或更狭义的递归论中的一个概念。可数集合S被称为是递归可枚举、计算可枚举的、半可判定的或可证明的,如果
- 存在一个算法,只有当输入是S中的元素时,算法才会中止。
此条目已列出参考文献,但因为没有文内引注而使来源仍然不明。 (2014年7月11日) |
或者等价的说,
- 存在一个算法,可以将S中的成员枚举出来。也就是说该算法的输出就是 S 的成员列表: s1, s2, s3, ... 如果需要它可以永远运行下去。
包含所有可递归枚举集合的复杂性类是 RE。
共同的编程意义会暗示出如何转换一种算法到等价的另一种算法。第一种情况说明了为什么有时说半可判定的,而第二种情况说明了为什么叫计算可枚举的。