递归可枚举集合

跳转到: 导航, 搜索

在可计算性理论或更少称谓的递归论中，可数集合 S 被称为递归可枚举的、计算可枚举的、半可判定的或可证明的，如果

或者等价的说，

包含所有可递归枚举集合的复杂性类是 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.$

换句话说， $S$ 是 $f$ 的域:

dom(f) = S

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

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

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

rng(f) = S

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

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

可数集合

S

被称为递归可枚举的，如果有一个图灵机，在给定

S

的一个元素作为输入的时候，总是停机，并在给定的输入不属于

S

的时候永不停机。

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

所有递归集合都是递归可枚举的，但不是所有递归可枚举集合都是递归的。
递归可枚举语言是在形式语言的字母表上所有可能词的集合中的递归可枚举集合。
Matiyasevich 定理声称所有 Diophantine 集合都是递归可枚举的。
简单集合是递归可枚举的但不是递归的。
创造集合是递归可枚举的但不是递归的。
生产集合不是递归可枚举的。
对于偏可计算函数 $φ$ 的哥德尔数 $i$ ，则集合 $\{\langle i,x \rangle | \phi_i(x) \downarrow\}$ (带有 $\langle i,x \rangle$ 康拖尔配对函数) 是递归可枚举的。这个集合编码了停机问题，因为它描述了每个图灵机停机的输入参数。
给定一个偏可计算函数 $φ$ 的哥德尔数 $x$ ，则集合 $\lbrace \left \langle x, y, z \right \rangle | \phi_x(y)=z \rbrace$ 是递归可枚举的。这个集合编码判定一个函数值的问题。