Доказательство. Предположим противное, т.е

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

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

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

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

di (x) =

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

 

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

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

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

di(x) = (fi(x)) + (fi (x)).

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

"i (p(i) = k di = fk),

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

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

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

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

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

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

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

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

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

y(x) = c(i0, p(x)).

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

y(x) = .

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

y(x) = .

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

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








Дата добавления: 2015-09-18; просмотров: 505;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.