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

Теорем аЗ (Райе [1]). Если © - непустое семейство одноместных частично рекурсивных функций, отличное от совокупности всех таких функций, то множество клиниевских номеров функций, принадлежащих ©, не моэюет быть рекурсивным.

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

a, если хА,

b, если хА.

Согласно теореме 4 (п. 6.3) функция g (х) общерекурсивна. Применяя теорему о неподвижной точке, приходим к выводу, что должно существовать число п, для которого

%g (п) = %п. (5)

Какое из множестве. А содержит и? Если п А, то при помощи (5) получаем

7ге=4И?г6©=Фх(?г)е©. (6)

С другой стороны, принимая во внимание (4), имеем

n(:A=g{n) = b=4ng(?i) = %b&. (7)

Заключения (6) и (7) противоречат друг другу и потому п не может принадлежать А. Меняя ролями множества А и А, получим, что п не может принадлежать А. Мы получили противоречие, так как каждое число должно входить либо в А, либо в его дополнение А. Теорема 3 доказана.

Итак, совокупность всех клпнпевскпх номеров всех функций любого нетрпвпального семейства функций © не может быть рекурсивным множеством. Однако для некоторых частных семейств © совокупность А будет рекурсивно иеречислпмой. Мы сейчас не будем заниматься разысканием всех семейств ©, обладающих указанным свойством (см. задачи 9, 10 в конце этого параграфа), ограничимся лишь следующим очевидным утверждением.

Теорема 4. Множество А клиниевских номеров gcex одноместных частично рекурсивных функций, прини-уающих в данной точке х = а данное значение Ь, рекур-сивно перечислимо. Множество В всех клиниевских номеров всех непустых *) функций также рекурсивно перечислимо.

В самом деле, А есть множество решений уравнения Л (г/, а) = Ъ. Ввиду частичной рекурсивности функции Q - \К{у, а) - Ь\ это множество рекурсивно перечислимо (следствие 1 теоремы 1 (п. 6.1)). Аналогично доказывается U рекурсивная перечислимость множества В номеров непустых функций.

Согласно теореме Раиса мнолества А ж В нерекурсивны. Таким образом, в дополнение к примеру, построенному в п. 6.3, мы получили серию новых рекурсивно неречислимых нерекурсивных множеств.

7.3. Нумерация Поста. Так как каждое рекурсивно иеречислимое множество есть совокупность значений подходящей частично рекурсивной функции и совокупность значений каждой частично рекурсивной функции есть рекурсивно перечислимое множество, то, называя совокупность значений функции К (п, х) при а; = О, 1, 2, . . . множеством с номером п, мы получим нумерацию всех рекурсивно перечислимых множеств. Эта нумерация называется нумерацией Поста и будет далее обозначаться символом я. В частности, символами яп или 3t„ будет обозначаться множество с номером п, т. е. совокупность значений указанной выше функции К [п, х).

Между нумерациями Клини и Поста существует простая связь, часто позволяющая из свойств одной нумерации пол5Т[ать свойства другой. А именно, если А - какое-нибудь рекурсивно перечислимое множество, то ростовским номером А является клиниевский номер каждой частично рекурсивной функции, совокупность значений которой совпадает с А. Таким образом, еслп совокупностп всех клиниевских номеров отдельных функций называть кли-нпевскпьш кирпичами, а совокупности пестовских номеров рекурсивно перечислимых множеств - постовскими кирпичами, то каждый постовскпй кирпич будет блоком, составленным из целых клпниевскпх кирпичей. Ясно, что для каждого непустого рекурсивно перечпслимого мно/кества А стцествует бесконечно много частично рекур-

*) Пустой называется фшкцпя с пустыл! графиком, т. е. нигде не определенная функция.

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

Заметим еще, что совокупность постовских номеров всех множеств, содержащих данное число а, является рекурсивно перечислимой.

Действительно, эта совокупность совпадает с совокупностью тех значений п, для которых уравнение К {п, х) = = а имеет хотя бы одно решение х. Ввиду частичной рекурсивности функции к указанная совокупность рекурсивно перечислима.

