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


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

60 РЕКУРСИВНЫЕ ФУНКЦИИ
Покажем, как для л + 1 построить число х(я+1), удовлетворяющее тому же условию. В силу определения (D) и сделанного п редположения,
("t1) =Р (я, «' (a), G 5))Н(Я, «, Ф (* (Я), «)> Ф (* (Я), Y («)))• Из определения (D) вытекают, далее, тождества
в-ф(0,а), т (а)=Т (Ф (0, а)); кроме того,
Поэтому
(я, Ф (0, а), Ф (*(«), а), ф (* («), Ф (2, а))). В силу предыдущего пункта,
и, следовательно,
("?') = ? (я, ф (0, а), ф (х («), а), ф (v (х («), 2), а)). Наконец, определение (D) дает
Р (п, ф (0, а),ф (х (п), а), ф (v = Ф (2а - 3я • 5° • 7» <*> . 1 1» (» W. 2), а); окончательно
Итак, для п+1 удается построить нужное число. Функция х (п) определяется, таким образом, с помощью примитивной рекурсии
х(0)=1,
х(п4-1)=2!!.Зя.7*<я>-П1'0'<я>'2>) причем
Функция (ц) получается подстановкой из примитивно-рекурсивной функции и, следовательно, сама является примитивно-рекурсивной.
5. Аналогично можно показать, что рекурсия вида
«(О, а)=а(а),

 

1 10 20 30 40 50 60 61 62 63 64 65 66 67 68 69 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260


Математика