строим расширенное соответствие (6). Как уже говорилось, номера соответствий (5) и (6) обозначаются через S (т, п) и Т (т, /г), где п - номер соответствия (3).

Конечно, нас интересуют лишь случаи, когда последовательность (3) является финитным соответствием. Однако с формальной точки зрения описанные выше процессы нахождения числа уь+х в случаях а), б) дают определенный результат и тогда, когда последовательность (3) не есть финитное соответствие. Чтобы достичь этого в случае в), достаточно считать серию г/;„ г/;, . . у обрываюгдейся, как только окажется, что / (xt) {уо, , Ут:} или что yi совпадает с каким-либо предыдущим членом в последовательности У1, У1, . . .

После этого дополнительного замечания мы можем считать функции S (т, п), Т (т, п) онределенными для всех значений т, п, исключая /г = О, 1, так как последовательностей с такими номерами вообще нет. Но мы и для /г = О, 1 доопределим функции S (т, п), Т (т, п) каким-либо регулярным способом. В результате будем иметь всюду определенные функции S, Т, значения которых вычисляются при помощи точного алгоритма. Согласно тезису Чёрча отсюда следует рекурсивность функций S, Т. Строгое доказательство рекурсивности S, Т требует, чтобы функции S, Т были выражены через /, g и другие рекурсивные функции ири помощи операций подстановки и х-онераций. Ввиду рутинного характера соответствующих вычислений здесь их приводить не будем.

Итак, нами построены общерекурсивные функции S и Т. Функция S позволяет финитное соответствие с номером п нонолнить нарой (jn, yn+i}, содержащей в качестве левого элемента произво-иьно заданное число т, а функция Т позволяет финитное соответствие с номером п нонолнить нарой (Хк+х, тУ, содержащей произвольно заданное число ттг в качестве правого элемента.

Берем теперь простейшее соответствие, состоящее все-гоиз одной пары <0, / (0)>, и называем его начальным, а затем ностененно расширяем его, применяя поочередно функции S ъ Т так, чтобы в целом нолнлось отображение всего натурального ряда на себя. Для более точного описания этого процесса вводим функцшо w (х), значение которой W (п) будет равно номеру п-то расширения начального соответствия. Полагаем но определению

W (п -Ь 1) =

/ re-f 1

, W {п) , W (п)

если п четно,

если п нечетно.

Отсюда видно, что функция w (х) возникает иримитив-иой рекурсией из функции

n + i

+ + .7

и потому W {х) - общерекурсивная функция.

Рассмотрим, наконец, функцию у = h{x), значение которой у равно правому числу той пары финитного соответствия с номером W {2х), левое число которой равно х.

Согласно схеме (8) последняя пара финитного соответствия с номером W {2х) имеет вид {х, Ук+хУ, причем

Ук+х = [ех {2х, W (2а;)) - i],

где [zjgg - правый элемент пары с номером z (п. 7.1). Поэтому

у = h (х) = [ех (2а;, w (2а:)) - i]

II, следовательно, функция h (х) общерекурсивна. Если Хх <. X, то соответствие с номером w (2а;) содержит пары {хх, h {хх)У и <а;, h (а;)>. Из (4) получаем h (хх) ф h (х). С другой стороны, соответствие с номером 2т + i согласно (8) оканчивается парой вида <а; +i, m> и, значит, уравнение k (х) = т имеет решение хц+х для каждого т. Таким образом, функция h (х) взаимно однозначно отображает натуральный ряд на себя, удовлетворяет требованию фа; = \h (х) и представляет искомый изоморфизм нумерации ф на нумерацию ij).

Доказательство теоремы 2 завершено.

Теорелш 1 и 2 относятся к нумерациям одной и той же совокупности объектов. Однако нетрудно нолзпить соответственные теоремы и для нумераций различных совокупностей объектов. Мы ограничимся здесь переформулировкой теоремы 2.

Теорема 3. Пусть заданы какие-либо нумерованные .множества <3/, ф>, (Ж, ф> и взаимно однозначное отображение совокупности объектов Мх первого множества на совокупность объектов второго. Если существуют общерекурсивные функции f [х), g {х), принимающие в раз-

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

I [щ) = {х), I Ы (х)) = х, (9)

то отображение 1, есть изоморфизм (М, ф> на (М, г])), т. е. существует общерекурсивная функция h {х), взаимно однозначно отображающая натуральный ряд на себя и удовлетворяющая требованию

I {щ) = # {х).

Действительно, введем еще одну нумерацию совокупности М, полагая

= С {п). (10)

Соотношения (9) показывают, что функция / {х) одно-сводит г]?! к tl;, а функция g (х) односводит "ф к -ф. По теореме 2 отсюда заключаем, что нумерации ф и ф рекурсивно изоморфны, т. е. что существует общерекурсивная функция h (х), взаимно однозначно отображающая натуральный ряд на себя и удовлетворяющая требованию фа; = ф/г (х). В силу (9) и (10) это соотношение можно переписать в форме (фз;) = ф/! (х), что и требовалось.

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

Обозначим через t, отображение, при котором одноместной частично рекурсивной функции Е (п, х) ставится в соответствие двуместная частично рекурсивная функция К {п, [х, у]). Ясно, что взаимно однозначно отображает совокупность %l.v всех одноместных частично рекурсивных функций на совокупность 5р.г всех: двуместных частично рекурсивных функций. Ищем такое постоянное а, чтобы

К [п, [х, у]) = К {[а, п], X, у).

Отсюда полуяае.\1 х?г = х, [а, ?г\. С.чедовательно, функция / [х] = [а, х] «односводит» к х,. С другой стороны,-ищем такую постоянную Ь, чтобы

К {п, lt],y, UU) = K{b, п, t).

Подставляя сюда вместо t выражение [х, у], получим

ff {[b, n], Ix, у]) = E in, X, y\

