Как найти дополнение к следующему языку?

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 имеет свойство, необходимое для членства в S, является

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

, где x' это элемент вселенной U а также ~P(x) это отрицание P(x) и верно, если x' не имеет имущества, необходимого для членства в S,

В вашем примере:

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

Сначала мы должны определить, что такое вселенная. Если принять вселенную за все строки, которые представляют кодировки ТМ, ваш ответ близок, но, возможно, не верен, в зависимости от ваших определений. Было бы более однозначно правильно, если бы вы сказали "не принимает" вместо "отклоняет", так как ТМ может бесконечно зацикливаться на палиндроме, никогда не принимая и не отвергая его.

Если, с другой стороны, юниверс был ТМ, которые останавливаются на всех входах, ваш ответ верен. С другой стороны, если бы в юниверсе были все двоичные строки, ваш ответ был бы неправильным, если бы каждая возможная двоичная строка не была допустимой кодировкой некоторой TM в вашей кодировке. Если бы были некоторые кодировки, которые не были действительными ТМ, они должны были бы принадлежать к дополнению L также.