8.5.3. Проблема всюду определенности

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

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

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

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

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

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

ТЕОРЕМА 8.5

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

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

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

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

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

g(0) = t( (t) = 0);

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

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

Последовательность функций f_g(0), . . . , f_g(i), . . . содержит все всюду определенные функции последовательности (3) в порядке возрастания номеров этих функций в нумерации , множества 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₂ не является разрешимым множеством.

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

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

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

Определим множество R₃ = {(m, n) | f_m  f_n}.

То есть это множество пар номеров равных функций в нумерации всех одноместных частично-рекурсивных функций.

Если множество R₃ является разрешимым, то существует разрешающий алгоритм для проблемы эквивалентности программ.

ТЕОРЕМА 8.6

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

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

Предположим противное, т.е. множество R₃ является разрешимым, а его характеристическая функция

( n, m) =  вычислимая.

Р ассмотрим преобразование функций последовательности (3), которое всякой функции f_i ставит в соответствие частичную функцию:

1, значение f_i(x) определено

d_i (x) =

, значение f_i(x) не определено.

Справедливо следующее свойство: функция d_i совпадает с функцией, тождественно равной единице тогда и только тогда, когда функция f_i является всюду определенной.

По определению последовательности (3) и нумерации  существует метод, который по  номеру i произвольной функции f_i позволяет построить схему определения этой функции.

Достроим полученную схему до определения функции d_i, например, с помощью соотношения:

d_i(x) = (f_i(x)) + (f_i (x)).

Тогда функция p(x), определяемая соотношением:

i (p(i) = k d_i = f_k),

является вычислимой.

Содержательно отображение p преобразует  номер произвольной функции f_i и F¹ в некоторый конкретный  номер, равный p(i), такой функции в той же последовательности (3), которая совпадает с d_i. Для вычисления значений функции p можно воспользоваться следующей схемой:

1. Построим дерево Df_i определения функции f_i (x).

2. Достроим Df_i в дерево D, представляющее определение функции f_i(x)) + (f_i (x).

3. По дереву D построим его код .

4. Найдем код в последовательности (1) кодов деревьев определений частично-рекурсивных функций.

5. Если k  номер найденного слова в последовательности (1), то положим p(i) = k.

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

Рассмотрим функцию:

(x) = (i₀, p(x)).

Очевидно, что она является вычислимой. Кроме того:

(x) = .

Из этого следует, что  (x) = 1 тогда и только тогда, когда f_i  всюду определенная функция, т.е.

(x) = .

Значит  это вычислимая характеристическая функция множества R₂. Это противоречит доказанной ранее теореме о неразрешимости данного множества.

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

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

Замечание. В доказательстве последней теоремы использован прием, который состоит в сведении одной задачи разрешимости к другой, более общей, задаче разрешимости.

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

В таком случае будем говорить, что первая задача сводится ко второй задаче, поскольку из существования алгоритма решения второй задачи следует существование алгоритма решения первой задачи.

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

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

Говорят также о том, что множество R₂ сводится к множеству R₃.

Упражнение.

1. Обозначим как R  множество {(n,m,k)| f_n(m) = k}.

Доказать, что R  неразрешимое множество, сведением его к неразрешимому множеству R₁;

2. Доказать неразрешимость множества частично-рекурсивных функций одной переменной, которые определены для почти всех значений начальных данных;

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

236