т. е. t (к [Ъ, п]) = хге. Это показывает, что функция g [х) = lb, х] «односводит» нумерацию х к пумерации х. Слово «односводит» взято нами в кавычки, так как понятие односводимости было нами определено лишь для различных нумераций одной и той же совокупности, а здесь mi пмеем дело с разными совокупностямп и «односводимость» следует понимать в смысле, указанном в теореме 3. Пользуясь этой теоремой, заключаем, что отображение t, есть

изоморфизм <3"р.г, х> на (Ър-г, щУ-

9.3. Полные нумерации. Нумерация ф совокупности объектов М называется полной (см. Мальцев [3]), если в М существует особый объект о, обладающий следующим свойством: для каждой частично рекурсивной функции F (х) существует такая общерекурсивная функция G (х), что для каждого числа х

ц>а (х)

(ц)Р (х), если F (х) определено.

если F (х) не определено.

Здесь, как и всюду, под нумерацией мы понимаем простую нумерацию, у которой номерное множество совпадает со всем натуральным рядом. Если совокупность М содержит лишь один объект, то простых нумераций у М лишь одна и она, очевидно, полна.

Теорема 1. Гомоморфный образ совокупности с полной нумерацией есть совокупность с полной нумерацией.

Действительно, пусть функция h (х) представляет го-модюрфизм полно нумерованной совокупности (Л£, (рУ с особыд! объектом о на нумерованную совокупность O-v Ф) и. значит,

фа; = фг/ = ф/г [х) = (у).

Пусть а - какой-нибудь ф-номер о. Положим о = ф/ (а) и рассдютрид! произвольную частично рекурсивную функцию F {х). По условию найдется такая общерекурсивная Ф.\"нкцня G {х), для которой

h{F{x)), если F{x) определено, 1 фа, если F (х) не опреде.лено.

В сплу (2) дгы дюжед! в этих равенствах сшмвол ф заменить СПД1В0Л0Д1 ф/i и получить, таким образом, условия полноты нумерации ф с особым элементом о.

Из теоремы 1, в частности, следует, что если нумерованное множество изоморфно множеству с полной нумерацией, то оно само имеет полную нумерацию.

Теорема 2. Нумерация Клини полна и имеет нигде не определенную функцию своим особым элементом.

Пусть F (х) - какая-нибудь частично рекурсивная функция. Ищем такое число а, чтобы для всех значений X, t было

Е {F (х), t) = К {[а, х], t).

Таким образом, если F (х) определено, то функция с номером [а, х] совпадает с функцией с номером i? (х). Если же F (х) не определено, то функция с номером [а, х] есть нигде не определенная функция о. Следовательно, общерекурсивная функция G (х) = [а, х] удовлетворяет условию (1) и нумерация х полна.

В п. 9.2 было установлено, что нумерация Клини Ks всех s-местных частично рекурсивных функций изоморфна нумерация х. Поэтому вместе с нумерацией х полными являются и все нумерации Xj. В п. 9.1 показано, что нумерация Поста л: есть гомоморфный образ нумерации к. Следовательно, я - также полная нумерация, причем особым элементом для л: является пустое множество.

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

Мы хотим теперь некоторые свойства нумерации Клини, полученные в § 7, распространить на произвольные полные нумерации.

Теорема 3. Для каждой полной нумерации ф и калсдого г существует общерекурсивная функция P\f (ж, . . ., Хг), об.чадающая следующим свойством: для каждой частично рекурсивной г-.честной функции Н [xi, . . Хг) существует такое число а, что для любых значений х, . . х.

фРф (а, X., . . ., х,) =

ц>Н(а, Хп, . ., Хг), если Н(а, Хо,. .., х,)

определено, (3)

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

Рассмотрим вспомогательную функцию F{x) = K {[х],„ . . ., {х]гг),

где {x\ij - введенные в п. 7.1 нумерационные функции. Вследствие полноты ф существует общерекурсивная функ-]щя G {х), связанная с F {х) соотношениями (1). Из (1) подстановкой х = [х, . . ., ж] получаем соотношение

[G{[xi,х,]) =

фJ5C(Жl, • •, Хг), если K{xi, . . ., х) определено,

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

Поканем, что функция

Рф [Хх, . . ., Хг) = G {[xi, . . ., ж,.])

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

Н {{Хх, Х}, Х,. . Хг) = Е {1с, Xj], Xz, . . ., Хг).

Полагая здесь х = с, а = [с, с] и подставляя в (4) вместо Xl число а, получим (3).

Теорема 4. Для каждой полной нумерации ф и каждой частично рекурсивной функции f {Xi, . . ., Xr) существует такая общерекурсивная функция g . . ., Хг), что

W {Х, . . ., Хг) = ф/ {g (Xz, . . ., Xr), Xi, . . ., Xr),

если f {g {x2, . . ., Xr), X2, . . ., Xr) определено, и Ц)g {x2, . . ., Xr) = 0 в противном случае. Рассмотрим функцию

Я {Xi, . . ., Хг) = f (Рф {Xi, . . ., Хг), . . ., Хг),

I де функция Рф указана в теореме 3. Согласно теореме 3 Найдется число а такое, что

Ч>Рц [а, Х2, . . ., Хг) = ф/ (Рф {а, . . ., Хг), Хо,. ., Хг),

РСЛ11 выражение, стоящее справа, определено, и

фРф {а, Хо, . . ., Хг) = о

li противном слтсае. Отсюда видно: чтобы удовлетворить Рореме 4, достаточно в качестве функции (.г.,, . . ., Хг) "зять {а, Хо,-. .., Хг).