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

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

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

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

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

d_i (x) =

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

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

По определению последовательности (3) и нумерации n существует метод, который по n номеру 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 преобразует n номер произвольной функции f_i и F¹ в некоторый конкретный n номер, равный 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.

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

y(x) = c(i₀, p(x)).

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

y(x) = .

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

y(x) = .

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

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