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

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是 Universe 的一个元素,U并且当且仅当具有成员资格所需的属性时为P(x)真, 是xS

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

，其中x'是全域的一个元素，U是~P(x)的否定，P(x)并且当当且仅当x'不具有成员资格所需的属性时为真S。

在您的示例中：

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

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

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