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


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

140 РЕКУРСИВНЫЕ ФУНКЦИИ
Мы видим, что при каждом п значение (р(т+1, п+1, а) вычисляется без использования выражения <р(т+1, п, хг), которое встречается в первоначальном определении. Зато в этом вычислении участвуют теперь выражения ^(т, t, yv..., yr) при t^n.
Введем вспомогательную функцию ф(/га, п, а), которая будет обладать следующими свойствами. Прежде всего
ф(от, п, а)=0, если т-п=0.
Далее, мы предположим, что к множеству значений этой функции принадлежит а, вместе со всякими числами у1}..., уг — числа РД/ге, t, ylt ..., уг) (при любэм t) и вместе со всякими х^, xz — числа w (т, xt, хг). Очевидно, что среди значений функции t]> встречаются все значения функции <е. Точнее, для всех т и п и для соответствующим образом выбранного х справедливо равенство
1, х, а).
При исследовании однократно-рекурсивного определения функции ( д J не требовалось, чтобы . вспомогательная функция прини-
мала и значения определяемой функции <р= ( па ) . Поэтому теперь
определение вспомогательной функции будет несколько сложнее, чем раньше: в этом определении тепэрь будут встречаться вставки. Однако вставка будет одинарной и определение вспомогательной функции t]) будет, вообще говоря, проще, нежели определение первоначальной функции. Функция х попрежнему примитивно-рекурсивна, однако теперь ее построение тесно связано с построением ф.
3. Так как ф(/ге, п, а)=0 при т-п=0, то
<1»(/га+1-, 0, а) = 0=<р(/га+1, 0, а).
Следовательно, в качестве первого определяющего равенства для х(«) можно принять
х(0)=0.
Итак, для т-п=0 заведомо выполняется равенство (р(т, п, а)=(])(да, х(л), а).
В качестве точек, предшествующих п, будем, как это неоднократно делалось раньше, использовать показатели разложения ii на простые множители. Отдельные случаи мы будем различать по величине показателя двойки, равного ехр0 (п). Заменяя <р (т, xv X2) выражением ф(от, *(*i),. *2) с подходящим ,х(«), получцм,

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 141 142 143 144 145 146 147 148 149 150 160 170 180 190 200 210 220 230 240 250 260


Математика