递归可枚举集

自然数集合S 被称为递归枚举的条件： 如果有一个部分递归函数的域为S，意思是当且仅当函数的输入属于S。

以下是自然数集合S 的所有等价属性 :

半定性:

• 集合S 是递归可枚举的，指的是S 是部分递归函数的域(共域)。
• 有一个部分递归函数 f 使得:

     

可枚举性:

• 集合S 是部分递归函数的范围。
• 集合S 是完全递归函数的范围或为空。如果 S 是无限的，函数可以选择为内射的。
• 集合S 的范围是原始递归函数或者空的。虽然 S 是无限的，在这种情况下重复值可能是必要的。

丢番图:

• 有一个整数系数多项式 p 和变量 x, a, b, c, d, e, f, g, h, i 属于自然数，就像：

     

(这个定义中的绑定变量的数量是已知的；可能用一个更小的数来定义所有的丢番图集合。)

• 从整数到整数有一个多项式，集合S 恰好包含其范围内的非负数。

半可数性和可数性的等价性可以通过以下技术获得 燕尾连接楔形接合。

递归可枚举集的丢番图特征虽然不如第一个定义简单直观，但由 Yuri Matiyasevich 作为消极解决方案的一部分 希尔伯特的第十个问题。丢番图集早于递归理论，因此在历史上是描述这些集的第一种方法(尽管这种等价在递归可枚举集引入三十多年后才被注意到)。

• 每一个 递归集 是递归可枚举的，但并非每个递归可枚举集都是递归的。对于递归集，算法还必须说明输入是否为 不 在集合中——递归枚举集合不需要这样做。
• A 递归枚举语言 是的递归可枚举子集 形式语言。
• 有效公理系统中所有可证明句子的集合是递归可枚举的集合。
• 马蒂亚斯维奇定理 声明每个递归可枚举集都是一个 丢番图集 (反之亦然)。
• 这 简单集合s是递归可枚举的，但不是递归的。
• 这 创意套装s是递归可枚举的，但不是递归的。
• 任何的 生产集 存在 不 递归枚举。
• 给定一个 哥德尔编号     在可计算函数中，集合     (哪里     是 康托配对函数 和     指示     定义)是递归可枚举的(参见固定 x)。该集合对 停机问题 正如它所描述的 每个输入参数 图灵机 暂停。
• 给定哥德尔编号     在可计算函数中，集合     是递归可枚举的。这个集合编码了决定函数值的问题。
• 给定一个部分函数 f 从自然数到自然数， f 是部分递归函数，当且仅当 f, 也就是说，所有对的集合     这样 f(x) 被定义，是递归可枚举的。

如果 A 和 B 是递归可枚举的集合 A ∪ B, A *: B 和 A × B (有序的自然数对映射到单个自然数 康托配对函数)是递归可枚举集。这 原图像 部分递归函数下的递归可枚举集是递归可枚举集。

集合是递归可枚举的，当且仅当它处于级别时    的 算术层次。

一套    叫做 共递归可枚举的 或者 co-r.e . 如果它 补充    是递归可枚举的。等价地，当且仅当一个集合处于水平时，它才是共r.e    算术层次的。

一套 A 存在 递归的 (同义词:可计算)如果且仅当两者都有 A 和的补充 A 是递归可枚举的。一个集合是递归的，当且仅当它是递增的总递归函数的范围或有限的。

一些递归可枚举集对是 有效分离的 有些不是。

根据 这 丘奇——图灵论文，任何可有效计算的函数都可以通过 图灵机，因此是一组 S 当且仅当存在一些 算法 这将产生 S。 然而，这不能被视为一个正式的定义，因为丘奇-图灵命题是一个非正式的猜想，而不是一个正式的公理。

递归可枚举集的定义为 领域 部分函数，而不是 范围 在当代文本中很常见。 这种选择的动机是，在广义递归理论中，例如 α递归理论已经发现，对应于域的定义更加自然。 其他文本使用枚举的定义，这相当于递归枚举集。