查看“递归可枚举集合”的源代码

{{no footnotes|time=2014-07-11T13:53:44+00:00}}
{{NoteTA
|G1 = IT
|G2 = Math
}}
'''递归可枚举集合'''（{{lang-en|Recursively enumerable set}}）是[[可计算性理论]]或更狭义的[[递归论]]中的一个概念。[[可数集合]]''{{lang|en|S}}''被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果 
*存在一个[[算法]]，只有当输入是''{{lang|en|S}}''中的元素时，算法才会中止。

或者等价的说，

*存在一个算法，可以将S中的成员枚举出来。也就是说该算法的输出就是 ''S'' 的成员列表:  ''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ...  如果需要它可以永远运行下去。

包含所有可递归枚举集合的[[复杂性类]]是 [[RE (复杂性)|RE]]。

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

== 定义 ==
可数集合 <math>S</math> 是递归可枚举的，如果存在一个[[偏函数|偏]][[可计算函数]] <math>f</math> 使得

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

换句话说，<math>S</math> 是 <math>f</math> 的[[定义域|域]]:
:<math>\mathrm{dom}(f) = S</math>
(注意这是偏函数的域的两种可能意义之一，是在递归论中所偏好的定义域。参见在[[偏函数]]中的讨论。)

集合 <math>S</math> 被成为 '''co-递归可枚举的'''或 '''co-r.e.'''，如果 <math>S</math> 的[[补集]]是递归可枚举的。

== 等价定义 ==
可数集合 <math>S</math> 被叫做'''递归可枚举的'''，如果存在着一个[[偏函数|偏]][[可计算函数]] <math>f :\subseteq \mathbb{N} \to S</math>，使得 <math>S</math> 是 <math>f</math> 的[[值域]]:

:<math>\mathrm{rng}(f) = S</math>

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

== 注解 ==

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

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

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

==例子==

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

==性质==

如果 ''A'' 和 ''B'' 是递归可枚举集合，则 ''A'' &cap; ''B''、''A'' &cup; ''B'' 和 ''A'' &times; ''B'' 是递归可枚举集合。集合 ''A'' 是[[递归集合]]，当且仅当 ''A'' 和 ''A'' 补集二者是递归可枚举集合。递归可枚举集合一个可计算函数下的[[原像]]是递归可枚举集合。

==引用==

* Rogers, H. ''The Theory of Recursive Functions and Effective Computability'', [[MIT Press]]. ISBN 0-262-68052-1; ISBN 0-07-053522-1.
* Soare, R. Recursively enumerable sets and degrees. ''Perspectives in Mathematical Logic.'' [[Springer-Verlag]], Berlin, 1987. ISBN 3-540-15299-7.
* Soare, Robert I. Recursively enumerable sets and degrees. ''Bull. Amer. Math. Soc.'' 84 (1978), no. 6, 1149–1181.


[[Category:递归论]]
[[Category:計算理論]]