Но условия (12) совпадают со схемой рекурсии 2-й ступени, рассмотренной в предыдущем разделе. Из (И) видно, что функции /1 (а;), Д (х) удовлетворяют требованиям

h {х) < X, /2 (х) < X,

наложенным на эти функции в п. 5.1. Применяя теорему о рекурсии 2-й ступени из п. 5.1, приходим к заключению, что функция В (п, s), удовлетворяющая требованиям (8)-(10), не только существует, но и является рекурсивной функцией.

Теперь индукцией по параметру т докажем, что

В {т, х) = F {т, х) (х = О, 1, 2, . . .) (13)

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

В самом деле, для начальных значений /п = О, 1, 2, 3 из (8)-(10) получаем непосредственно

В (О, х)=В (2, х) = О, Z> (1, х) = S (х), В (3, х) = q (х).

Далее, пусть доказываемое утверждение справедливо для всех значений т, не превосходящих некоторого п. Рассмотрим выражение В [п -{- 1, х) как функцию от х. По условию выражения В (Д (п), х), В (Д {п), х) являются примитивно рекурсивными функциями от X. Первые два равенства из систелш (12) показывают, что функция В (п -\- 1, х) возникает из примитивно рекурсивных функций посредством обычной примитивной рекурсии и потому эта функция примитивно рекурсивна.

Наконец, пусть п 4- 1 есть номер некоторого терма. Тогда fx (п) и /2 [п] - также номера термов и, следовательно ,

В (/, [п), x) = F (/, (гг), х) (г = 1, 2; х = О, 1, . . .). (14)

Первые два равенства систелш (12) для рассматриваемого значения п -\- I справедливы для фзгнкции В {п -{- i, х), и для фз-нкции F {п + i, х). В силу (14) правые части указанных равенств одинаковы для функции -D (п 4- 1, х) и для функции F (п + i, х)." Поэтому В {П + 1, х) = F (п -{- 1, х), что и требовалось.

существует ли такая функция D и совпадают ли значения D {п, х) со значениями F {п, х) в области определения F, если функция D существует? Чтобы ответить на первый вопрос, перепишем условия (7) для функции D в более подробной форме:

D(fi{ii),x+l) + D{f2{n),x+l), если exo(n+l) = l,

D(fi(n),D(U{,i),x + l)), если exo(n + l) = 2,

D(fi(fi),D(n + l,x)), • если exo (/г-f-1) = 3,

Q (ji 4- 1, a; 4-1) для остальных n,

D{n+ 1,0)

D(h{n),0) + D{U{n),0), если exo(«+l) = l, .D{h{n),D{h{n),0)), если exo(«4-l) = 2,

для остальных n,

D (0, X) = 0, (10)

где положено

А (n) = exi {n + 1), /2 (д) = ex2 {n + 1). (11)

С помощью приема, рассмотренного в п. 3.1, мы можем переписать схемы (8), (9) в виде простых равенств и таким образом заменить условия (8)-(10) условиями

(п + 1, а; + 1) =

= G (п 4- 1, а;, Д (Д (д), D{n + i, х)), D (Д [п), D (/2 И, а; 4- 1)), D (/ (п), x + i),D {U («), ж 4- 1)), (12) Z) (п + 1, 0) = Я (« 4-1,1 (/i (п), £) (/2 (п), 0)),

В (Д (п), 0), В (/2 (п), 0)),

G (т, а;, i/, z, u, у) =

= (w 4- у) sg I ex(,m - 1 I 4- zsg I ехц/п - 2 4-+ ущ\exoJn - 3 4- <? (та, a;) sg ( exm - 11 exom-2 X

X I exom - 3 I ),

H {m, y, z, u) = {z + u) sg I exom - 1 4" г/sg ехт -

- 2 I 4- s" 1 m - 1 I .

Итак, мы построили общерекурсивную функцию D (м, х), обладающую следующими свойствами:

а) для каждого фиксированного ?г одноместная функ-j ция D {п, х) является примитивно рекурсивной; .]

б) для каждой одноместной примитивно рекурсивной! функции / (х) существует такое число п (равное номеру] терма, представляющего функцию /), что D (п, х) = = /()-

