什么是可递归枚举集？

Question

什么是可递归枚举集？

recursioncomputer-scienceset

5

关于维基百科上该主题的文章，似乎存在很多讨论（和困惑）。谷歌搜索出来的其他结果不免费公开使用。

我很想知道你们有什么想法。

- user59634

3个回答

17

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

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

例1：所有质数的集合

您可以编写一个算法，它以自然数作为输入，并返回一个yes或no的答案（yes表示“是，该输入是质数”，no表示“不，该输入不是质数”）。这个算法很容易编写。如果您不费心优化性能，那么非常容易。因为您可以编写一个始终完成并给出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

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

坏处是：如果输入不是质数间隙，则它永远无法结束。它从不返回“否”的答案。

好处是：如果返回“是”的答案，您可以确定输入是质数间隙，反之亦然。

这个集合是半可定集（也称为递归可枚举集）。如果您输入一个质数间隙并等待足够长的时间，算法将始终给出肯定的确认，但是算法从不在输入不属于该集的情况下返回肯定的确认。

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

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

经过思考，您可能会意识到算法是否允许正确地返回“否”实际上并不重要。通过更多的思考，您还可以意识到是否允许错误也不重要。这些认识使我们能够提出一个等价、更简单但略微不太直观的定义：

不太直观的定义：如果存在一个算法，它接受一个输入，如果该算法返回（即程序终止），当且仅当给定输入集合中的输入时。

现在让我们谈论一下可列表集。如果有一种算法可以打印集合中的所有元素（而不是其他内容），则该集合是可列表集。当然，如果必须打印无限多个元素，那么该算法永远不会结束。经过一些思考，您可能会意识到，每当您有一种算法可以打印集合中的所有数字时，有时打印同一数字多次，您可以修改算法以使其仅打印所有数字一次。请注意，定义并没有说算法必须先打印最小元素，然后是第二个最小元素等等。我为什么要谈论可列表集？

定理：如果一个集合是可列表集，则它也是半可定集。

我们不深入探讨为什么这是真的（也许可以提出SO问题？），但是让我提一下，这就是“递归可枚举”一词的原因：您可以按顺序列出集合中的所有元素，“递归”仅表示“使用算法”。

那么，有没有不涉及数字的例子？

例如3.所有ASCII字符串的Python函数定义都不带参数且保证返回的集合。（为简单起见，让我们也排除调用执行某些硬件特定操作库的Python函数）

该集合是半可定集，因为您可以制作一个半决策算法。该算法只需模拟Python来运行Python函数，然后等待直到它完成为止。如果Python函数在您的仿真中返回，则您的算法返回“是”。那就是算法。我们能做得比那个算法还好吗？是的，制作一种检测某些情况下无限循环并返回否的算法。您是否能想出一种永远不会失败地检测到无限循环的算法？如果您能想出这样的算法，那么该集合将是可判定集。不幸的是，没有这样的算

- Jisang Yoo

2

递归可枚举集是指存在部分可计算算法来判断元素是否属于该集合（可以计算但不一定终止）的一种集合。

例如，确定一个项不在曼德博集合中是递归可枚举的。

- workmad3

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dietrich Epp · Accepted Answer

以下是对该内容的翻译:

一个可递归枚举的集合是指，你能够编写一个程序输出集合中每个元素（如E1、E2、E3等），即使这个程序永远不停止也没关系。

通常人们在语言的背景下谈论这一点。可递归枚举的语言是指，你可以编写一个程序，列出该语言中的每个有效字符串。语言只是一组字符串，所以“十进制质数的所有数字”是一个有效的语言。

但是，想象一下，如果你只是想检查并查看给定的字符串是否属于该语言，而不是生成语言中的所有字符串或集合中的所有元素。问题是，你永远无法确定该字符串是否不属于你的语言。如果你需要为这种语言编写编译器，你的编译器将在有效输入上运行良好，但在无效输入上，由于它在一个无限列表中搜索不存在的东西，导致编译器永远卡住。

“可递归语言”或“可递归集合”的集合是指，你能够编写一个程序来告诉你给定的输入是否属于该集合。所有可递归语言也是可递归枚举的，因为你可以列举每个字符串，并在它属于你的集合时输出它。可递归语言也称为可判定语言，因为你可以确定一个元素是否在其中。这在更一般的可递归枚举集合中并非如此。

通常情况下，证明一个集合或语言是可递归枚举的或可递归的要容易些，但证明它不是可递归却是可递归枚举的则要困难得多。