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

ТЕОРЕМА 8.4

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

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

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

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

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

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

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

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

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

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

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

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

g (x) = (x, x).

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

d (x) = .

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

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

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

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

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

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

Дата добавления: 2015-03-31