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

Question

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

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

Например, скажем, 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. Разве доказательство не сработает в последнем случае?

Answer 1

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

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

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

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

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