§ 3. Некоторые обобщения схем рекурсии и индукции

1. Рекурсии, допускающие сведение к простейшей схеме рекурсии (примитивная рекурсия); рекурсии пробега, одновременные рекурсии.

Отличительной чертой рекурсивной арифметики по сравнению с интуитивной теорией являются ограничения,

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

Правда, не меняя ничего, что было бы характерным для методов рекурсивной арифметики, мы можем произвести определенные обобщения схемы рекурсии, а также схемы индукции. Об этих обобщениях мы и хотели бы немного поговорить.

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

но все-таки могут быть сведены к рекурсиям, проводимым по этой схеме, — в дальнейшем эти последние мы будем кратко называть примитивными рекурсиями.

Пример такого рода рекурсии вообще, сводимой к примитивным рекурсиям, представляет собой схема

в которой вместо должен быть взят функциональный знак с одним аргументом, а

обозначают уже введенные термы, для которых выводимы формулы

Сведение этой схемы к примитивным рекурсиям производится таким образом, что сначала вместо в качестве рекурсивно определяемой функции берется функция

Эта функция определяется при помощи следующей примитивной рекурсии:

Затем получается из с помощью явного определения

Рассмотренная схема рекурсии представляет собой рекурсию типа «рекурсии пробега», т. е. такой рекурсии, при которой значение зависит не только от но и от всего пробега значений функции до аргумента Эту схему, не нарушая ее сводимости к примитивным рекурсиям, мы можем обобщить путем введения параметров, так что получится следующая схема:

где снова означают термы, для которых выводимы формулы

В эту схему могут быть, в частности, включены рекурсии следующего вида:

где Действительно, равенства этой схемы могут быть сведены в следующие два равенства:

а эти равенства уже укладываются в схему так как выводимы формулы

Пример рекурсивных равенств вида дает нам алгоритм Евклида для нахождения наибольшего общего делителя чисел Возникающая в процессе применения этого алгоритма последовательность равенств

представляет собой не что иное, как рекурсивное определение некоторой функции

которое производится с помощью функции

следующими равенствами:

К схеме может быть сведен другой тип обобщенной рекурсии — одновременная рекурсия для двух или большего числа функций. Схема одновременной рекурсии в простейшем случае, когда речь идет о двух одновременно определяемых функциях одного аргумента выглядит следующим образом:

В качестве примера такой одновременной рекурсии мы дадим второе определение для функций обращающих функцию а т. е. для тех двух функций, которые в определенной последовательности сопоставляют числам числовые пары. Это определение по сравнению с предыдущим будет иметь то преимущество, что оно получится непосредственно из процедуры нумерации без вспомогательных арифметических рассмотрений; оно выглядит следующим образом:

Сведение указанной схемы одновременной рекурсии для к схеме осуществляется путем написания рекурсивных равенств для функции значения которой определяются равенствами

Для этой цели мы используем функцию которая для четного аргумента принимает значение 0, а для нечетного — значение 1, и функцию которая для четного удовлетворяет равенству а для нечетного равенству Рекурсивные равенства для выглядят следующим образом:

После того как мы таким образом ввели функцию функции можно будет получить с помощью явных определений:

Совершенно аналогичным образом к обобщенной схеме рекурсии для одной функции сводится и одновременная рекурсия для нескольких функций; эта рекурсия может также содержать параметры:

Для этого сведения устраивается рекурсия для некоторой функции

значения которой связаны со значениями функций

равенствами

при этом нужно воспользоваться функциями и

Из сводимости одновременной рекурсии к рекурсии вида вытекает также сводимость ее к примитивным рекурсиям.