случай III В)), в этом случае ничего не меняем, т. е. полагаем 1 == " / ( t) = i{l,t- 1) для всех xiil.

Случай III: нп случай I, ни случай II места не имеют. Тогда выиолняе»! последовательно слудующие операцпи:

A) Если / (г,, t - i) оиределепо, то полагаем / (i,, t) = у = = / t - 1). Если же / (li, t - 1) не определено, то через у обозначаем наименьшее из чисел, не бывших до момента t ни разу последователями, и полагаем / (Z,, t) = у.

Б) Полагаем = S\j у л\. В силу свойств 3), 4) или

= 0, пли С а\. Поэтому после выполнения операцпи Б) будем иметь S\j = а\ .

B) Если существует такое х (единственное в силу 5)), что

S. = а\ и x ф у, то полагаем = yg (s), где s - наименьшее чпсло, при котором yg (s) содержит S*" п отлично от Sy, Sg", S\~, . . . Согласно условию р) такое s заведомо существует.

Выполняя операцию В), мы говорим, что смещ:ем число х числом It Б момент t.

Г) Если число x, смещаемое числом в момент t - 1 не свободно, то освобождаем х.

Полагаем = Sf, f {I, t) = f {I, t - 1) для всех z, I, которые не упоминаются в А), Б), В), Г).

Итак, способ построения S, / {I, t) указан. Из него непосредственно следует, что лшожества S, а\ и функция / {I, t) удовлетворяют требованиям 1) - 5). Докажем, что эти лшожества и функция обладают также следующим свойствами 6) - 9).

6) Каждое число х может смещаться лишь конечное число роз. Пусть x смещается в момент t и не свободно в момент t - i.

Тогда в силу Г) оно будет свободно в момент а в силу 2) х будет свободным и во все последующее моменты. Пусть х смещается снова в какой-нпбудь пз этих исследующих моментов и > t числом 1. По условию x свободно в момент и - 1. Еслп бы было х 1ц пли x смещался числом In ранее !\юлгента и, то у нас был бы сдз-чап Иб) пли Ив), что невозможно. Таким образом, во все последующие моменты и число х июжет смещаться лишь числами 1, меньшими х, I! каждым не более одного раза. Следовате.чьно, х смещается не более конечного чпсла раз.

7) Каждое Sx содержится в ©. Ec.iu Sx бесконечно, то число xt начиная с некоторого .мо.мента t, постоянно является пос.гедоват.ге.ч некоторого а и = Аа-

Сначала предположим, что Sx конечно. Тогда д.чя некоторого t Sx = S. G ©о п потому Sx G ©•

Пусть теперь S бесконечно. Так как Sx есть объедпнение возрастающей иос.чедовательностп конечны.х дшожеств (t = = О, 1, . . .), то в этой последовательности бесконечно лшого раз должен встречаться случай, когда ф S. Но это возможно лишь либо в случае III В) {х = у), либо когда х в момент t смещается

t

ЧИСЛОМ Ц. Согласно свойству 6) число х может смещаться лпшь конечное чпсло раз. Поэтому для бесконечно многих t должен наступать случаи III В), х = / (If, t - 1). Но X не может быть последователем разлтных чисел. Такпм образом, для бесконечного чпсла значений t имеем а = Ц, х = f (а, t - 1), S = А. Следовательно, начиная с некоторого момента t, х - последователь а и S = Аа-

8) Если x ф у, то Sxф Sy.

Пусть, напротив, хф у, Sx = Sy. Если S, Sy конечны, то для некоторого t было бы S. = Sy, что противоречит свойству 5). Пусть Sx, Sy бесконечны. Тогда в силу 7) должны существовать такие числа а, Ь, что Sx = Аа, Sy = А, п, начиная с некоторого мо.мента о, числа х, у - постоянные последователи чисел а, Ъ. Так как х ф у, то а ф Ь. Пусть а < Ъ. Жз Аа = А следует, что, начиная с некоторого момента ty,

{О, 1, . . ., J/} П 4 = {О, 1, . . ., Ь} П Ai it > ty).

