Доказательство окончено. Доказанная теорема означает, что не существует общего алгоритма, который позволит избежать появления бесконечных вычислений при работе произвольных программ

Доказанная теорема означает, что не существует общего алгоритма, который позволит избежать появления бесконечных вычислений при работе произвольных программ, с помощью предварительной проверки определенности значений функций, вычисляемых программами, на начальных данных.

Распознавать такие ситуации до запуска программ для всех случаев нельзя, поскольку не существует соответствующего алгоритма.

Тем не менее, для некоторых конкретных и простых программ проблема остановки может иметь решение.

Например, такими являются учебные программы, составляемые студентами при изучении основ программирования.

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

Действительно, пусть определенная ранее универсальная функция h(x₁, x₂) вычисляется некоторой программой P. Тогда вычисление программы P на начальных данных (m, n) заканчивается тогда и только тогда, когда значение h(m, n) определено.

То есть значение h(m, n) определено тогда и только тогда, когда (m, n) Î R₁.

Поскольку R₁ - неразрешимое множество, то проблема остановки для программы P является алгоритмически неразрешимой.