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

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

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

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

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

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

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

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

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

ПРОБЛЕМА ВСЮДУ ОПРЕДЕЛЕННОСТИ

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

Содержательно такие функции вычисляются программами, которые всегда останавливаются.

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

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

R₂ = {n | f_n - всюду определенная функция}.

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

ТЕОРЕМА 8.5

Множество R₂ является неразрешимым.

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

Предположим противное. Пусть характеристическая функция множества R₂:

(x) = является вычислимой.

Рассмотрим вспомогательную функцию g(x), задаваемую соотношениями:

g(0) = mt( (t) = 0);

g(k+1) = mt( (t) = 0 & t > g(k)).

Так как вычислимая функция, то функция g также вычислимая.

Последовательность функций f_g(0), . . . , f_g(i), . . . содержит все всюду определенные функции последовательности (3) в порядке возрастания номеров этих функций в нумерации p, множества F¹.

Пусть h(x, y) - определенная ранее универсальная функция.

Тогда функция q(x, y) = h(g(x), y) является вычислимой, и для каждого фиксированного значения x справедливо следующее равенство: q(x, y) = f_g(x)(y).

Поэтому функция d, определяемая соотношением: d(x) = q(x, x)+1 также является вычислимой всюду определенной частично-рекурсивной функцией. Поскольку последовательность f_g(0), . . . , f_g(i), . . . содержит все всюду определенные частично-рекурсивные функции, то $ i Î N(d(x) = f_g(i)(x)).

Рассмотрим значение d(i).

1.По определению функции d справедливы равенства:

d(i)= q(i, i)+1 = f_g(i)(i)+1.

2.С другой стороны значение i выбрано так, что

d (i) = f_g(i)(i).

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