Предикат Р {х, . . .,Хп) называется рекурсивно перечислимым {рекурсивным), если рекурсивно перечислимо (рекурсивно) множество тех и-ок (jc,. . ., ХпУ, для которых предикат Р истинен. Частичной характеристической функцией предиката Р будем называть частичную функцию % {xj, . . ., х, равную О на тех гг-ках, на которых предикат Р истинен, и не определенную там, где предикат Р ложен. Из следствия 3 (п. 6.1) видно, что предикат Р тогда и только тогда рекурсивно перечислим, когда его частичная характеристическая функция частично рекурсивна.

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

Теорема 1 (о представлении предикатов). Для каждого рекурсивно перечислимого предиката Р {х-, . . . .... Xn+i) существует такая примитивно рекурсивная функция h {хо, . . ., Xn+i), что

Р {Хх, Х2, . . ., X„+i) 4=? Xi(: як {Х2, . . ., ВДч!)

для всех значений х, . . ., Xn+i-

Рассмотрпм сначала случай п - i. По условию график предиката Р {х, у) можно представить в виде

X = V {t), у = w{t) {t = О, 1, . . .),.

где V, W - подходящие примитивно рекурсивные функции.

При заданном у все значения t, удовлетворяющие второму из уравнений (2), можно представить (ср. п. 4.2) в виде

t = usg\w {u) - y\-{-sg \w {и) - у \ii{w {z) = y). (3)

Подставляя выражение (3) вместо t в формулу х = v {t), получим формулу вида х = F {у, и), где F - частично рекурсивная функция от у, и. Функцию F {у, и) можно представить при подходящем числе а в виде К {а, у, и) и, значит,

Р {х, у) {Зи){Б {[а, у], и) = х)

Р {х, у) хе [а, у].

Итак, для п = 1 теорема 1 доказана. Пусть теперь и > 1. Обозначим через Q [х, i/) предикат Р {х, [i/]„i, .. . • • fyJnn)- По только что доказанному существует примитивно рекурсивная функция g [у) такая, что

Q {хх, у) xeg {у).

Подставляя сюда вместо у выражение \х2, . . ., Xn+i], получим требуемое утверждение (1)*).

Теорему 1 иногда ф.ормулиру10т в следующем виде: для каждой частично рекурсивной функции F {х-, . . . . . . , Хп+х) существует такая примитивно рекурсивная функция h {х2, . .., Xn+i), что для любых фиксированных значений Хп, . . ., Xn+i множество значений х, удовлетворяющих уравнению F {х, х. , . ., a:n+i) = О, имеет постовский номер h {х2, . . ., Xn+i).

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

Р {хх, . . ., Xn-i) 44 F (Xj, . . ., Xni) = О,

п применить к Р теорему 1.

В качестве одного пз приложений этой теоремы дока-жаем такое

Следствие. Существуют такие прилттивно рекурсивные функции и {х, у), V {х, у), что для .гюбых чисел

*) Если Р - токдественно ложный предикат, то h (.г,..., ,,+i) = = а, где а - какой-либо номер пустой фзкдпи.

142 т, п

П = d(m, п;, л;,„ и я:„ = Ли{т, п)-

Согласно определению л есть совокупность тех зна-чений t, для которых уравнение -ЕС [т, х) = t имеет решение X. Аналогично, я;„ есть совокупность тех значений t, для которых уравнение К [и, у) = t имеет какое-то решение у. Отсюда видно, что мнончсство П состоит из тех значений t, для которых уравнение

1 К (т, х)~ t \ + ]К {п, y)-t \ =0

имеет решение <а;, z/)>. Согласно следствию 4 теоремы о параметризации частично рекурсивных функций (п. 6.1) совокупность Р троек (т, ?г, t}, для которых указанное уравнение имеет решение <(а;, уУ, является рекурсивно неречислимой. По теореме 1 суш;ествует примитивно рекурсивная функция V {т, п), для которой

<7?г, П, tyePtl Л.,гп,пЬ

но это и значит, что я„ f] л„ = яы,п)-

Докажем второе утверждение. Введем функцию

G (т, п, х) -

если X четно, если X нечетно.

Согласно теореме о кусочно заданных функциях (п. 6.3) функция G {т, 71, х) частично рекурсивна. Множество ее значений при а; = О, 1, 2, . . . есть я; (J п- Иш;ем такое число а, чтобы для всех т, п, х

G {т, п. х) = К {а, т, п, х) = К ([а, т, п], х).

Совокупность значений функции К {[а, т, п], х) есть Я1а,т,п]- Такимобразом,

И, следовательно, в качестве искомой функции и (щ, п) можно взять функцию [а, т, п].

В каком-то смысле аналогом для теоремы Клини о неподвижной точке (и. 7.2) является следующая

Теорема 2 (теорема М а й х и л а [2] о неподвижной точке). Для каждого рекурсивно перечпслимого предиката Р [ху, . . ., Xi+i) существуепъ чпакая примитивно

рекурсивная функция g {Xi, . . , Хп), что

Р [Ху, . . ., Хп, g (Хг, . .., Хп)) Xyng [Xi, . . ., Хп) (4)

для всех значений Ху, . . Хп-

В самом деле, согласно теореме 1 найдется такая при.митивно рекурсивная функция /i (xg, . . ., Xni), что будет иметь место соотношение (1). Применяя к функции ll (жа, . . ., Xai) теорему Клини о неподвижной точке, заключаем, что для подходящей примитивно рекурсивной функции g {х2, . .., Хп) будем иметь

(2, . . .,Хп, g (ха, . . ., Хп)) = y-g (2, . . ., Хп). (5)

По для любых чисел а, Ъ равенство иа = влечет ра-БбНство л;а = яЪ. Поэтому из (5) имеем

лЬ, (2, . . ., Хп, g [Xi, . . ., Xr)) = rtg (2, . . ., Хп).

Наконец, подставляя в соотношение (1) вместо хпп выра->1;ение g [х., . . ., а;), с помощью равенства (6) полу-мим (4).

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

Теорема 3 (о совместном нродолжении). Пусть заданы частично рекурсивные функции Ft [х, у) с областями определения Ai {i - i, . . г). Существу em частично рекурсивная функция F [х, у, z, . . z), удовлетворяющая следующим требованиям:

а) F определена для тех и только тех значений х, у, . . ., г,., для которых выполнено хотя бы одно из условий

X (:nzi & (х, уУ е Ai {i = 1, . . ., г);

б) для каждых х, у, Zy, . . z из области определения Функции F сугцествует такое i, что х G г,- и

F (.г, г/, Zi, . . ., Zr) == Fi {х, у).

Функцию F, удовлетворяющую условиям а), б), можно определить, например, следучощим алгоритмом. Пусть заданы какие-нибудь числа а;, у, Zj, . .., Zr. По условию существ5чот регулярные процессы, позволяюпще находить •)ле.л1енты множеств А, . . ., Аг, Лг„ ., Яг. Делаем первые шаги в этпх процессах, затем последовательно делаем вторые шаги и т. д. В результате некоторых шагов