递归可枚举集合

维基百科,自由的百科全书
跳转至: 导航搜索

递归可枚举集合可计算性理论或更狭义的递归论中的一个概念。可数集合S被称为是递归可枚举、计算可枚举的、半可判定的或可证明的,如果

  • 存在一个算法,只有当输入是S中的元素时,算法才会中止。

或者等价的说,

  • 存在一个算法,可以将S中的成员枚举出来。也就是说该算法的输出就是 S 的成员列表: s1, s2, s3, ... 如果需要它可以永远运行下去。

包含所有可递归枚举集合的复杂性类RE

共同的编程意义会暗示出如何转换一种算法到等价的另一种算法。第一种情况说明了为什么有时说半可判定的,而第二种情况说明了为什么叫计算可枚举的

定义[编辑]

可数集合 S 是递归可枚举的,如果存在一个可计算函数 f 使得

f(x) = 
\left\{\begin{matrix} 
0 &\mbox{if}\ x \in S \\
\mbox{undef/does not halt}\ &\mbox{if}\ x \notin S
\end{matrix}\right.

换句话说,Sf:

\mathrm{dom}(f) = S

(注意这是偏函数的域的两种可能意义之一,是在递归论中所偏好的定义域。参见在偏函数中的讨论。)

集合 S 被成为 co-递归可枚举的co-r.e.,如果 S补集是递归可枚举的。

等价定义[编辑]

可数集合 S 被叫做递归可枚举的,如果存在着一个可计算函数 f :\subseteq \mathbb{N} \to S,使得 Sf值域:

\mathrm{rng}(f) = S

f 被称为枚举函数,因为它关联上一个枚举上的次序(rank)到 S 的每个元素。

注解[编辑]

因为邱奇-图灵论题声称可计算函数被图灵机和其他计算模型等价的定义,我们陈述定义为

可数集合 S 被称为递归可枚举的,如果有一个图灵机,在给定 S 的一个元素作为输入的时候,总是停机,并在给定的输入不属于 S 的时候永不停机。

这也是递归可枚举集合的常见定义。

例子[编辑]

性质[编辑]

如果 AB 是递归可枚举集合,则 ABABA × B 是递归可枚举集合。集合 A递归集合,当且仅当 AA 补集二者是递归可枚举集合。递归可枚举集合一个可计算函数下的原像是递归可枚举集合。

引用[编辑]