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


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

120 РЕКУРСИВНЫЕ ФУНКЦИИ
с помощью которой разрозненное определение функции ty(m, n), данное в предыдущем пункте, можно переписать в виде
, я)=о1(я)|
, /г)).
Это определение, очевидно, является двукратной рекурсией, построенной с использованием лишь примитивно-рекурсивных функций. Совершенно аналогично любую другую трансфинитную рекурсию типа ш3 можно свести к обычной двукратной рекурсии.
9. Можно провести и обратное рассуждение — сведение двукратной рекурсии к однократной трансфинитной рекурсии типа ш2.
Покажем это на примере двукратной рекурсии со вставками
ty(m, n)=l, если т-п—0,
(/»+!, я+1)=р(да, п, ф(да, ф(/» + 1, /г))). Пусть
г=о(да, /г), тогда
w=Po(r) и я=Рх(г), поэтому функцию ф(г), обладающую свойством
можно определить следующим образом:
1, если р0(/')-р1(г)=0, и в противном случае
Из этого определения вытекает, что
«Р(0)=1-Действительно,
Pe(0).Pl(0)=0.0=0. Положим для сокращения записи
(1, если Po(r+l)-Pl(r+l)=0,
1р(р„(г+1)— 1, рг(г+1)— 1, а) в противном случае

 

1 10 20 30 40 50 60 70 80 90 100 110 120 121 122 123 124 125 126 127 128 129 130 140 150 160 170 180 190 200 210 220 230 240 250 260


Математика