ПРОБЛЕМА ОСТАНОВКИ

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

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

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

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

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

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

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

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