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