2. Перекрестные рекурсии; несводимость перекрестных рекурсий определенного типа к примитивным рекурсиям.

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

На этот вопрос следует дать отрицательный ответ: могут быть указаны рекурсии, обладающие указанными свойствами и такие, что они не могут быть сведены к примитивным.

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

но эта функция не может встречаться рассматриваемом нами перечислении, потому что если бы она имела в нем номер то должно было бы иметь место равенство

которое при подстановке вместо привело бы нас к противоречию.

Следовательно, если нам теперь удастся определить эту функцию с помощью какой-либо рекурсии, то тем самым мы получим пример рекурсии, несводимой к примитивным рекурсиям.

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

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

Функция, для которой Аккерман установил этот факт, получается следующим образом. Строится такая последовательность функций двух аргументов

что

а затем (для определяется с помощью рекурсией

Если рассматривать эту последовательность как функцию трех аргументов

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

Эти равенства имеют вид «перекрестной» рекурсии, т. е. такой рекурсии, которая производится по значениям двух переменных.

Если в этих равенствах вместо по очереди подставить цифры от 0 до 5, то получатся схемы рекурсии обычного типа для функций

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

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

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

И тем не менее эта рекурсия не может быть сведена к примитивным. Действительно, если бы это имело место, то функция

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

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

Рассмотрим перекрестную рекурсию

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

С этой целью мы извлечем из рекурсии для ряд полезных для дальнейшего оценок.

Во-первых, для каждой цифры оказывается выводимым неравенство

Действительно, неравенство

может быть получено непосредственно. Если уже выведено неравенство

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

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

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

Из неравенства

мы получаем

Во-вторых, для каждой цифры может быть выведена формула

Сначала для каждой цифры мы получим

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

заодно дает и формулу

Теперь из формулы

мы индукцией по к выведем формулу

а из нее с помощью формулы

искомую формулу

Из этой формулы получается также импликация

В-третьих, для каждой цифры индукцией по а может быть выведена формула

Действительно, неравенство

получается непосредственно, а с помощью формул

и

могут быть получены формулы

и

которые в сочетании с третьей рекурсивной формулой для дают нам формулу

так что при помощи схемы индукции мы получим формулу

Объединив эту формулу с неравенством

мы получим также неравенство

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

В дальнейшем будет целесообразно использовать как явное определение следующий способ записи:

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

а кроме того, для любой цифры большей выводима формула

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

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

или

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

При этом мы можем также освободиться от произвольности терма а, соответственно Если мы, например, рассматриваем рекурсию

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

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

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

В этой редукции используются функции

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

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

В соответствии с этим, из примитивных рекурсий без параметров мы можем рассматривать лишь такие, у которых первое равенство имеет вид

а среди рекурсий с одним параметром — лишь такие, у которых первое равенство имеет вид

или

так что в любом из этих случаев будет выводимо неравенство

Примитивную рекурсию с не более чем одним параметром, первое равенство которой имеет один из видов

мы для краткости будем называть нормированной рекурсией.

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

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

Теперь для того, чтобы с помощью имеющегося у нас определения функции получить требуемое неравенство

мы выведем друг за другом оценки одного и того же типа для всех входящих в определение термов. Эти оценки для термов с одной переменной будут иметь вид

а для термов с двумя и тремя переменными — вид

или

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

из которых можно вывести формулы

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

1. Для любой цифры выводимы формулы

2. Если I) (а) вводится рекурсией

и если для выведена оценка

то отсюда могут быть выведены формулы

а с помощью равенства

и формула

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

при помощи схемы индукции дает формулу

Заметим, что сделанные здесь предположения выполняются и тогда, когда в встречается только одна из переменных и когда для этой переменной оказывается выводимым неравенство

или

соответственно. Действительно, каждое из этих неравенств с помощью формулы

дает неравенство

3. Если введено рекурсией

и если для

выводимо ограничение

то отсюда мы получим ограничение

Действительно, индукцией по мы сначала следующим образом выведем неравенство

Прежде всего мы имеем

далее, мы получим

а затем отсюда получим

теперь с помощью схемы индукции можно будет получить

С другой стороны, используя формулы

мы получим неравенство

так что в целом можно будет получить

Случай, когда в

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

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

а для неравенство

где с — один из термов

Тогда будет выводимо также неравенство

Действительно, можно получить неравенства

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

где термы из списка

Тогда можно вывести неравенство

где с снова — один из термов

Действительно, сначала мы получим

а отсюда, аналогично тому, как это делалось в п. 4, получим

Кроме того, выводимо равенство

в котором с — один из термов, указанных в нашем утверждении. На основании установленных в пп. 1—5 утверждений о

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

которую можно также записать в виде

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

из которого подстановкой вместо а получилась бы формула

а из нее — противоречие. Однако это противоречие было бы противоречием внутри рекурсивной арифметики (понимаемой в нашем первоначальном смысле), в то время как мы показали, что возможность противоречия такого рода исключается.

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

Из этого результата мы можем следующим образом получить аналогичное утверждение и относительно аккермановской функции Рассмотрим функцию

Для этой функции мы получим сначала

затем

и наконец,

С помощью этих формул для каждой цифры может быть выведена формула

Для эта формула уже выведена. Таким образом, достаточно показать, что с помощью формулы

может быть выведена формула

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

получим формулу

Теперь все дело сводится к тому, чтобы получить формулу

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

может быть выведена формула

а тем самым и формула

Из этой формулы, используя формулу

и равенства

мы получим формулу

С другой стороны, из формулы

путем подстановки получим

а отсюда с помощью рекурсивного равенства

формулу

так что в итоге получится искомая формула

Тем самым, действительно, формула

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

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

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