Покажем теперь, что каковы бы ни были функции G, H,h ш функции/j, gi, удовлетворяющие условиям (5), существует функция F (х, у) и только одна, удовлетворяющая схеме (6).

Построение функции F (х, у) выполняется очевидным путем. По определению для всех х полагаем F {О, х) =-= h {х). Далее, если для всех пар <ц, у), меньших нары/ <ге -- 1, 0>, значения F (и, v) определены и для них условия (6) соблюдены, то значение (?г -f 1, 0) определяем второй формулой из (6). Наконец, если значения F определены для всех пар, меньших нары <ге -- 1, ж -- 1>, то значение F (п -j- i, ж -f 1) определяем первой формулой из (6). Ясно, что полученная таким образом функция удовлетворяет условияхм (6). Поскольку выбиравшиеся значения для F (п, ж) однозначно вытекали из формулы (6), то формулы (6) определяют F однозначно.

Для дальнейшего принципиальное значение имеет;

Теоред1а 1(о рекурсии 2-й ступени). Если указанные в определении рекурсии 2-й ступени функции G, Н, h, fi: gj примитивно рекурснвны, то возникающая из них посредством рекурсии (6) функция F является общерекурсивной.

Чтобы сократить запись формул, докажем эту теорему для m = 4, /с = 3. В общем случае рассуждения остаются теми же.

Обозначим через М график функции F, т. е. совокупность троекчисел вида <ж, у, F (ж, г/)>. Согласно п. 4.4 теорема 1 будет доказана, если мы обнаружим, что совокупность М рекурсивно перечислима. Посмотрим, что означают равенства (6) для М,

Первое из равенств (6), очевидно, можно пересказать так: если тройки

<7Z -Ь 1, ж, м>, </i (?г), и, vy, </з (/г), ж -Ь 1, рУ, <f2{n),p,qy,<fAn),x + l,wy (7)

принадлежат М, то

<7z + 1, ж + 1, G (7z -t- 1, ж, V, q, w)y G 31. (8)

Второе из равенств (6) равносильно утверждению: если тройки

<go [п), О, «>, <gi (71), ц, иУ, <7Z, О, ш>, (п), О, рУ (9) принадлежат 31, то

<п -f 1, О, Я (?г -f 1, V, W, р)У G ЛГ. (10)

Наконец, последнее из равенств (6) утверждает, что Ж содержит все тройки вида <0, ж, h (ж)>.

Обозначим через № совокупность всех тр-оек чисел. Д1ы хотим определить на такие операции .А [ui, щ, и, щ, Us), S (щ, щ, из, и), которые д.ля наборов троек (7), (9) имели бы своими значениями соответственно тройки (8) и (10). С этой целью полагаем по определению для произвольных Xi, yt, Zi

