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

问题描述：

我想知道递归和递归枚举语言在停止和图灵机方面有什么区别。我知道递归可枚举语言是递归语言的子集，但我不确定这种差异。递归和递归枚举语言有什么区别

可能更适合http://cstheory.stackexchange.com或http://cs.stackexchange.com – nawfal

我投票结束这个问题作为题外话，因为它是关于计算理论，而不是节目。 –

@RaymondChen我认为有“理论”和“计算理论”标签的事实证明我的问题是正确的。 – Bren

答

您有R和之间RE向后的关系：- [R是RE的（适当的）子集。基本上，递归语言就是你总有一个决定因素。

回想一下递归可枚举语言的定义：部分决定器存在;也就是说，一个图灵机可以根据你的语言正确地接受/拒绝这个词，或者如果这个词不是你的语言，它可能会永远循环。

相反，递归语言是一个总决定器存在的一种语言，即永远不会循环的一种语言，并且总是停止在接受状态或拒绝状态。

把这两个定义放在一起，显然递归语言也是递归枚举的，因为总决策者也是部分决定者（它从来没有“选择”循环而不是停止正确答案）。