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

Question

好像有很多discussion (和混淆)关于维基百科 article关于这个话题。谷歌抛出的其他结果不可免费公开使用。

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

Answer 1

这是一个定义:递归可枚举集是这样一个集合，您可以在其中编写一个程序，该程序将输出该集合中的每个元素:E1、E2、E3……如果该程序永不停止就可以了。

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

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

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

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