Берем такое t, что = Ь, i > «р, i > ty. Тогда в момент t имеем случай I и потому в этот момент должны освободить число у воирекм иредноложеншо. Итак, Sxф Sy и свойство 8) доказано.

9) Каждое Аа совпадает с некоторым Sx-

Пусть т - наименьшее число, для которого А = Аа, п потому для каждого I <; т имеем А) ф А- Мнонества Ai и А. отличаются некоторым элементом z, {I = О, i, . . ., т - 1), входящим в одно из них и не входящим в другое. Берем такой момент и, когда каждое из чисел Zq, Zi, . . ., z j уне находится в соответствующем

пз множеств А, А, . . ., A]j . Тогда не только в момент и, по и п произвольные более поздние моменты ty, t будем плгеть

A\фAl {l<:m,ty>u,tu)

и, сверх того,

{О, i, . . ., х} f] а\ф {О, i, . : ., х} f] а (x>z), (3) где S =г шах {z„, Zy, . . ., z J .

Допустим, что в какой-то момент i,, некоторое число с приобретает последователя х, раньше последователем не бывшего. Поскольку последователи приобретаются только посредством операцип III А), то

1, = с, x = f (с, г„), 4 = А*.

Посмотрим, как меняется .S при возрастании t от до момента !•, в KOTopuii х освобождается. Измененпе множества 5 может происходить лишь прп помощи операции III Б) п операции смещешш .1, во время которой происходит одновременно и освобождение х. Поэтому до момента освобождения .г- ьшожество может увеличиваться лпшь при П01ЮЩП операции 1П Б), т. е. в те моменты t, когда

1, = с, x = f (с, t), Sl: = 4. Таким образом, если t растет от до v, то множество S нооче-редно становится равным а1\ 4*, . . ., А и перед моментом

освобождения v

- Ак

Может ли число т бескопечно много раз приобретать и потом терять последователей? Произвольное число, побывав последователем и освободившись, вновь последователем стать пе мол?ет. Поэтому, если ответ на поставленный вопрос положителен, то число т в какой-то момент > " должно приобрести последователя з; > z и затем в некоторый момент у > и потерять его. Покалим, что это невозможно.

Освобождение х может происходить двумя способами: после операции смещения х числом Ij, и при помощи случая I, когда т = Ij,. Так как

г > Z, X = f {т, V - i), у > к,

то из неравенств (2) вытекает, что освобождение при помощи случая I невозмояшо. Допустим, что х смещается в момент у числом 1 и потому

5-1=4, xf{m,v-i), 1<т.

Сравнивая эти условия с равенством (4) для с = т., получаем

{t>tu>u, V>u, 1<т),

что и противоречит соотношению (2).

Итак, ответ на заданный вопрос отрицателен и потому существует такой момент w, начиная с которого т не может терять последователей.

Сзтцествует бесконечно много значений t, удовлетворяющих условиям Ц = т, tw. В каждый из таких моментов t число т не может терять последователя и потому в момент t случай I заведомо не HacTjrnaeT. Допустим, что в рассматриваемые моменты бесконечно часто nacTjTiaeT случай III, т. е. для бесконечно многих значений t

т=1и x=j(m,t-i), SI = aI„ {tw).

Так как, начиная с момента w, число т не может менять последователей, то чпсло X здесь от t не зависит. Но если для фиксированных X, т равенство Sj. = А] выполняется при бесконечно многих значенпях t, то = А п, следовательно, утверждение 9) при сделанных дощтценпях истинно.

Допустим теперь, что слай III выполняется лпшь для конечного чпсла paccмaтpпвaeuiIX значений t. Тогда бесконечно часто должен встречаться хотя бы один из случаев Па), Иб), Ив).

HjCTb бесконечно часто встречается случай Иб), ири котором

X т.

Чпсло X здесь может меняться с ростом t, но множество возможных значений для него лшпь конечно. Поэтому для какого-то фнксп-рованпого X равенство = а\ будет пметь место при бесконечном числе значений t и потому Sx= Am-

Пусть бесконечно часто наступает случай Ив), когда

= 4 и X ранее смещен числом т. (5)

