Рассмотрим вопрос о существовании такого алгоритма, который для произвольной программы и начальных данных для нее позволяет ответить на вопрос: "заканчивается работа программы на заданных исходных данных за конечное число шагов или нет?".
Сформулированная задача называется проблемой остановки. Переформулируем эту проблему в терминах разрешимости множеств.
Всякую программу будем рассматривать как представление алгоритма, вычисления значений числовой функции. Для определенности будем считать, что программы представлены в виде конечной последовательности задающих их текстов.
Начальные данные для программы Pбудем представлять натуральными числами. Тогда можно считать, что программа с текстом P вычисляет одноместную числовую функцию
f: N ® N, совпадающую с некоторой функцией fi(x) из последовательности (3), содержащей все одноместные вычислимые числовые функции.
Определим множество:
R1 = {(m, n) | значение fm(n) определено}.
Нетрудно видеть, что если существует алгоритм, который по произвольной программе P и некоторому начальному данному d для этой программы определяет, заканчивается ли вычисление программы P на d или нет, то множество R1 является разрешимым.
Покажем, что множество R1 не является разрешимым. Из этого будет следовать неразрешимость проблемы остановки.
