如何找到以下语言的补语？

Question

如何求 L 的补集，

L = {<M>: M is a TM, which accepts some palindrome}

求补码的一般规则是什么？ 我在想在这种特殊情况下会是

L_bar = {<M_bar> : M_bar is a TM, which rejects any palindrome .???

Answer 1

寻找语言补集（相对于某些已理解的宇宙U）的一般规则：

S = {x: P(x)}

，其中 x 是宇宙 U 的一个元素，P(x) 为真当且仅当 x 具有成为 [=18 成员所需的 属性 =]，是

S' = {x': ~P(x')}

，其中 x' 是宇宙 U 的一个元素，~P(x) 是 P(x) 的否定并且是真的当且仅当 x' 没有属性 需要加入 S。

在你的例子中：

L = {<M>: M is a TM, which accepts some palindrome}

首先要确定宇宙是什么。如果我们将宇宙视为代表 TM 编码的所有字符串，您的答案很接近但可能不正确，具体取决于您的定义。如果你说 "does not accept" 而不是 "rejects" 会更加明确正确，因为 TM 可以在回文上永远循环，永远不会接受或拒绝它。

另一方面，如果宇宙是所有输入都停止的 TM，那么您的答案是正确的。另一方面，如果宇宙都是二进制字符串，那么您的答案将是错误的，除非每个可能的二进制字符串都是您编码中某些 TM 的有效编码。如果有一些编码不是有效的 TM，它们也需要属于 L 的补码。