Как программа превращает прогноз в противоречие
Представим проверяльщик, которому дают описание программы и её входные данные. Он всегда заканчивает работу и безошибочно отвечает: завершится ли эта программа или будет выполняться бесконечно. Именно обещание «для любой программы» делает задачу невозможной.
В доказательстве используют возможность передать программе её собственное описание — например, представить текст программы как данные. Строят особую программу: она обращается к проверяльщику с вопросом о программе, описание которой ей передали, а затем выбирает поведение, противоположное прогнозу. Если проверяльщик предсказывает остановку, программа входит в бесконечный цикл; если предсказывает бесконечное выполнение — завершает работу.
Теперь этой программе передают её собственное описание. Проверяльщик должен дать ответ о ней самой, но любой ответ приводит к обратному результату. Если он говорит «остановится», она не останавливается; если говорит «не остановится», она останавливается. Значит, универсального безошибочного проверяльщика с такими условиями быть не может.
Что именно доказывает эта ловушка
Это не означает, что нельзя понять поведение конкретной программы. Для многих простых случаев остановку легко установить, а анализаторы кода могут находить отдельные ошибки или гарантировать свойства в заданных пределах. Невозможна другая цель: алгоритм, который для всех программ и входных данных всегда выдаёт правильный ответ и сам гарантированно заканчивает проверку.
Поэтому разработчики инструментов вынуждены выбирать компромисс: проверять ограниченный класс программ, искать только некоторые виды зацикливания или иногда сообщать, что ответа нет. Ловушка важна не как необычный трюк, а как точная граница того, что вообще можно автоматизировать.
