递归语言和可递归枚举语言有什么区别？

Question

14

我想知道递归语言和可递归语言在停机和图灵机方面的区别。我知道可递归语言是递归语言的子集，但除此之外我不确定区别。

我想知道递归语言和可递归语言在停机和图灵机方面的区别。可递归语言可以由图灵机接受并产生回答结果，而递归语言可以通过算法计算并得到结果。递归语言是可递归语言的超集，这意味着递归语言包含所有可递归语言，并具有额外的性质。

- Bren

3

也许更适合在http://cstheory.stackexchange.com或http://cs.stackexchange.com上讨论。 - nawfal

3

我投票关闭此问题，因为它涉及计算理论而非编程。 - Raymond Chen

10

我认为存在“理论”和“计算理论”标签的事实可以证明我的问题。 - Bren

3个回答

5

主要区别在于，在可递归枚举语言中，对于属于 L 语言的输入字符串，机器会停止计算。但对于不属于 L 语言的输入字符串，机器可能会停止计算，也可能不会。

当涉及到递归语言时，无论被机器接受与否，它都会停止计算。如果被接受，它将到达 (q accept) 并停止。如果未被机器接受，则直接到达 (q halt)。

- Abdulhakim Zeinu

1

停机问题是一个可枚举但不可判定的问题的典型例子。

在尝试分割复杂度类时，最好有一个例子属于其中一个类但不属于另一个类。

在这种情况下，典型的例子是对应于停机问题决策问题的语言:

HALT = 所有停机的图灵机/输入对

众所周知，停机问题不能被任何图灵机确定性地解决，因此语言HALT不属于R。

但显然，HALT属于RE。

我们回顾一下递归可枚举语言的定义：

一个可枚举语言是这样一个语言，即存在一个图灵机，在该图灵机上每个属于该语言的成员都会以yes输出停止，而非成员则可能永远运行下去。

因此，我们只需要使用模拟另一个图灵机（通用图灵机）的图灵机。那么该机器将在HALT的每个成员上停止，因此HALT属于RE。

仅凭这个事实就可以看出RE比R难得多：RE包含不可判定问题，对于这些问题设计算法是不可能的！而根据定义，R则没有这种问题。

非RE问题

同时查看两者的例子也很有帮助：

经典示例是HALT的补集：所有非停机TM/输入对的语言。

- Ciro Santilli OurBigBook.com

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

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

- Cactus · Accepted Answer

您将R和RE之间的关系弄反了：实际上，R是RE的（正确的）子集。基本上，递归语言是指具有完全决策器的语言。

回想一下，一个递归可枚举语言的定义是指存在一个部分决策器，即一个图灵机，它可以接受一个字母表中的单词作为输入，并根据您的语言正确地接受/拒绝该单词，或者如果该单词不在您的语言中，则可能永远循环。

相比之下，递归语言是指存在一个完全决策器的语言，即无论如何都不会循环，而总是以接受或拒绝状态停止。

将这两个定义并置，显然递归语言也是递归可枚举的，因为完全决策器也是部分决策器（它只是从不“选择”循环而不是以正确的答案终止）。