Это означает, что D (п, х) есть искомая общерекурсив- -ная универсальная функция для класса всех одноместных j примитивно рекурсивных функций.

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

В качестве примера можно взять двуместную функцию D {п, х). Она общерекурсивна и согласно теореме 1 примитивно рекурсивной быть не может. Из доказательства теоремы 1 видно, что общерекурсивная одноместная функция D [х, х) также не является примитивно рекурсивной.

Следствие 2. Для каждого л = 1, 2, . . . класс всех п-местных примитивно рекурсивных функций имеет общерекурсивную универсальную функцию.

Для п = 1 искомой универсальной функцией является D {п, х). Поэтому пусть и > 2. Рассмотрим функцию

D+i (жо, Хх, . . ., х„) = D {хо, с {Хх, . . ., Хп)),

где с (хх, . . ., Хп) - канторовский номер (п. 3.3) п-ки чисел {Хх, . . ., ХпУ. Для любого фиксированного Xq функция D" является примитивно рекурсивной функцией от Хх, . . ., Хп. С другой стороны, пусть g [Хх, . . ., Хп) - какая-нибудь ?г-местная при.митивно рекурсивная функция. Тогда примитивно рекурсивной будет и одноместная функция

f (Х) = g (Спх (Х), . ,Спп (Х)),

где Cnl [х) есть г-й член ге-кп, имеющей канторовскпй номер X (п. 3.3). Из универсальности функцпп D вытекает, что для подходящего Хд для всех х будем пметь

f (х) D (хо, х).

Подставляя сюда вместо х чпсло с (хх, . ., х„) л за.мечая, что

Cni [с (Хх, . . ., Хп)) = Xi,

получим

g {Хх, . . .,Хп) = D {Хо, с [Хх, . . ., Хп)).

Следовательно, D" (Жо, ж, . . ., а;„) - искомая общерекурсивная функция, универсальная для семейства всех примитивно рекурсивных м-местных функций.

Построив общерекурсивные функции, не являющиеся примитивно рекурсивными, естественно спросить себя, а существуют ли рекурсивные множества, не являющиеся примитивно рекурсивными (п. 4.1)? Ответ утвердителен. Чтобы найти такое множество, достаточно найти общерекурсивную функцию, принимающую лишь значения О II 1 и не совпадающую ни с одной примитивно рекурсивной функцией. Но такой функцией заведомо является функция

D {х)=щО {X, X).

В самом деле, функция!) [х) общерекурсивна и принимает лишь значения О и 1. Если бы D [х) была примитивно рекурсивной, то нашлось бы такое число п, что для всех х

sgD {х, х) = D {п, п),

откуда при X = п получили бы противоречие

sg D (п, п) = D {п, п).

Множество, характеристической функцией которого служит функция D (х), и есть искомое рекурсивное, но пе примитивно рекурсивное множество.

Аналогичный вопрос о существовании нерекурсивных рекурсивно перечислимых множеств будет решен в п. 6.3.

5.3. Быстрорастущие функции. Мы решили задачу построения "ицерекурсивной ф5нкцнп, не являющейся примитивно рекур-I йеной, методом универсальных функций. Другим методом для ре-шеипя той же задачи может служить метод построения функцпп, растущей быстрее любой функцпп заданного класса. Этот метод ичопь удобен при исследовании сравнительной силы различного рода рекурсий. Мы сейчас изложим его применительно к уже рассмотренному классу приьштпвно рекурсивных фпакций.

Итак, мы хотим найти по возможностп простые, по очень бы-строраст}тцие функции. Опыт показывает, что произведенле растет оыстрее суъпш, степень быстрее произведения. Называя сложение, умножение и возведение в степень действиями 0-п, 1-й и 2-п ступени и вводя для них в целях единообразия обозначения

Pq (а, х) = а -г X, Р, (а, х) = ах, Р (а, х) = а,

приходим к знакомой всем идее о продолжении этой иоследователь-постп п>тем введения действий высших ступеней. При этом действие

Р, {а, x+i)= Р, [а, Ру (а, х)), Р, (а, 1) = а, Р (а, х+ i)= Ру {а, Р,, {а, х)), Р (а, 1) = а.

Продолжим эту цепочку, полагая по определению для п = 2, 3, . . .

Рпг 1) = (2)

