什么是递归可枚举集？

Question

关于该主题的维基百科文章似乎有很多讨论(和混淆).谷歌抛出的其他结果无法免费公开使用.

我会对你们要说的话感兴趣.

Answer 1

这里有一个定义:递归可枚举集是一个集合,你可以在其中编写一个程序,输出集合中的每个元素:E1,E2,E3 ......如果这个程序永远不会停止,那也没关系.

人们通常在语言的背景下谈论这个问题.递归可枚举语言是一种语言,您可以编写一个程序来写出该语言中的每个有效字符串.语言只是一组字符串,因此"基数为10的所有素数的集合"是一种有效的语言.

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

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

通常,更容易证明集合或语言是递归可枚举的或递归的,但更难以证明它不是递归的而是递归可枚举的.

Answer 2

这个概念最好通过示例和与递归集的比较以及不同定义的比较来说明.所以我会这样做:我先给你举例,然后给你不同的(但等价的)定义.

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

示例1:所有素数的集合

您可以编写一个算法,该算法将自然数作为输入并返回是或否的答案(是的意思是"是的,该输入是素数",没有意义"否,该输入不是素数.").该算法易于编写.如果您不打算优化以获得更好的性能,那么非常简单.因为您可以编写一个总是完成并给出是或否的答案的算法,所有素数的集合称为可判定集(也称为递归集).它被称为可判定的,因为你可以决定自然数是否是素数.请注意,如果您想证明一个集合是一个可判定的集合,您只需要提出一个总是完成并给出正确答案的算法,而您不需要优化性能.让我们不要理解为什么它被称为递归.

示例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

伪代码中的算法有一些好的和一些坏的.

坏事:如果输入不是主要差距,它将永远不会完成.它永远不会回答否定的答案.

好处:如果它返回肯定答案,你肯定知道输入是一个主要差距,反之亦然.

该集合是半可见集合(也称为递归可枚举集合)的示例.如果输入素数差距并且等待足够长时间,算法将始终给出肯定确认,但如果您输入的数字不是主要差距,则算法永远不会给您否定确认.

定义:如果有一个算法接受输入并且返回yes或者返回no或者从不返回(由于无限循环或错误),并且如果该算法在给定集合中的输入时返回yes,则set是半可见集合,并且如果该算法在给定不在集合中的输入时永远不会返回yes.

所有圆都是椭圆形,所有可判定的集都是半可分组.

通过一些思考,您可能会意识到算法是否允许有时正确返回并不是最终的定义并不重要.更多的想法,你也可能意识到,无论你是否允许错误,也无关紧要.这些实现使我们能够提出一个等效,更简单但稍微不那么直观的定义:

不太直观的定义:如果有一个算法接受输入并且该算法返回(即程序终止),当且仅当给定集合中的输入时,集合才是半集合.

现在让我们谈谈可列表集.如果有一个算法可以打印集合中的所有元素(没有其他内容),则集合是可列表集合.当然,如果必须打印无限多个元素,该算法永远不会完成.有了一些想法,您可能会发现,只要您有一个算法来打印集合中的所有数字,有时多次打印相同的数字,您可以修改算法,使其只打印一次所有数字.请注意,该定义并未说算法必须首先打印最小元素,然后打印第二个最小元素,依此类推.我为什么要谈论可列表集？

定理:当且仅当它是半可设置的集合时,集合是可列表集合.

让我们不要说明为什么这是真的(或许可以提出一个问题吗？),但我要提一下,这就是"递归枚举"这个短语的原因:你可以枚举这个集合,你可以列出所有元素一个接一个,"递归"只是意味着"用算法".

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

示例3.作为Python函数定义的所有ASCII字符串的集合,不带参数并保证返回.(为简单起见,我们还要排除Python函数调用库来执行一些特定于硬件的东西)

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

示例结局.当斯大林掌权时,一套良好的苏维埃政府政策就像一个半自杀的政策.有人是政府的顾问之一.斯大林会问他,"我对新政策有所了解.这个想法是等等等等.这是一个好政策吗？" 一个简单的是或否的问题.经过几天的分析表明政策确实很好,他会回答是的.如果政策不好怎么办？他有"不要说谎"的原则,但他也知道那些对斯大林说不的人会发生什么.每当斯大林说"你有没有决定这项政策是否合适？自从我就此提出你的意见以来已经有好几个月了." 斯大林同志说:"给我更多时间思考."

Answer 3

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

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