Не существует машины Тьюринга , решающей проблему остановки для произвольной наперед неизвестной машины Тьюринга .
ДОКАЗАТЕЛЬСТВО.
A. От противного. Предположим, что машина Тьюринга существует. Тогда необходимо записать на ленту , где
— начальное и заключительное состояние машины Тьюринга ,
— система команд исследуемой машины Тьюринга, закодированная как в теореме 2.2 об универсальной машине Тьюринга.
— начальное состояние машины Тьюринга.
— входные данные для машины Тьюринга, которые так же закодированы.
B. Построим вспомогательную машину Тьюринга такую, что останавливается, если машина Тьюринга не останавливается и машина Тьюринга не останавливается, если машина Тьюринга останавливается.
Для построения машины Тьюринга используем систему команд машины Тьюринга , добавив новое заключительное состояние и две команды и .
Если существует машина Тьюринга , то и существует машина Тьюринга так как машина Тьюринга получена из машины Тьюринга вполне конструктивным образом, то есть легко может быть построена машина Тьюринга, которое может сделать это преобразование.
C. Поставим задачу самоприменимости, то есть применим машину к самой себе. , где в качестве исходной строки записана система команд машины Тьюринга .
Машина Тьюринга останавливается в том случае, когда машина Тьюринга не останавливается наоборот.
D. В пункте С доказательства получено противоречие. В связи с тем, что машина Тьюринга получена из машины Тьюринга конструктивными средствами и при этом никак не связана с конкретным видом команд машины Тьюринга , то можно сделать вывод о том, что никакая машина Тьюринга решающая проблему остановки невозможна.
Окончание доказательства.

Замечание. Алгоритмически неразрешимой проблемой является определение результативности алгоритмов.

Замечание. Теорема 2.3 утверждает лишь, что отсутствует единый алгоритм решающий проблему остановки. При этом вовсе не исключается возможность решения этой проблемы в частных случаях, когда задан конкретный алгоритм, но каждый раз решение этой задачи может быть выполнено различными средствами.

Замечание. Неразрешимость общей проблемы остановки вовсе не снимает необходимость доказывать сходимость разрабатываемых алгоритмов и показывает, что поиск таких доказательств нельзя полностью автоматизировать.

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