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

或者等价的说,

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

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

定义

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

f ( x ) = { 0 if   x S undef/does not halt   if   x S {\displaystyle 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 {\displaystyle S} f {\displaystyle f} 的域:

d o m ( f ) = S {\displaystyle \mathrm {dom} (f)=S}

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

集合 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} 的值域:

r n g ( f ) = S {\displaystyle \mathrm {rng} (f)=S}

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

注解

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

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

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

例子

性质

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

引用

www.zuoweixin.com
问题反馈联系QQ:暂无联系方式,也可发qq邮箱。