图灵可判定和共图灵可判定的区别

Question

我真的很难理解这两者之间的区别。从我的教材中，它基本上通过以下方式描述了它们之间的区别：

如果一门语言是图灵可识别语言的补集，则该语言为共同图灵可识别语言。

我猜我不理解这个定义的部分是：当它是一个图灵可识别语言的补集时，这意味着什么？

你如何确定它是否是另一种语言的补集？

- Jason M.

Answer 1

（注：术语“图灵可判定”和“共图灵可判定”是同一事物。但是，“图灵可识别”和“共图灵可识别”不同，我决定在回答中涵盖这一点。原因是如果一个语言是可判定的，则它的补集也必须是可判定的。对于可识别的语言则不适用此规律。）

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

虽然如果一个语言是某个图灵可识别语言的补集，则这个语言是共图灵可识别的，但这种定义并没有提供太多信息。直观地说，如果一个语言是共图灵可识别的，则意味着存在一个计算机程序，可以确认一个不属于该语言的字符串确实不属于该语言。如果给它一个确实属于该语言的字符串，该程序可能会无限循环。原因很简单 - 如果某个字符串w不包含在共图灵可识别语言中，则该字符串w必须包含在该共图灵可识别语言的补集中，这（根据定义）必须是图灵可识别的。由于w在图灵可识别补集中，因此必须存在某个程序，可以确认w确实在该补集中。因此，该程序可以确认w不属于原始的共图灵可识别语言。

简而言之，图灵可识别性意味着存在一个程序可以确认一个字符串w是否属于该语言，而共图灵可识别性则意味着存在一个程序可以确认一个字符串w不属于该语言。

希望这有所帮助！

- templatetypedef

---

这确实非常有帮助。我无法用言语表达我的想法，这使得确定实际定义变得困难 :) - Jason M.

Downvoter- 你能否解释一下这个答案有什么问题吗？我希望它尽可能地有用，但我不确定它有什么问题。 - templatetypedef

@templatetypedef 我猜你对这个比那个踩你的人更了解。 - Rob Neuhaus

你可能想要添加一种语言既是图灵可识别的又是共图灵可识别的这一重要性，因为这意味着可决定性。 - ramblinjan

如果我没错的话，我们可以说如果一种语言是图灵可识别的，那么它就是“递归可枚举”的。那么如果一种语言是共轭图灵可识别的，我们该如何描述它的递归可枚举性呢？它是“不可递归可枚举的”吗？ - Mahesha999

有可能一种语言是共同图灵认可的，也是递归可枚举的 - 这意味着它是可判定的！你有时会听到“co-RE”这个术语，用来描述那些共同递归可枚举的语言。 - templatetypedef

Answer 2

让我来告诉你为什么可判定和可共判定是指同一概念，只是用了不同的术语。如果有经验的人在这里，请告诉我是否有错：

如果我们有字符串集合 S，构成 L，则 S' 将形成 L'。现在，L 被认为是可判定的，意味着我们有算法/图灵机可以确认任何属于 L 的字符串 s，并且 s'∈S' 不属于 L。同样的算法将告诉我们 s∈S 不属于 L' 且 s'∈S' 属于 L'。因此，换句话说，我们对 L' 有完全相同的定义。因此，判定语言的补集概念并没有不同的含义。因此，可判定和可共判定语言被认为是相同的。

- MsA

Answer 3

如果存在一个图灵机，它将停止并仅接受该语言中的字符串，并且对于不属于该语言的字符串，TM要么拒绝，要么根本不停止，则该语言是可识别的。注意：对于不属于该语言的字符串，图灵机不一定需要停止。

如果存在一个图灵机，它将接受该语言中的字符串并拒绝不属于该语言的字符串，则该语言是可判定的。

- Avinash Singh

---

这个回答完全回避了被问的问题，只是给出了一些正式的定义。他要么不理解问题，要么回避了它。 - Muhammad Razib