Зачем нам нужно использовать часть отрицания в Turing's Halting Proof?

Question

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

Спасибо!

Answer 1

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