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


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

70 ''" РЕКУРСИВНЫЕ 'ФУНКЦИЙ * "
Для введенной нами функции справедливы следующие равенства: М=«Р('0,*.(а), Х(а))=а(х(«),Х(а)), ;
Определение
) = а(х(0),
представляет собой примитивную рекурсию, в которой участвуют исключительно примитивно-рекурсивные функции. Из определенной таким образом двуместной примитивно-рекурсивной функции ф (n,a) первоначальная функция Произвольную примитивную рекурсию, определяющую многоместную функцию <р (п, аг ..... а,), можно тем же методом постепенно свести к примитивной рекурсии, определяющей функцию с од.-ним-единственным параметром, и додстановке. Для этого нужно сначала объединить два первых параметра в один, затем снова два и т. д. Употребляемые при этом функции i, х, X являются одно- и двуместными. Если выбрать их такими (а будет показано, что это можно сделать), чтобы их построение из 0 и п + 1 осуществлялось посредством рекурсий, определяющих не более чем двуместные функции, то отсюда будет следовать, что все примитивно-рекурсивные функции ^строятся из 0 и п + 1 с помощью конечного числа подстановок и примитивных рекурсий вида - •
(0,a) = a(a), cf>(/t+ 1,а) = р(я,а,«р(я,а)). •
Функции i, х, X остаются пока неопределенными. Выбрав их подходящим образом, можно добиться того, чтобы оставшиеся в новой схеме два аргумента были сведены к одному. "Это сделать не так просто, ибо один из этих аргументов является не параметром, а рекурсивным переменным.
4. Для начала заменим трехместную функцию р, встречающуюся в новой схеме, на двуместную. Тем самым мы покажем, что достаточно употреблять примитивные рекурсии вида
«Pi(0,a)=«! (a),

 

1 10 20 30 40 50 60 70 71 72 73 74 75 76 77 78 79 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260


Математика