Л {{xi, уг, Zi>- • • <5, Уь, Z5» =

= <1, Уз, G (Ж1, Ух, Z2, Z4, Zs)), (И)

если выполнены условия Ж2 = fl [xi 1), У2 = Zi, Xs = /з (Хх 1), Уз = У1 + 1.

Xi = /2 {Xl 1), г/4 = 2з, Х; = /4 {Хх 1), 1/5 = 1/1 + 1,

(12)

II полагаем

Л {<Хх, Ух, Zl>, . . ., <Ж5, 1/5, 25» = <0, О, h (0)>, (13)

если условия (12) не выполнены.

Аналогично полагаем по определению

S «Ж1, Ух, Zi>, . . ., <Ж4, г/4, Z4» =

= <Жз -f 1, О, Я (жз + 1, z„ zs, z,)y, (14) если выполнены условия

Xl = g2 {Xs), Х = gx {Хз), у2 = Zi, Ж4 = 3 (Жз), (15)

и полагаем

Ш «Хх, Ух, zi>, . . ., <Ж4, 1/4, Z4» = <0, о, h (0)>, (16)

если условия (15) для Хх, Ух, , z не удовлетворяются.

Так как функции G, Н, h, fi, gi примитивно рекурсивны, то согласно и. 4.4 операции J, ш 3S также придштивно рекурсивны.

Обозначим через 3£„ совокупность троек вида ф, ж, h (ж)>. Из примитивной рекурсивности функции h (ж) следует, что совокупность ж о рекурсивно неречпслид1а.

Согласно теореме о порождаемых совокупностях (п. 4.4) совокупность Л/* всех троек, которые дюжно ползчить пз троек множества Mq с помощью операций Jt, 33, является рекурсивно перечислимой и над1 остается доказать лишь совпадение совокупности Ж* с графикод! 31.

Прежде всего замечаед!, что 3f содержит порождающее множество JIq. Кродш того, условия (И), (13) и (14) , (16)

показывают, что совокупность М замкнута относительно операций Л, So. Совокупность М* по определению есть наименьшая совокупность, замкнутая относительно Л, и содерлчащая Ж,,. Таким образом, М* Q М.

Обратное вк.лючение М Q Ж* проще всего доказать индукцией по параметрам п, х троек <7г, ж, F {п, ж)), составляющих график Ж. Для п = 0 график Ж содержит лишь тройки <0, X, h (х)у. Все они входятв Ж*. Пусть для некоторого п все тройки (г, х, F (г, ж)), удовлетворяющие; условию г < п, входят в Ж *. Покажем, что тогда и тройка <?г + 1, О,(?г + 1, 0)> ВХОДИТЕ Ж*. Полагая и = = F [gi in), 0), vF {gx in), и), w = F [n, 0), p = = F {gz [n), 0), имеем в силу (6)

F{n + l,0)=H{n + l,v,w,p).

Так как gi {п) п, то все тройки (9) по предположению входят в Ж*. Применяя к тройкам (9) операцию 33, получим тройку <w + 1, О, F {п + I, 0)>. Совокупность Ж* замкнута относительно операции 33. Следовательно, тройка </г -f 1, О, F (ге -Ь 1, 0)> принадлежит Ж*.

Аналогично доказывается и утверждение, что если для данных 71, X все тройки (г, s, F (г, s)> с условием (г, s> < <. in i, X + iy содержатся в Ж*, то и тройка <ге -f -f 1, а;-f 1, f (re +1, а:-f 1)> содержится в Ж*. Тем самым включение Ж Q Ж*, а вместе с ним и равенство 31 = 31* доказаны.

5.2. Универсальная общерекурсивная функция. Рассмотрим произвольную систему © частичных ге-местных функций. Частичная функция F {х, х, . . ., х„) от п -\- i переменных называется универсальной для семейства ©, если выполнены следующие два условия:

а) для каждого фиксированного числа i п-местная функция F [i, Xi, . . ., х„) принадлежит ©;

б) для каждой функции / {х, . . ., а:„) мз © существует такое число i, что для всех х, . . ., х

F {i, Хх, . . ., X,,)- = f [хх, . . ., Хп).

Иначе говоря, функция F {х„, Хх, . . .", х) универсаль- на для семейства ©, если все функции пз © можно расположить в последовательность

F{0, Хх, . . ., Xn),F {1,хх, . . ., Хп), ...,F{i,Xx,..., an). •• •

Число i называется номером функции F {i, Хх, Хп), а полученная таким образом нумерация функций семейства © называется нумерацией, отвечающей универсальной функции F. Обратно, если задана какая-либо нумерация системы ©, т. е. если задано какое-нибудь отображение i ft натурального ряда на ©, то функция

F (хо, X,

., а:„), определенная формулой F [х, Хх, . . ., Хп) = fx [хх, , Хп),

яиляется уггг1верса.льной для ©.

Заметим, что рассматриваемые здесь нумерации в от-лпчне от нумераций пар, троек и т. д. из п. 3.3 не одно-однозначны: различные натуральные числа i могут быть номерами одной и той же функции из ©.

Существование достаточно «хорошэй» универсальной функции является важной характеристикой системы ©. ]-1апример, если система © состоит только из всюду оцределенных функций, то существует очень простой метод (диагональный метод Кантора) построения всюду определенной функции, не входящей в ©.

В самом деле, пусть F {х, Хх, . . ., а:„) - универсальная функция для семейства © некоторых всюду определенных функций от ге переменных. Из определения следует, что эта универсальная функция будет также всюду определенной. Вводим новую функцию g, полагая

g {хх, . . .,Хп) = F {хх, Хх, х, . . ., х„) -f 1. (2)

Функция g {хх, . . ., Хп) не входит в ©.

Действительно, если бы g принадлежала семейству ©, то при подходящем натуральном i для всех Хх, . . Хп было бы истинно равенство

F (i, Хх, . . ., Хп) = F {хх, Хх, Xi, . . ., Хп) + 1-

Однако при Хх = i оно обращается в противоречивое соотношение

F (г, i, . . ., Хп) = F . . ., х„) + 1,

что и доказывает наше утверждение.

От.метнм два важных следствия этого утверждения. Пусть © - система всех тг-местных рекурсивных или cooTBeTCTBeHrfo при.лштивно рекурсивных функций. Равенство (2) показывает, что если функция F {хд, Хх, . . ., х,) рекурсивна или прплштивно рекурсивна, то таковой является и функция g (хх, . . ., Хп). Но эта функция не

MovKHO считать, следовательно, что мы опрсде.лили для каждого терма й его номер. Ясно, что далеко не каждое натуральное число является номером некоторого терма, но если число а есть номер терма, то только одного, и этот терм легко восстанавливается путем разложения а на простые множители.

Определяем теперь новую функцию F [п, х) формулой

F [п, X) = /„ (х), (5)

рде терм с номером п. Так как не все натуральные числа являются номерами термов, то функция F [п, х) также определена не для всех значений ге и потому является частичной. Однако для тех значений ге, для которых F определена, из способа нумерации тердюв (3) и (4) вытекают следующие соотношения:

(faix) + hix), если re = 2.3"•5

UiUix)), если re = 4.3»•5

faifnix-i)), если ге = 8.3",а:>0,

О, если /г = 8 3", х = 0,

q (х), если ге = 3,

.8{х), если /1 = 1.

во внимание равенство (5), мы можем соотношения (6) переписать в виде

F (ге, х) =

F (exi ге, х) + F (ехг п, х), F (exi п, F (ех2 п, х)),

F (ге, х) =

Принимая

F{exin,F{n,x-l)), О,

Q [п, х)

если ехоге = 1,

если ехо п = 2,

если ехо = 3, а: > О,

если ехо?г = 3, а: = 0,

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

где для краткости положено

(? (ге, ж) = S (ж) sg I ге - 1 I + g (ж) ig" I ге - 3 .

Подчеркнел! еще раз, что соотношения (7) установлены лишь для тех значений ге, которые являются номерами термов. Мы хотим теперь найти всюду определенную функцию D (ге, х), удовлетворяющую тем же соотношениям (7) для всех значений ге, х. Возникают вопросы:

ВХОДИТ в © и, значит, она не рекурсивна или соответственно не примитивно рекурсивна. Тем самым пришли к следующей простой, но существенной теореме.

Теорема 1. Система всех п-местных общерекурсивных функций не имеет общерекурсивной универсальной функции. Система всех п-местных примитивно рекурсивных функций не имеет примитивно рекурсивной универсальной функции (?г = 1, 2, . . .).

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

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

Чтобы построить искомую универсальную функцию, нужно все одноместные примитивно рекурсивные функции расположить в последовательность вида (1). Для этой цели мы воспользуемся теоремой Р. Робинсона из и. 3.5, согласно которой все одноместные примитивно рекурсивные функции моншо получить из функций S [х) = X i и q [х) = X - [Ух] операциями сложения, суиерпози-ции и итерирования функций. Эти операции были обозначены в п. 3.5 символами --, *, J. Упомянутая теорема Р. Робинсона утвернедает, что каждая одноместная примитивно рекурсивная функция является значением подходящего терма, составленного из индивидуальных символов S, q ж функциональных символов. Обратное также верно: значение каждого терма упомянутого вида есть примитивно рекурсивная одноместная функция. Поэтому, нумеруя термы, мы одновременно занумеруем и все примитивно рекурсивные одноместные функции. Номер терма й условимся обозначать через N (а).

Для самых коротких термов s к q полагаем но определению

N{s) = 1, N{q) = 3. (3)

Далее определяем номера термов индуктивно, восходя от коротких термов к более длинным. А именно, если для каких-нибудь термов й, Ь мы уже знаем пх номера N (й) = а, N (Ь) = Ъ, то но определению полагаем

Л(й + Ь) = 2.3"-5\ N{a*b) = A-T -5,

N{Ja) = 8.y. (4)

Например, термы s + Jqn J {s s) будут иметь номера 2-3-5*3 и соответственно В-З".