theory - 图灵可判定和协同图灵可判定之间的区别

Question

我真的很难理解这两者之间的区别。从我的教科书中，它基本上通过说来描述差异

如果一种语言是图灵可识别语言的补充，则它是共同图灵可识别的。

我想我不明白这个定义的一部分是：当它是图灵可识别语言的补充时，它意味着什么？

您如何确定它是否是另一种语言的补充？

Answer 1

（注意-术语“图灵可判定”和“共同图灵可判定”是同一件事。但是，“图灵可识别”和“图灵可识别”并不相同，这就是我决定的在我的回答中涵盖。这样做的原因是，如果一种语言是可判定的，那么它的补语也必须是可判定的。可识别的语言也是如此。）

直观地说，如果存在某种计算机程序，给定该语言中的字符串，可以确认该字符串确实在该语言中，则该语言是图灵可识别的。如果字符串不在该语言中，该程序可能会无限循环，但如果您给它一个语言中的字符串，则可以保证始终最终接受。

虽然如果一种语言是图灵可识别语言的补充，那么它确实是共同图灵可识别的，但这个定义并不能说明正在发生的事情。直观地说，如果一种语言是 co-Turing 可识别的，这意味着有一个计算机程序，给定一个字符串不在语言中，最终将确认该字符串不在该语言中。但是，如果字符串确实在语言中，它可能会无限循环。这样做的原因很简单——如果某个字符串 w 不包含在可共同图灵识别的语言中，则该字符串 w 必须包含在该可共同图灵识别的语言的补语中，（根据定义）必须是图灵可识别的。由于 w 在图灵可识别的补码中，因此必须有一些程序可以确认 w 确实在补码中。因此，该程序可以确认 w 不是原始的协同图灵可识别语言。

简而言之，图灵可识别性意味着有一个程序可以确认字符串 w 是一种语言，而图灵可识别性意味着有一个程序可以确认字符串 w不是该语言。

希望这可以帮助！

Answer 2

让我来解释一下为什么可判定和可共同判定在一些不同的用法上意味着相同。在这里有经验，如果我走错了路，请告诉我：

如果我们有一组形成 L 的字符串 S。那么 S' 将形成 L'。现在，L 是可判定的意味着我们有算法 / TM 可以确认任何字符串 s∈S 属于 L 并且 s'∈S' 不属于 L。同样的算法会告诉我们 s∈S 不属于 L' 和 s '∈S' 属于 L'。所以，换句话说，我们对 L' 有完全相同的定义。因此，可判定语言概念的补语没有这种不同的含义。因此，可判定语言和可共同判定语言都被认为是相同的。

Answer 3

一种语言是可识别的，如果有一个图灵机将停止并仅接受该语言中的字符串，并且对于不在该语言中的字符串，TM 要么拒绝，要么根本不停止。注意：没有要求图灵机应该为非该语言的字符串停止。

一种语言是可判定的，如果有一个图灵机将接受该语言中的字符串并拒绝该语言中的字符串。