recursion - 什么是递归可枚举集？

Question

关于该主题的维基百科文章似乎有很多讨论（和混淆）。谷歌抛出的其他结果不可免费供公众使用。

我会对你们说的话很感兴趣。

Answer 1

这是一个定义：递归可枚举集合是一个集合，您可以在其中编写一个程序，该程序将输出集合中的每个元素：E1、E2、E3……如果这个程序永远不会停止也没关系。

人们通常在语言的背景下谈论这个。递归可枚举语言是一种语言，您可以在其中编写一个程序，以该语言写出每个有效字符串。语言只是一组字符串，因此“以 10 为底的所有素数的集合”是有效的语言。

然而，想象一下，您不想生成语言中的所有字符串或集合中的所有元素。您只想检查给定的字符串是否使用该语言。问题是您永远无法确定该字符串不是您的语言。如果你需要为这种语言编写编译器，你的编译器可以在有效输入上正常工作，但无效输入会使你的编译器永远挂起，因为它会在无限列表中搜索不存在的东西。

“递归语言”或“递归集”的集合是您可以编写程序告诉您给定输入是否在集合中的集合。所有递归语言也是递归可枚举的，因为您可以枚举每个字符串，然后在您的集合中输出它。递归语言也被称为可判定的，因为你可以确定一个元素是否在其中。对于更一般的递归可枚举集，情况并非如此。

一般来说，更容易证明一个集合或语言是递归可枚举的或递归的，但更难证明它不是递归的而是递归可枚举的。

Answer 2

这个概念最好通过示例和与递归集的比较以及不同定义的比较来说明。所以我会这样做：我先给你例子，然后给你不同的（但等价的）定义。

首先，请注意，从技术上讲，我们将形容词“递归可枚举”（也称为“半可枚举”）应用于自然数集。但是这个形容词也可以应用于一组整数，一组整数对，一组 Unicode 字符串。请注意，任何这些东西（整数、整数对、Unicode 字符串）都可以存储在计算机内存中。（不能存储在计算机内存中的东西包括任意（无限精度）实数和 0 或 1 的无限序列）

示例 1：所有素数的集合

您可以编写一个算法，将自然数作为输入并返回是或否的答案（yes 表示“是，该输入是素数”，no 表示“不，该输入不是素数。”）。这个算法很容易写。如果您不费心优化以获得更好的性能，这非常容易。因为您可以编写一个始终完成并给出是或否答案的算法，所以所有素数的集合称为可判定集合（也称为递归集合）。它被称为可决定的，因为你可以决定自然数是否是素数。请注意，如果您想证明一个集合是一个可判定集合，您只需要提出一个始终完成并给出正确答案的算法，您不需要优化性能。让我们不要讨论为什么它被称为递归。

示例 2.素数间隙是两个连续素数之间的差。例如，13 是素数，下一个素数是 17，因此它们的差 4 是素数间隙。我们的第二个例子是所有素数缺口的集合。

你能写一个算法来检查一个数字是否是质数间隙吗？下面的伪代码怎么样？

input: x

set i to 1
loop
  check primeness of i, i+1, ..., i+x
  if only i and i+x among them are primes, return yes.
  otherwise, increment i by 1 and go to start of loop

伪代码中的算法有好有坏。

坏处：如果输入不是主要间隙，它将永远不会完成。它永远不会返回否定的答案。

好处：如果它返回“是”的答案，您肯定知道输入是质数间隙，反之亦然。

该集合是半可判定集合（也称为递归可枚举集合）的示例。如果您输入一个质数间隙并等待足够长的时间，该算法将始终给您一个肯定的确认，但如果您输入一个不是质数间隙的数字，该算法永远不会给您一个否定的确认。

定义：一个集合是一个半可判定集合，如果有一个算法接受一个输入并且返回是或返回否或从不返回（由于无限循环或错误）并且如果该算法在给定集合中的输入时返回是，并且如果该算法在给定不在集合中的输入时永远不会返回“是”。

所有的圆都是椭圆，所有可判定的集合都是半可判定的集合。

经过一番思考，您可能会意识到算法是否允许有时正确返回 no 对于最终的定义并不重要。通过更多的思考，您可能还会意识到是否允许错误对于定义也无关紧要。这些实现使我们能够提出一个等价的、更简单但不太直观的定义：

不太直观的定义：一个集合是一个半可判定集合，如果有一个算法接受一个输入，并且如果该算法返回（即程序终止）当且仅当给定集合中的一个输入。

现在让我们谈谈可列表集。如果有一种算法可以打印集合中的所有元素（仅此而已），则集合是可列出的集合。当然，如果必须打印无限多的元素，该算法永远不会完成。有了一些想法，您可能会意识到，每当您有一个算法来打印集合中的所有数字时，有时会多次打印相同的数字，您可以修改算法，使其只打印一次所有数字。请注意，定义并没有说算法必须首先打印最小的元素，然后是第二小的元素，依此类推。为什么我在谈论可列出的集合？

定理：一个集合是一个可列集当且仅当它是一个半可判定集合。

让我们不讨论为什么这是真的（也许为此提出一个 SO 问题？），但让我提一下，这就是“递归可枚举”这个短语的原因：您可以枚举集合，因为您可以列出所有元素一个一个，“递归”只是意味着“使用算法”。

一个不涉及数字的例子怎么样？

示例 3. 所有 ASCII 字符串的集合，它是一个不带参数且保证返回的 Python 函数定义。（为简单起见，我们还排除了调用库的 Python 函数，这些库执行一些特定于硬件的操作）

这个集合是一个半可判定集合，因为你可以制定一个半判定算法。该算法只需要模拟 Python 来运行 Python 函数，然后等待它完成。如果 Python 函数曾经在您的仿真中返回，那么您的算法将返回 yes。这就是算法。我们能比那个算法做得更好吗？是的，制作一个在某些情况下检测无限循环并返回否的算法。你能想出一个永远不会检测到无限循环的算法吗？如果你能想出这样一个算法，这个集合将是一个可判定集合。可悲的是，没有这样的算法，我们可以证明这一点。

示例结局。当斯大林掌权时，苏联政府的一套好的政策就像一个半决定性的一套。有人是政府的顾问之一。斯大林会问他，“我有一个新政策的想法。这个想法是胡说八道。这是一个好政策吗？” 一个简单的是或否的问题。经过几天的分析，他的回答是肯定的，政策确实是好的。如果政策不好怎么办？他有“永远不撒谎”的原则，但他也知道那些对斯大林说不的人会怎么样。每当斯大林说“你决定好政策好不好了吗？我已经好几个月没有征求你的意见了。” 他会说：“给我更多的时间思考，斯大林同志。”

Answer 3

递归可枚举集合是一个集合，其中有一个部分可计算的算法来决定一个元素是否包含在集合中（它可以被计算但它不一定会终止）

例如，确定一个项目是否不在mandlebrot 集中是递归可枚举的。