为啥递归可枚举语言被称为“递归可枚举”
【为啥递归可枚举语言被称为“递归可枚举”】 递归可枚举的意思就是，你可以用类似穷举的算法在有限时间内判定一个元素属于该集合；对于不属于该集合的元素，算法“可能”不会在有限时间内有结果。用图灵机的说法就是使图灵机停机的集合。
■网友
因为这种语言中的所有字符串可以被当前字符集下的递归函数一一列举。
■网友
泻药。我只从计算理论的角度答下自己的理解...在计算理论里，递归是一个重要的话题，从一开始的正则语言，到后面的图灵机，递归无处不在，为什么?因为递归代表着一种计算的可行性。正如我们看到的那样，语言L递归和图灵机判定语言L是等价的，这里判定的意思是对于任意字符串w属于L，图灵机会在输入w上停机，对于不属于L的w，图灵机也停机。那什么叫语言L递归可枚举呢?考虑一个问题：验证字符串w属于语言L。这好办，我们把字符串输入图灵机，然后看图灵机停不停机，只要停机，那就说明w属于L，至于图灵机此时的停机状态，根本不必管。换句话说，只要w确实是属于L的，那么验证这件事就一定能办到，对于L中的元素，我一一验证，总有一天会验证到这个w，这就是可枚举的意思（注意这里的前提是我们已经知道它在L里了，所以和未来有个美妙的契约：我不停地找你，总有一天能找到你，哪怕海枯石烂，天荒地老(??ω??)??至于怎么知道的?靠图灵机啊）。但是，对于另一个判定问题：验证w不在L里就遇到麻烦了，因为图灵机可能永不停机，而永不停机不代表它不是，只是你永远不知道。总结起来，这就是所谓的半判定或者叫部分判定，所以递归可枚举和图灵机半判定等价。更进一步，还可以证明递归可枚举和图灵可枚举是等价的。图灵可枚举的意思是，对于图灵机M的某个固定状态q，语言L={w: (s,\u0026gt;空格)|-*(q,\u0026gt;空格w)}，也就是说会从初态最终变到状态q字符串w这样的格局，w属于语言L。这里可枚举的含义就更清晰了，图灵机直接从无到有把L的字符串生成了一遍，不就是在枚举它吗...
■网友
我觉得应该站在工业生产的角度来理解这个事情：
1、枚举的真实含义就是搬砖，枚举的动作告诉大家砖要一块一块地搬，所以为什么那么多程序猿996要加班搬砖，本质上是由枚举来决定的，一些爱好者学了点编程就觉得很好玩很有趣，以为自己了不起了，殊不知只不过是用积木搭了个玩具，真实的情况就是需要不停地搬砖（枚举）
2、递归的含义就是我们在软件工程里面经常说的复用和重复，现在很多工程师都是在复用上面下功夫。
真实的需求往往是很复杂的，复杂度超乎很多人的想象，很多时候没办法直接复用，最后还是得回归到枚举搬砖上面来。也正是这个巨大的复杂度创造了一个巨大的搬砖空间，才能容纳这么多程序猿进行就业。简而言之，递归可枚举揭露了计算的本质和真相，告诉计算其实是非常原始的一块块砖，等着一堆程序猿拿来搭建摩天大厦，真正的智能仍在程序猿身上，真正的难度和技术含量在于真实业务 到 底层计算 的分解映射的这个过程。
推荐阅读
- 为啥看到书柜上的藏书会有心旷神怡的感觉
- 为啥知乎上普便有一种【我在北上广深打工，所以拥有更好的视野】这样的错觉
- 为啥工商银行的用户体验如此之差
- 汽车|看了中消协4S店服务测评调查结果，终于知道法系车为啥卖不好了
- 你为啥从窝窝商城离职?
- 为啥5G和2.4G默认的BSSID是相同的
- 为啥电器实体店的价格比淘宝贵那么多
- 现在在线学习视频有很多了，为啥大部分人还是喜欢下载下来观看
- 为啥到现在你还没有女朋友 ?
- 天赐的声音|33岁张雨绮为啥总离婚？看过这些照片就明白了，都是性感惹得祸