8.5.2. Проблема остановки

Рассмотрим вопрос о существовании такого алгоритма, который для произвольной программы и начальных данных для нее позволяет ответить на вопрос: "заканчивается работа программы на заданных исходных данных за конечное число шагов или нет?".

Сформулированная задача называется проблемой остановки. Переформулируем эту проблему в терминах разрешимости множеств.

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

Начальные данные для программы P будем представлять натуральными числами. Тогда можно считать, что программа с текстом P вычисляет одноместную числовую функцию f: N  N, совпадающую с некоторой функцией f_i(x) из последовательности (3), содержащей все одноместные вычислимые числовые функции.

Определим множество:

R₁ = {(m, n) | значение f_m(n) определено}.

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

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

ТЕОРЕМА 8.4

Множество R₁ неразрешимое.

Доказательство

Предположим противное. Пусть характеристическая функция множества R₁: (x₁, x₂)= является вычислимой.

Поскольку  вычислимая, то вычислима и функция

g(x) = (x, x).

Определим вспомогательную функцию:

d(x) = .

Функция d называется диагональной. Для каждого значения своего аргумента, равного x, она определена тогда и только тогда, когда значение f_x(x) не определено.

То есть d отлична от любой функции последовательности (3) всех одноместных частично-рекурсивных функций.

С другой стороны d получается из вычислимой числовой функции с помощью программно реализуемых (вычислимых) операций и поэтому является вычислимой.

Следовательно, d должна совпадать с одной из функций в последовательности всех одноместных частично-рекурсивных функций (3).

Полученное противоречие означает, что предположение о разрешимости множества R₁ является неверным.

Следовательно, R₁  это неразрешимое множество.

Доказательство окончено.

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

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

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

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

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

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

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

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