Но в момент S смещения х числом т должен наступать случай III, а таких моментов по предположению существует лишь конечное число. Поэтому в соотношенип (5) х хотя и зависит от t, но может принимать .лишь конечное число значений. Среди этих значений найдется такое а;, при котором равенство = а} будет выполняться для бесконечно многих значений i, откуда снова 8= А. Нако-пец, пусть бесконечно часто наступает случай Иа), при котором

S-i = Ai

x = f(l,t-l), Z<m, t>w.

Значение I здесь, вообще говоря, зависит от t, но так как оно пе больше фиксированного числа т, то условия (6) должны выполняться бесконечно часто и для некоторого фиксированного значе-нпя I, которое далее только и буд&т рассматриваться.

Пусть I = т. Так как после момента ц? число m не меняет последователей, то а: в (6) не зависит от t и потому S~ = А* для бесконечно многих значений t, откуда Sx = А-

Аналогично, если Z <; т, но а: ири изменении t принимает лишь конечное множество значений, то тогда снова при некотором фиксированном X для бесконечного числа значений t будем иметь S*~ = = а1„, откуда Sx = Am.

Остается рассмотреть случай, когда в соотношении (6) для фиксированного I переменная х принимает бесконечно много различных значений при изменении t. Отсюда следует, что число I бесконечно много раз приобретает последователей.

Пусть X становится последователем I в момент > и; и в момент t > ip удовлетворяет требовашшм (6). Согласно (4)

(ift > to).

Сравнивая с (6), получаем

что противоречит неравенству (2). Таким образом, рассматриваемый случай невозмонен, а во всех предыдтцих случаях -оказалось, что Аа = Am = Sx и, значит, свойство 9) пстинно.

Свойства 7) - 9) в совокупности означают, что отображение j; является однозначной нмерацисй системы ©. Остается

доказать вычислимость этой нумерации. Правила построения множеств дают воз>южность для каждых .т, t найти стандартный номер ф (х, t) множества s\. причем легко убедиться, что функция ф [х, t) общерекурсивна.

С другой стороны, легко строится примптивно рекурсивная функция у (р, х), совокупность значений которой прп каждом р>0 совпадает с конечным множеством, имеющим стандартный номер р. Рассмотрим общерекурсивняо функцию Ф {х, t, у) = у (ф {х, t), у). Фиксируя X и меняя t, у, получим в качестве значений фу1шцип ф

все числа ишожсства Sx п только их. Поэтому фупкция Ф (х, I (и), г (и)) является искомой общсрекурсивпой функцией, универсальной для нумерации х -» Sx, что и требовалось.

Следствие (Ф р и д б е р г [1]). Совокупность © всех рекурсивно перечислимых множеств обладает однозначной вычислимой нумерацией.

В самом деле, семейство © вычислимо, так как оно имеет уни-версальн}чо частично рекурсивную функцию К (п, t). С другой стороны, оно содержит все конечные множества, совокупность которых п можно взять в качестве семейства ©q, указанного в условиях теоремы 3.

Выше рассматривались семейства множеств чпсел. Переход от семейств множеств к семействам функций требует лишь нескольких очевидных дополнительных замечаний.

Пусть @ - семейство одноместных функций. Отображение а: iV -> ® натурального ряда на © называется нумерацией ©. Если различным числам отвечают различные функции, то нумерация называется однозначной. Функция F (и, х) называется универсальной для пу.черации а, если число п есть а-номер функции f [х) = = F (п, х). Нумерации, имеющие частично рекурсивные универсальные функции, называются вычислимыми.

График функции / (х) - это совокупность пар чпсел <х, у)>, удовлетворяющих соотношению f (х) = у. Совокупность канторовых номеров этих пар условимся временно называть i-графиком функции/. Согласно п. 6.1 функция / частотно рекурсивна тогда и только тогда, когда ее 1-график - множество, рекурсивно перечис-лимое.

Пусть задана какая-либо нумерация а: 2V -> @ некоторого семейства функций © и пусть п - а-нодгер функции / £ ©. Ставя числу п в соответствие 1-графпк функции /, пол>чим нумерацию семейства <В\ 1-графиков функций из ©. Эту нумерацию семейства ©1 также будем называть а-нумерацпей.

