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


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

НО РЕКУРСИВНЫЕ ФУНКЦИИ
циям 0 и я+1 нужно присоединить а-\-п (см. п. 16 § 7); кроме того, в этом случае схему <р(/г)=а (п) +Р(я) не следует причислять к определяющим схемам; зато следует принять схему подстановки двуместных функций
8. Диагональный метод можно применять и к ^-рекурсивным функциям (при произвольном К). На основании п. 6 предыдущего параграфа легко показать (так же, как это было сделано в начале настоящего параграфа для примитивно-рекурсивных функций), что множество ^-рекурсивных функций при произвольном k счетно. Расположив ^-местные fc-рекурсивные функции в последовательность
«Pi («!,...,№*), получим, что (&-|-1)-местная функция
<р (т, п„..., nk )= не является ^-рекурсивной. В противном случае была бы ^-рекурсивна и получаемая подстановкой функция <р(/гй, nv nz, ..., nk) от k переменных, а вместе с ней — функция, получаемая из нэе прибавлением 1; последняя функция, таким образом; должна была бы содержаться в нашей последовательности. Поэтому существовало бы число т, для которого при любых fiv..., nk выполнялось бы равенство
Но тогда при nL—nz=...—n.k — т мы имели бы равенство v(m, т,..., т)+1=Ф(т, т,..., т),
что невозможно.
Осуществление по вышеуказанному образцу эффективного пересчета fe-рекурсивных функций не вызывает никаких принципиальных затруднений1).
Определение функции, осуществляющей пересчет, является при этом (&+1)-кратной рекурсией. Следовательно, не только для Л=1, но для произвольного k справедлива теорема: (k-\-iy кратная рекурсия со вставками выводит за пределы класса k- рекурсивных функций (мы знаем, с другой стороны, что рекурсия без вставок не выводит даже за пределы класса 1 -рекурсивных функций).
§ 12. ТРАНСФИНИТНЫЕ РЕКУРСИИ
I. К понятию ^-рекурсивной функции мы пришли в связи с примером функции, не являющейся примитивно-рекурсивной. Однако следует признать, что исключение из рассмотрения многократ-
Ч Петер [5], §4.

 

1 10 20 30 40 50 60 70 80 90 100 110 111 112 113 114 115 116 117 118 119 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260


Математика