11.4. Другие виды рекурсии

Слова «рекурсивное определение функции» можно по­нимать и в более широком смысле, нежели мы это делали (см. выше определение рекурсии, или примитивной ре­курсии) — как любой способ задания функции, который связывает значение функции в данной точке с другими сё значениями. Как мы увидим ниже при обсуждении функ­ции Акксрмана, есть такие схемы рекурсивных опреде­лений, которые выводят из класса примитивно рекурсив­ных функций. Но есть и такие, которые можно свести к рассмотренной нами схеме.

Мы приведём два примера последнего типа: совмест­ное определение нескольких функций и использование произвольных меньших значений аргумента.

Совместная рекурсия. Пусть две одноместные функ­ции f ш д заданы соотношениями:

/(0) = а,

9(0) = Ь, f(n + ї) = F(n.J(n).,g(n)) д(п+Г) = С(пЛп),д(п))

где а и Ь — некоторые числа, а функции Р и С — прими­тивно рекурсивные функции трёх аргументов. Покажем, что тогда функции f ш д примитивно рекурсивны.

Чтобы доказать это, нам потребуется примитивно ре­курсивная нумерация пар — такая функция (х, у) —5- [х, у] (номер пары мы обозначаем квадратными скобками), ко­торая была бы примитивно рекурсивна вместе с двумя обратными функциями (дающими по номеру пары сё пер­вый и второй члены). Тогда мы сможем написать рскур-

Другие виды рекурсии

сивноо определение для функции Ь,(п) = [/(п), д(п)\.

где функции рі и р2 дают по номеру пары первый и вто­рой сё члены. Если функция К примитивно рекурсивна, то и функции f ш д (композиции К с функциями р\ и ро) также примитивно рекурсивны.

Осталось объяснить, как найти примитивно рекур­сивную нумерацию пар. Можно заметить, что есть мно­гочлен второго порядка с двумя переменными, задающий взаимно однозначное соответствие N х N —5- N. Это соот­ветствие видно из таблицы:

Примитивную рскурсивность обратных отображений р\ и р2 можно установить, воспользовавшись ограниченной минимизацией, так как р\(п) есть минимальное х <С п, для которого найдётся у <С п, при котором [х, у] = п.

Менее симметричная нумерация пар может быть за­дана формулой [а, Ь] = (2а + 1)26. Можно также заметить, что нам не нужно, чтобы вес числа были номерами ка­ких-то пар, и воспользоваться нумерацией [а, Ь] = 2°36.

Заметим в заключение, что аналогичная конструкция применима для большего числа одновременно определя­емых функций и для функций от большего числа аргу­ментов.

Возвратная рекурсия. Следующее утверждение пока­зывает, что при рекурсивном определении можно исполь­зовать не только значение в предыдущей точке, но и лю­бое предшествующее значение.

Теорема 74. Пусть функция д одного аргумента при­митивно рекурсивна, причём д(х) < х при х > 0; пусть

МО)

[а, Ь],

[Р(п,Рі(Іі(п)),р2(Щп))), С(п;р1(Цп));Р2(Цп)))]

6

3 7 1 4 0 2 8

5 9

F — примитивно рекурсивная функция двух аргументов; пусть с — произвольная константа. Тогда функция h, определённая соотношениями

ЦО) = с,

h(x) = F(x, h(g(x))) при х > О

примитивно рекурсивна.

<] Чтобы доказать эту теорему, используем следу­ющую нумерацию конечных последовательностей нату­ральных чисел: номером пустой последовательности счи­таем число 1, номером одноэлементной последователь­ности (а) считаем число 2а+1, последовательность (а, Ь) имеет номер 2а+136+1, последовательность (а, Ь, с) имеет номер 2а+136+15с+1 и так далее (основания степеней — простые числа). Будем обозначать номер последователь­ности (а, Ь,..., z) через [а, Ь,..., г]. Эта нумерация в не­котором смысле примитивно рекурсивна. Конечно, бу­квально это понимать нельзя, так как нумерация пред­ставляет собой «функцию с переменным числом аргумен­тов». Но разные связанные с ней функции примитивно рекурсивны. В частности, таковы функции

• Length(ai) = длина последовательности с номером х;

• Select (г, х) = г-ый член последовательности с номе­ром X]

• Append{х, у) = номер последовательности, которая получается приписыванием числа у к последова­тельности с номером х.

Все эти функции (и другие аналогичные) сводятся к раз­личным операциям с простыми числами и множителями, которые мы в сущности уже разбирали. Теперь мы докажем, что функция

х ^ Н(х) = [h(0), h(l),h(x)]

примитивно рекурсивна. В самом деле, Н(0) = [с], а

ff(fc+1) = Append(H(k);F(k+l;Select(g(k+l);H(k)))). >

Машины Тьюринга и рекурсивные функции