Рп+1 (а, х+ 1) = Рп {а, Рп,у {а, X)). Чтобы функции Рп (а, х) были определены всюду, положим

(а, 0) = 1 {n=i, 2,. . .)

и соотношения (2), (3) будем считать определениями функций Рп (а, х) для = 2, 3,. . . Ясно, что равенства (1) вытекают из соотношений (2), (3) и соотношения Ру (а, 0) = 0. В силу (2), (3), например, имеем

Рз(а, 0) = 1, Рз(а, 1) = а, (а, 2) = а«, Р {а, 3) = а"" Вводим новые функции

Б (п, х) = Рп (2, х), А (х) = В (х, х).

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

Для функции В («, х) из соотношений (2), (3) вытекают следующие тождества:

В (п -Ь 1, x+i) = В{п, В {п + 1, х)), (4)

В (ге -Ь 1, 0) = sg re, (5)

S (О, х) = 2+ X. (6)

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

Наша цель теперь состоит в доказательстве след>тощего пред-ложенпя:

Теорема 1(Аккерман [1]). Д.гя каждой одноместной примитивно рекурсивной функции f (х) существует такое число а, что

f(x)<A (х)

{х= а, a-fl, . . .),

и, с.гедовате.гъно, функция А {х) не при.митивно рекурсивна.

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

В {п, х) > 2- (ге > 2; ж = 1, 2,

Так как В (2, г) = 2, то для ге. = 2 это соотношеппе верно. Далее применяем индукцию по п. Пусть для некоторого ге 2

/ (а:)< В (ге, х)

(а;= 2, 3,. . .).

Лемма. Все одноместные примитивно рекурсивные функции В-мажорируемы.

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

1) Функции S (х) = X -i- I ж q {х) = X - lxf В-мажорируе-м,-, так как для а; > 2

QixXs (х) < 2« = В (2, а:).

2) Сумма В-мажорируемых функций В-мажорируема. Пусть произвольные функции / {х), g (х) для а; > 2 удовлетворяют соотношениям

f{x)<B{ny, X), g{xXB{n,,, х). Тогда, полагая п = пу -- п, имеем

/(а:)<В(«, х), g{x)<Bin, X). (7)

Отсюда согласно а), б), в) полчае.м

/ {х) + (х)< 2В («, х) < 2«("+1- < В (ге, В (ге + 1, х)) =

= В (ге-Ы, а; 1)< В (ге-f 2, а:),

что п требовалось.

3) Суперпозиция В-мажорируе.чых функций В-.чажорируема. Действительно, пз (7) последовательно получаем

/ {g (х)) <В(п, g {х)) <:В (п, В{п+ 1, .г)) =

= В (ге -Ь 1, а; -Ь 1)< В (ге -t- 2, а:).

высшей ступени должно возникать из действия предыдущей ступени так же, как умножение возникает из сложения, возведение в степень из умножения. Функции ?„, Pj, связаны следующими соотношениями:

соотношение а) истинно при всех значениях а; > 1. Согласно (2) В(;г + 1, 1) = Р„+1 (2, 1)=2>21.

Пусть теперь для какого-то а; > 1 имеем В (ге -)- 1, а:) > 2*. Тогда 5 (ге + 1, х+ \) = В (ге, В (ге -Ы, а;))-> 2В(»+1. > 2 > 2+.1

и, следовательно, соотношение а) доказано.

б) В (ге, а; -Ь 1) > В (ге, х) (ге, а; = 1, 2, . . .).

Так как В.(1, х) = 2х, то для ге = 1 это неравенство истинно. Пусть б) истинно для некоторого ге > 1. В силу (4) и а)

5 (ге -f 1, а; -Ь 1) = В (ге, В (ге -Ь 1, аг)) > 2(+1 > > В (ге -Ь 1, а:),

что и требовалось.

в) В(ге-Ь1, аг)>В(ге, x+i) (ге > 1, а: > 2). Действ:ительно, в силу (4), а), б)

В (ге + 1, а: -Ы) = В (ге, В (ге -Ь 1, а;)) > В (ге, 2«) > В (ге, а: -Ь 2).

Произвольную одноместную функцию / {х) условимся называть В-мажорируемой, если существует такое ге, что