Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Петер Р.N. Рекурсивные функции
 
djvu / html
 

\
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
тождественно нулю, несмотря на то, что из первого соотношения
получается
и т. Д. )•
Если сохранить только требование однозначности результата
/т. е- требование, чтобы разные пути вычисления m= *,«!, я,,..., я,),
из которой любая /--местная частично-рекурсивная (а следовательно, и любая обще-рекурсивная) функцит <р (я^ я2, ..., я,) получается при надлежащем tv в виде
21-
Ограничиваясь случаем г=1, заметим, что диагональная функция [определенная для тех t, для которых определено i|» (f , t) \
"'Но,'
доставляет пример частично-рекурсивной функции, которая не может быть «дополнена» до обще-рекурсивной функции*). Отсюда, полагая
_ /X (0» ^ли X (*) определено, если х (0 не определено,
получаем пример всюду определенной функции, которая не является обще-рекурсивной. Аналогичный пример в § 19 остается
г) Впрочем, невозможность получения из определяющей системы соотношений ошибочных равенств между числами можно ввести в определение без вреда для дела в виде дополнительного требования.
2) То есть не существует обще-рекурсивной функции Xi(0> совпадающей с i(t) всюду, где i(t) определена. В самом деле, для такой функции Xi(0 существовало бы число s, при котором
Ь Ю=<К», О
для всех t. Но тогда ^ (s, s) должно было бы быть определено, что дило бы к противоречию:

 

1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260


Математика