будут получаться элементы упомянутых мно?кеств, а некоторые шаги будут давать промелуточные результаты. Получив после какого-нибудь шага число х из некоторого яг} или пару чисел (х, у} из Ai, проверим, не будет ли среди всех полученных, в том числе и на предыдущих шагах, чпсел, пар чисел и информации вида а 6 яг, {а, Ъу G Aj для какой-нибудь г-й нары утверждений х G rtzj, <(а;, уУ G A-i. Как только такая пара найдется, процесс I прекращается и вычисляется значение Fi {х, у). Это и будет значением выражения F [х, у, z, . . ., z). Если указанный процесс не обрывается, то F {х, у, z, . . ., z) считается неопределенным.

Ясно, что построенная таким образом функция F удовлетворяет требованиям теоремы 3. Значения F вычисляются посредством процесса, имеющего алгоритмический характер. В силу тезиса Чёрча (п. 2.3) мы молем верить, что функция F частично рекурсивна. Однако для формального доказательства частичной рекурсивности функции F надо все же выразить F при помощи операций подстановки и [х-операции через рекурсивные функции, т. е. переложить приведенное выше определение функции F на язык формул. Это мы теперь и сделаем.

Ищем такие числа а„, чтобы

Fi {х, у) = К (ai, X, у) = К {[ui, х], у) {i = 1, . . ., г).

Представим график функции w = К {п, у) в параметрической форме:

п = / (t), y = g (t), w = h (t),

где f,g,h - подходящие рекурсивные функции (п. 6.1).

В каждый момент времени t находим числа / (t), g (t), h [t) и запоминаем следующую информацию:

h{t) = K (/ (i), g (i)), h it) 6 я! (t).

В соответствии с изложенным ищем наименьшее ири котором для подходящего г, 1 г г, было бы

h [и) = X, f (и) = Zi, / {v) = -[ai, х], g (v) = у,

где и = [flai, V = Ы22 (см. п. 7.1). Вводя функции Oi (t) = Oi (t, X, у, Zi, . . .,Zr) =

= \x-h{u)\+\f{u)-Zi\+ \f{v)- [ai, x] I +

+ \ g{v)-yU

мы смол<ем искомое значение t представить в виде t* = t* {х, у, zi, . . ., Z,) = lit (Фг- . . . -Ф. = 0).

Зная t*, мы должны найти еще то значение г, при котором Ф; (f") = О, после чего положить функцию F равной величине выражения Fi [х, у) = h {и {t*)). Но это будет достигнуто, если мы по определению положим F [х, у, z,... . . .,z,) = h{v it*)).

Функция F получается из рекурсивных функций /, g, h подстановками, [х-онерацией и операциями --, ~. Поэтому функция F частично рекурсивна, что нам и требовалось.

В теореме 3 указаны функции Ft [х, у) лишь от двух переменных. Однако ясно, что сама теорема и ее доказательство остаются истинными и в случае, когда задаются функции Fi [х, Ух, . . ут), содержащие любое число параметров у, . . ., i/.

Заметим еще, что теорема 3 останется верной и в том случае, если в ее формулировке условия xnzi заменить условиями fi [х, у, Zx, . . ., Zr) = О, где fi - какие-нибудь частично рекурсивные функции, так как в силу и. 7.3 условия /г = О равносильны условиям вида х(:Яд1{у, Zx,. . ., Zr), где (Ji - подходящие рекурсивные функции.

7.4. Однозначные нумерации. Изтиерации Клинп и Поста занимают исключительное место в теории алгоритмов благодаря тому, что, имея какой-нибудь алгоритм для вьписления значений функций /о {х), fx {х), . . . или чисел множеств Sq, Si, . . ., мы всегда можем найти такую примитивно рекурсивную функцию ф (71), что Ф (ге) будет клиниевским номером функции /„ (х) или соответственно постовским номером множества S„. Конечно, нумерации Клини и Поста не единственные из нумераций, обладающих этим свойством. Все Н5Т11ерацпи, обладающие указанным свойством, носят г>бщее название гёделевских нумераций. В известном, точно опреде-чеппом смысле все гёделевскпе нзмерацпи изоморфны друг другу (см. п. 9.3) и все они достаточно сложны. Как мы впделп, каждая частично рекурсивная функция и каждое рекурсивно перечислп-мое множество имеют в измерациях К.линп и Поста нерекурсивные сово5;упности номеров. Естественно вознпкает вопрос: нельзя ли «строить такую нумерацию всех рекурсивно перечислпмых мно-;klctd (или частично рекурсивных функцпп), при которой каждое рскурспвпо перечислп-мое множество (частично рекурсивная функция) имело бы в точности один номер, и в то же время чтобы по но-•еру II множества (функции) в новой нумерации мончно было посредством алгоритма найтп постовский (клпниевскпй) номер ф (ге) ТОГО 1шожества (ф5нкции)? В 1958 г. Ф р п д б е р г [1] показал. Что такие однозначные нугмерацпи рекурсивно перечислпмых множеств II всех частично рекурсивных функций действительно стцест-liyiOT. Ниже эти результаты излагаются в слегка обобщенной форме.

Пусть @ - какая-то непустая система рекурсивно перечпсли-лшх множеств. Произвольное отображение а совокупности натуральных чисел N на систему © называется нумерацией ©. Через а (п) или an обозначается то множество пз ©, которое отвечает числу п при отображении а. Чпсло п называется а-номером множества ал.

Нтиерация а называется вычислимой (Успенский [1]), если существует общерекурсивная функция ф (г) такая, что ф {п) есть постовскип номер множества an, т. е. если

an = яф (ге) (ге = О, 1, . . .).

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

Частичная функция А {п, х) называется универсальной для нумерации а, если для каждого натурального значения ге множество an совпадает с множеством всех значений А (п, х) при х = О, 1, . . .

Легко убедиться, что нумерация а тогда и только тогда вычислима, когда она обладает частично рекурсивной универсальной функцией.

Действительно, пусть частично рекурсивная функция А (п, х) универсальна для нумерации а. Обозначая через а клиниевский номер функции А, имеем для произвольных п, х

А (п, X) = К (а, п, х) = К ([а, ге], х)

и, такпм образом, [а, п] - ностовский номер множества an.

Обратно, пусть нумерация а вьгаислима п ф {п) - общерекурсивная функция, удовлетворяющая соотношению (1). Тогда функция К (ф (71), х) очевидно, частично рекурсивна и универсальна для а.

Нумерация а семейства множеств © называется однозначной, если am ф an для т ф п, т. с. еслп каждое мно?кество из © имеет один и только один а-номер.

Поставим вопрос: какие вычислимые семейства множеств обладают вычислимой однозначной нумерацпе!!? Каковы необходимые и достаточные признаки тех вычислимых семейств множеств, которые обладают вычислимыми однозначнылш нумера-циялш?

Воирос этот в настоящее время, по-видимому, открыт. Нпже даются Л1Ш1Ь достаточные условия, из которых, однако, с.те-дует, что семеГютво всех рекурсивно перечпслпмых множеств обладает однозначной вычислимой нумерацпей. Предварительно докажем следующее очевидное утверждение, справедливое как для вычислимых, так и для однозначных вычислимых нумераций.

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

В самом деле, пусть А (п, х) - нжверсальпая частично рекурсивная функция, осуществляющая (однозначную) вычислимую нумерацию семейства <В. Обозначим через М совокупность тех значений параметра п, для которых уравнение А (ге, х) = у имеет хотя бы одно решение х, у. В силу п. 4.2 множество М рекурсивно неречислпмо. Берем общерекурспвпую функщпо р {t), совокупность значений которой совпадает с Л1 и которая при различных значениях аргумента принимает различные значения (п. 6.3). Ясно, что частично рекурсивная функция

Ау (и, х) = А {р (п), х)

является универсальной для семейства @ - 0. Если нумерация S однозначна, то ввиду равнозначности функции р нумерация, осуществляемая функцией А, (п, х), так?ке однозначна.

Доканем второе утверждение теоремы. Пусть снова А (ге, х) - универсальная функция нумерации семейства © п пусть /q {х), . . . . . ., fs{x) - примитивно рекурсивные функции, совокзшности значений которых Мд, . . ., 31 раз.чичны и не входят в семейство S. Тогда частично рекурсивная функция

Ау{п,х)= 2;fi{x)sg\n-i\-\~sg{ns)A{n{s-i-l),x),

очевидно, яв.чяется универсальной для семейства © п множеств Л/q, . . ., Mg. Прп этом, если функция А давала однозначную пу-лгеращпо, то А дает также однозначную нумерацию.

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

Пусть А (ге, х) - какая-нибудь частично рекурсивная универсальная для © функция. Область определения этой функцип представпма в виде cobokjtihocth пар ф {t), (г)>, t=0, 1, . . ., где ф, - подходящие пршштпвно рекурспвные функции. Для каждого п coBoKjTiHocTb тех значений х, для которых функция .1 (п, х) определена, можно представить в впде совокупности всех р.иачсний, принимаемых при t = О, 1, ... функцией (см. и. 4.2)

В (л, г) = sg I ге - ф (О Н (О Ч- sg I ге - ф (О И (Ру (Ф (у) = ге)). Так как для каждого ге уравненпе ф (у) = п имеет решение, то функция В (п, t) общерекурсивна. Фрткцпя А (п, В (ге, t)) универсальна Д.ЧЯ щшерации а. В силу изложенного она общерекурсивна.

Стандартным но.меро.м (у-номеро.м) конечного множества чисел W], . . ., mji (re!i <"2 <С • • • <! "ift) называется число ге = ~- 2" -L 2™= -f . . . -i- 2". Стандартным номером - пустого множества называется 0. Ясно, что стандартная щтиерация - одна вычислимых однозначных Щмерацпп семейства всех конечных множеств. Характерное ее свойство состоит в том, что прп ней чпсло элементов лгножества с номером п, а следовательно, максимальный п мпнпмальнып элементы этого гножества cjTb рекурспвные функцип от п.

Семейство © каких-нибудь конечных 1Шожеств .называется ".-псречпслпмьш, если совокупность у-номеров лгножеств пз © рекурсивно иеречислима, Всякое у-иеречислимое семейство ко-

нечных множеств, очевидно, вычислимо и даже однозначно вычислимо.

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

Теорема 3. Пусть вычислимое семейство (3 рекурсивно перечислимых множеств содержит у-перечислимое подсемейство ©р конечных множеств такое, что

а) любое конечное подмножество произвольного множества М из © содержится в подходящем конечном подмножестве Mi С М и ЛГ1 S ©о;

(3) каждое множество из ©о содержится в некотором строго большем множестве из ©q.

Тогда заведомо существует однозначная вычислимая нумерация семейства ©.

Из теоремы 1 следует, что при доказательсве теоремы 3 мы можем предполагать, что семейство @ не содержит пустого множества. Согласно теореме 2 в этом случае © обладает общерекурсивной универсальной функцией А {п, г) и © состоит из множеств Ад, А], . . ., Al, . . ., где А[ - совокупность значений А{1, 0), А {I, 1), ... функции А {I, х).

Наша цель - построить такую последовательность Si,. .. рекурсивно иеречислимых множеств, чтобы множества этой последовательности были попарно различны и в совокупности исчерпывали семейство ©. Следуя Фридбергу, будем строить эти множества «шагами». Конечная часть множества S, построенная после г-го шага, бедет обозначаться через а множество S будет но определению равно объединению множеств (i = 0,1,...).

Одновременно с множестваьга будут строиться конечные множества А\ и особая частичная функция / {I, t).

Множества .4 будут строиться так, чтобы выполнялось следующее их свойство:

1) Каждое непустое а\ принадлежит ©„, Ai А\ ( А\ С. . . .

и Al есть объединение всех А\

Если / {I, t) определено при некоторых значениях I, t п х - = / {I, t), то будем говорить, что число х - последователь числа I в момент t. Еслп х = f {I, г - 1), а / {I, t) не определено, то будем говорить, что х освобождается (от I) в .люмент t. Соотношение х = = / {I, t) содержательно означает, что в момент t мы «хотим» далее так строить множества S", чтобы оказалось Sx = Ai, и только некоторые «препятствия» могут нас заставить да.лее отказаться от этогонамеренияи в некоторый момент освободить х от I. Числа, не"являгопщеся в момент t последователям, будем называть свободными в момент t. Наконец, будем говорить, что в момент t обозревается номер li= I [t), где I (t) - левая нумерационная функция из п. 3.3. Из свойств этой фзнкпри следует, что каждый данный номер п - 1) обозревается в бесконечное число моментов t, так как уравнение п = Ц имеет бесконечно 5Шого решенпй для t.

Указываемый ниже процесс построения *шожеств А\, S. и функции / таков, что означенные множества и фзнкция / будут, по»тмо требования 1), удовлетворять также требованиям:

2) в каждый момент t произвольное чисхо х может быть последователем не более одного числа I. Если чисю х в люмент t освобождается, то в момент t и во все следующие моменты х остается свободным.

3) Д.гя каждого х 5° С С С .. . Если ранее момента t число X было свободным все время, то S" = 0.

4) Для каждых х, t из 8\.ф 0 следуем S]. 6 ©о. Если для некоторых X, t x = f(lt, t), то

5) В каждый мо.нент t из Sli=0, хф у следует С . По определению полагаем множества Ji, S~ пустыми и значения / (I, -1) неопределенными {I, х = 0, 1, . . .).

Берем произвольное /! > О и иредполаг*ем, что Af, S, f {I, и)

для всех и -it всех I, х известны и удовлетворяют требованиям 1) - 5).

