computer-science - 递归和递归可枚举语言有什么区别

Question

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

Answer 1

你有 R 和 RE 之间的反向关系:R 是 RE 的(适当的)子集。基本上，递归语言是一种你有一个总决策者的语言。

回想一下递归可枚举语言的定义，其中一个 部分决策者 存在；也就是说，一个图灵机输入一个字母表上的单词，它将根据您的语言正确接受/拒绝该单词，或者如果该单词不在您的语言中，它可能会永远循环。

相比之下，递归语言是一种 总决策者存在，即永远不会循环，并且总是在接受或拒绝状态中停止。

将这两个定义放在一起，很明显递归语言也是递归可枚举的，因为总决策器也是部分决策器(它只是从不“选择”循环而不是用正确的答案停止)。