Почему мы должны использовать отрицание в Доказательстве остановки Тьюринга?

Question

Почему мы должны использовать отрицание в Доказательстве остановки Тьюринга?

Например, допустим, у меня есть машина Тьюринга H, которая сообщает нам, остановится ли программа и ввод. Допустим, мы называем H на себя. Он должен дать ответ, поэтому, если он печатает "не останавливается", то не технически ли он останавливает печать этого утверждения? Или это просто всегда в теории распечатывать "останавливается"? У меня проблемы с тем, чтобы обернуть голову, призывая Н чисто к себе, без отрицания, и что бы это ни делало. Я понимаю, почему отрицание приводит к противоречию, но мне просто интересно, приводит ли следующий сценарий к противоречию.

Спасибо!

1

loops logic proof turing-machines halting-problem

Источник

user3813411 01 фев '15 в 07:24

1 ответ

Решение

Другие вопросы по тегам loops logic proof turing-machines halting-problem

user775806 01 фев '15 в 07:47 2015-02-01 07:47 · Accepted Answer · 2015-02-01 07:47

Вам нужно доказать, что H не существует. Вы показали, что H, примененный к самому себе, не может печатать "не останавливается". Но, как вы справедливо указываете, возможность того, что он печатает "действительно останавливается", не исключена. Там нет очевидного противоречия в этом. Таким образом, это применение H к себе не достаточно, чтобы доказать, что H не существует, нам нужно использовать другие методы. Неверно утверждать, что этот сценарий не приводит к противоречию. Это вероятно будет, если вы исследуете это дальше. Просто не сразу.