如何找到以下語言的補充？

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的補碼。