递归可枚举集合

在可计算性理论中，一组自然数 S 被称为可计算可枚举 (c.e.)、递归可枚举 (r.e.)、半可判定、部分可判定、可列出、可证明或图灵可识别，如果：

• 存在一种算法，使得算法停止的输入数字集恰好是 S。

或者，等价地，

• 有一种算法可以枚举 S 的成员。这意味着它的输出只是 S 的所有成员的列表：s1, s2, s3, ...。 如果 S 是无限的，这个算法将永远运行。

xxx个条件说明了为什么有时使用术语半可判定的。 更准确地说，如果一个数字在集合中，可以通过运行算法来决定，但如果数字不在集合中，算法将永远运行，并且不会返回任何信息。 完全可判定的集合是可计算的集合。 第二个条件说明了为什么使用可计算可枚举的。 缩写词 c.e. 和 r.e. 经常使用，甚至在印刷中，而不是完整的短语。

在计算复杂性理论中，包含所有可计算可枚举集的复杂性类是 RE。 在递归理论中，c.e. 的格子。 包含下的集合表示为 E {displaystyle {mathcal {E}}} 。

一个自然数集合 S 被称为可计算可枚举的，如果存在一个定义域恰好是 S 的部分可计算函数，这意味着当且仅当它的输入是 S 的成员时，该函数才被定义。

以下是自然数集合 S 的所有等价性质：

半可判定性：

• 集合 S 是可计算可枚举的。 也就是说，S 是部分可计算函数的定义域（协域）。
• 集合 S 是 Σ 1 0 {displaystyle Sigma _{1}{0}}（指的是算术层次）。

可枚举性：

• 集合 S 是部分可计算函数的范围。
• 集合 S 是总可计算函数的范围，或者是空的。 如果 S 是无穷大，则可以选择单射函数。
• 集合 S 是原始递归函数的范围或为空。 即使 S 是无穷大，在这种情况下也可能需要重复值。

丢番图：

• 存在一个整数系数和变量 x, a, b, c, d, e, f, g, h, i 的多项式 p，其范围在自然数范围内，使得 x ∈ S ⇔ ∃ a , b , c , d, e, f, g, h, i (p (x, a, b, c, d, e, f, g, h, i) = 0) 。 {displaystyle xin SLeftrightarrow 存在 a,b,c,d,e,f,g,h,i (p(x,a,b,c,d,e,f ,g,h,i)=0).}（这个定义中的绑定变量的数量是目前已知的最多的；它可能是一个更小的数量可以用来定义所有的丢番图集。）
• 存在从整数到整数的多项式，使得集合 S 恰好包含其范围内的非负数。

半判定性和可枚举性的等价性可以通过燕尾技术获得。

可计算可枚举集的丢番图特征虽然不像xxx个定义那样直接或直观，但被 Yuri Matiyasevich 发现为希尔伯特第十问题的否定解决方案的一部分。 丢番图集合早于递归理论，因此在历史上是描述这些集合的xxx种方法（尽管这种等价性在可计算可枚举集合引入后三十多年才被注意到）。

• 每个可计算集都是可计算可枚举的，但并不是每个可计算可枚举集都是可计算的。 对于可计算集，算法还必须说明输入是否不在集合中——这对于可计算可枚举集来说不是必需的。
• 递归可枚举语言是形式语言的可计算可枚举子集。
• 有效呈现的公理系统中所有可证明句子的集合是可计算的可枚举集合。

• Matiyasevich 定理指出每个可计算可枚举集都是丢番图集（反之亦然）。
• 简单集是可计算可枚举但不可计算的。
• 创意集可计算枚举但不可计算。
• 任何生产集都不是可计算的可枚举的。