Теорема 4. Семейство функций @ тогда и только тогда вычислимо {соответственно однозначно вычислимо), когда вычислимо {однозначно вычисли.мо) семейство ©, i-графиков функций из ©.

В самом деле, пусть А (ге, t) - универсальная фупкция для семейства ©j. Фиксируем п. Совокзшность An значений функции А (ге, t) будет 1-графиком некоторой функцип / {х) пз @. Найдем эту функцию. Пусть X задано, у = j (.г). Тогда номер пары <.г, уу должен принадлежать An, т. е. для подходящего t

с {х, у) = А (ге, t), х = 1{А {п, t)), у = г {А {п, t)).

Беря для t наименьшее значение, удовлетворяющее второму равенству, пол}чим

у г {А (ге, ц, {1А{п, t) = х))) = В {п, х).

Таким образом, функция В (ге, х) является частично рекурсивной универсальной функцией для семейства ©.

Аналошчно доказывается п обратное утверждение.

Частичная фзцпя называется конечно определенной, еслп она имеет определенные значения .лпшь для конечного чпсла значений аргумента. Ясно, что частичная фрткция является конечно определенной тогда п только тогда, когда ее 1-графпк является конечным множеством. Стандартны.ч но.чером конечно определенной функции

будем называть стандартный номер ее 1-графика. Семейство ©„ конечно определенных функций называется у-неречислимым, если совокупность стандартных номеров функций из ©j, рекурсивно иеречислима.

Из теоремы 3 непосредственно вытекает

Теорема 5. Пусть вычислимое семейство (5* частично рекурсивных одноместных функций содержит у-перечислимое подсемейство @* конечно определенных функций такое, что

а) любая конечно определенная функция (х), содержащаяся *) в произвольной функции f {х) из ©*, содержится в подходящей конечно определенной функции /i {х), содержащейся в функции / {х) и входящей в подсемейство. ©;

Р) каждая функция из © содержится в некоторой отличной от нее функции из

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

Для доказательства достаточно вместо семейств функций ©*, ©* рассмотреть семейства ©, ©„ их 1-графиков и воспользоваться теоремам 3 и 4.

Как и в случае теоремы 3, из теоремы 5 вытекает главное

Следствие (Фридберг [1]). Семейство © всех одноместных частично рекурсивных функций обладает однозначной вы-числи.чой нумерацией.

Действительно, семейство © вычислимо, так как функция Клини К {п, х) является для него универсальной. С другой стороны, © содержит семейство ©овсех конечно определенных функций, заведомо обладающее свойствами а), Р), указанными в теореме 5. Легко доказывается, что ©„ •у-перечнслиио и потому © обладает однозначной вычислимой нумерацией.

Дополнения, примеры и задачи

1. Показать, что значения выражений [в, х\, [х, х] являются монотонно возрастающиш функциями от х.

2. Используя предыдущий результат, доказать следующее уточнение теоремы Майхила о неподвижной точке: для каждого рекурсивно иеречпслимого предиката Р {х, у, z) существует такая .юнотонно возрастающая пртштивно рекурсивная функция g {у), что Р {х, у, g {у)) хе. ng {у).

3. Доказать счцествование примитивно рекурсивной функции Ф {т, ге, и, V) такой, что если функции / (.т), /., (.г), gy {х), g, (.v) имеют клинпсвскис номера т, п, и, v, то ф (;ге, п, и, v) будет клиниевским номером фзнкцип h (.г), определенной в теореме 4 п. 6.3 ;1ля ге = 2, S = 1.. •

4. Показать, что объединение конечного чпсла вычислимых семейств лгаожеств есть вычислп&юе семейство.

5. Семейство всех рекурсивно неречислимых подмножеств данного рекурсивно перечпслимого множества и семейство всех частично рекурсивных функций, содержащихся в заданной частично рекурсивной фз-нкцип, являются вычпслпмышг.

*) Функп(пя / {х) содержится в g (.г), еслп график / (х) содержится в графике функции g {х).