Построим сначала множества а\. Полагаем а\= 0 для и > Если же V t, то конструнруе}! А следующим образом. По условию существует такая примитивно рекурсивная функция g (п), что числа g (0), g{i), : . ., g (z), . . . являются стандартными номерами всех множеств семейства ©о. Вычисляя ностеиен-по элементы этих множеств и сравнивая длД каждого г = О, 1, ... *1Иожества 7g (0), yg (i), . . ., yg (z) с дданными множествами D . М (у, 0), А (v, 1), . . ., А (и, t)} и растущим множеством \А (и, 0), 4 (у, 1),..., Л (и, z)}, ищем такое значение s, чтобы

{А (V, 0), А {и, t)} и А- С yg (s) с

С {А (V, 0), А (V, 1), А (V, Z)}.

Из предположения а) доказываемой теоремЯ следует, что искомые значения s найдутся. Берем минимальное значение s и полагаем yg {)- Ясно, что построенные таким способом множества а! удовлетворяют требованию 1).

Переходим к определению S. и / (I, t). Здесь придется различать несколько случаев.

Случай 1: / (Z,, t - i) = у ц для некоторого I < Ц

{О, 1, . . ., J/} п а\= {0,i,...,y} п а\. Освобождаем у, полагая / (2,, t) неопределенным, и полагаем

/ {v, t) = / [v, t - 1) (Г ф I,}, si = s-i.

Случай II: случай I места не имеет п существует чпсло х, для которого а1 = S~ и одновременно

а) х= f{l, f-i) и 2 < /,

о) X в момент t-~ 1 свободно в х If, или в) X ь момент t - 1 свободно и ранее момента t чпсло х с.чеще-40 числом, равныл! (операция смещения определена ниже (см.