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


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

130 РЕКУРСИВНЫЕ ФУНКЦИИ
Bx(m,n,f(x)), для которой при п = 0,1,2,... справедливы равенства
ЯЛ«, 1, f (*))= Р(«, 0, f(Y(«, 0, <>)),<)),
Вх (т, 2, f (*)) = р (да, 1 , f (Y (и, 1 , Р (да, 0, f (у (т, 0, 0)), 0))),
,p(w,0,f(Y(«,0,0)),0)),
Таким образом, для Вх(т, п, f(x)) можно дать следующее определение:
В,(да,0, /(*)) = 0,
В,(да,л+1, /(дс)) = р(да, п, f(Y(m, л, В, (те, n,f (*)))), В, (да, /г, f (дс))).
Так как, далее, при /(дс) = <р(/п, дс) и /г = О, 1, 2,... выражение Bx(m,n,f(x)) принимает значения (р(/п+1,л), то функцию <р(/п, /г) можно задать равенствами
<р(0,л) = 0, «р(да + 1, л) = ^(те, /г, <р(т, дс)).
Это определение, так же как и определение Вх(т, п, f(x)), является однократной рекурсией второй ступени.
5. Рассуждения предыдущего пункта можно облечь в форму строгого доказательства.
Пусть (т, п) определяется двукратной рекурсией
<р(0,д.) = 0, «р(да+1,0) = 0, if (т + 1, п + 1) = р(/п, п, ч(т, Y(m, п, w(m + 1, л))), tp(m + 1, л)).
Определим «функцию от функции» Bx(m,n,f(x)) и функцию <|> (т, п) посредством однократных рекурсий второй ступени
Я, (да, 0, /(*)) = О, В, (да, л+1, / (дс))=Р(да, «, f (Y(w, л, Вл (т, /г, f (дс)))), В, (да, /г, /(дс))),
и
t (да + 1, л) = В, (т, /г, ф (т, дс)).
Мы утверждаем, что для всех т и п справедливо равенство
ф(да, л)=Ф(да, л).
Для доказательства воспользуемся методом трансфинитной индукции. Прежде всего, равенство справедливо для точки (0,0), так как
ф (0,0) -0 = ?(0,0).

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 131 132 133 134 135 136 137 138 139 140 150 160 170 180 190 200 210 220 230 240 250 260


Математика