问图灵决策与协同决策的差异

EN

(注：“图灵可判定”和“共同决定”是同一回事。然而，“图灵-可识别”和“共同-图灵-可识别”是不一样的，这是我决定在我的答案中涵盖的。这样做的原因是，如果一种语言是可分辨的，那么它的补语也必须是可分辨的。对于可识别的语言，情况并非如此。)

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

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

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

希望这能有所帮助！

让我来解释一下，为什么可分词和共同分词的意思是相同的，有些不同的用法。这里有经验，如果我走错了路，请告诉我：

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

语言是可识别的，如果有图灵机，它将只停止并接受该语言中的字符串，对于非语言的字符串，TM要么拒绝，要么根本不停止。注意:没有要求图灵机停止使用非语言中的字符串。

语言是可决定的，如果有图灵机，它将接受语言中的字符串，而拒绝该语言中的字符串。