Предположим, что существует детерминированная машина Тьюринга, например. который запускается в полиномиальное время и решает язык L.Если детерминированная машина Тьюринга решает язык L, означает ли это, что он также решает L's дополнение?
Это автоматически означает, что он также решает язык языка L?
Когда мы говорим язык комплемента L'с, я, конечно, имею в виду на язык K такое, что:
K = {x : x not in L}
Предположит, что у вас есть детерминированный машин Тьюринга с ограниченным временем работы, вы можете легко построить Тьюринг машина, которая принимает дополнение L, отменяя его ответ. Однако для этого требуется, чтобы машина Тьюринга останавливалась на каждом входе (что имеет место, если он решает язык L и таким образом останавливается на каждом входе). Сама машина не является решателем для дополнения L, потому что решающий язык должен принять ее.
В общем случае машина, которая просто принимает (должна останавливаться только на входах с «да»), но не решает (останавливается на каждом входе), язык L может попасть в бесконечный цикл для входов, которые не являются в L, поэтому, возможно, нет явного «нет» -сервера, который можно было бы отменить.
Что означает «решение» в этом контексте? – User