Что значит передать машину и ее описание в качестве входных данных в задаче об остановке?

Почему в доказательстве проблемы остановки мы должны передавать машину и ее описание в качестве входных данных?

Например, я мог бы передать описание машины и некоторые другие входные данные (не саму машину), и все же доказательство от противного сработало бы.

Например, скажем, H (a, b) дает ответ «да», если a останавливается на «b», и «нет» в противном случае.

Теперь мы создаем другую машину «H*», которая делает противоположное тому, что делает H.

Остановка H означает, что H* переходит в бесконечный цикл, а H не останавливается, подразумевает, что H* останавливается.

Теперь вместо передачи H(H*, H*); если бы я прошел H(H*, X), то это означало бы, что H* остановится, если H* не остановится на X, и наоборот (все же это было бы доказательством от противного).

Я не обязательно вижу идею передачи H(H*, H*) вместо того, чтобы просто передавать H(H*, X) для некоторого X. Разве доказательство не сработает в последнем случае?


turing-machines computability automata
person sayantan dasgupta    schedule 09.11.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Например, пусть H(a, b) дает ответ «да», если a останавливается на b, и «нет» в противном случае.

Теперь мы создаем другую машину H*, которая делает противоположное тому, что делает H.

Дело в том, что это не всегда возможно. Как показывает проблема остановки, рекурсивно перечислимые языки не замкнуты относительно дополнения. Поэтому для некоторых их дополнений такого H* не существует, например, для проблемы остановки.

Проблема при построении H* заключается в том, чтобы определить, когда H входит в бесконечный цикл. Алгоритма для этого нет. Тем не менее H* в принципе может существовать; но проблема остановки — это один из примеров множества, для дополнения которого можно доказать, что не может существовать перечисляющая ТМ.

Если бы класс был закрыт при дополнении, возможно, ваш аргумент прошел бы.

person Peter Leupold    schedule 10.11.2018