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

Question

如何找到升补，

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)的元素是真的iff x有会员所需的财产S，是

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，则它们也需要属于L的补码。