И = (/ (г) = X V (/ gjt) = X)),

lF(x), если {{h(x))=x, G(x), если g(h{x)) = x.

Аналогичное построение проходит и для функций от большего чпсла переменных (см. п. 7.3).

И, Основываясь на глубокой теореме (см. § 16) о представимости рекурсивно перечислимых совокупностей ге-ок чпсел в экспоненциально диофантовой форме, Д е в и с [3] показал, что существутот функции Р (х), g (х, у, z), h {х, у, z), получающееся конечным

числом подстановок пз функций о, ху, 2, I (х), г (х), такие, что каждая одноместная частично рекурсивная функция / (х) представима в форме

/ (х) = Р (t (g (п, X, t) = h {п, X, t))).

12. Бинарное отношение <, определенное на натуральном ряде, назовем простым понструктивным расположением натуральных чисел, если существует общерекурсивная функция а {х), значение которой 0 (п) есть «ближайшее за п большее чпсло» в смысле порядка < и если отношение < упорядочивает натуральные числа в простую последовательность, т. е. если все натуральные числа содержатся в последовательности

а < 0 (а)< 0 (0 (а)) < . . . < 0 (а)< . . .

Показать, что каждая общерекурсивная функция / (г) представима в форме f (х) = g (2*), где g определяется схемой

g (а) = ао, g (х) = h [х, g (а (х))) {х ф а).

(«)

Здесь а - наименьшее число в подходящем конструктивном простом порядке <, а {х) и h {х, у) - примитивно рекурсивные функции, причем а(х) <х для хф а (см. Л ю [2], М а й х и л [1]).

13. Показать, что существуют общерекурспвные одноместные функции, не представимые в виде ф {g (х)), где ф примитивно рекурсивна, а g определяется схемой (а) пз предыдущей задачи. (Проблема Раутледжа. Решение см. Л ю [1].)

Г ЛАВ А IV

НУМЕРОВАННЫЕ СОВОКУПНОСТИ

Для того чтобы понятия рекурсивности и рекурсивной перечислимости перенести из области натуральных чисел в область более сложных объектов - /г-ок чисел - мы предварительно занумеровали все п-ки натуральными числами. В данной главе метод нумерации будет рассмотрен в общем виде. Он позволяет глубже вскрыть природу алгоритмических процессов и прямым путем приводит к решению многих интересных проблем. Впервые метод нумерации для решения фундаментальных вопросов математической логики был применен К. Гёделем, вследствие чего многие важные нумерации обычно называются нумерациями Гёделя. При более детальном изучении конкретных нумераций Гёделя целесообразно, однако, ввести особые названия для некоторых из этих нумераций, что ниже и сделано.

§ 7. Нумерации совокупностей множеств и функций

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

7.1. Универсальные функции Клини. При детальном изучении свойств частично рекурсивных функций удобнее пользоваться не универсальнылш фукциядш (xq, х,... . ., Хп), построенныдш в п. 6.2, а особыми фзнкциями Клпни, к определению которых мы и перейдем.

Введем стандартное обозначение

[х, у] = е{1 [х), с [г (х), у)).

где с [х, у) - канторовский номер пары <х, г/>, а I (х) п г (х) - левое и правое чпсло пары с номером х (п.3.3).

ределения множество А а в каждой точке х А значение Н (х) или совпадает с F (х), или совпадает с G (х).

Пусть области определения функций F и G суть множества значений примитивно рекурсивных функций / (г) и соответственно g (х). Полагаем

ГЛ. IV. НУМЕРОВАННЫЕ СОВОКУПНОСТИ

Из тождеств

с {I (ж), г {х)) = X, г {с {х, у)) = X, г (с (х, у)) = у

и формулы (1) непосредственно следует, что если [х, у] = = и, то

х = с{1 (п), I {г {п))), у = г {г (п)). (2)

Поэтому вводя обозначения

[xki = с{1 {х), I {г (х))), [х]22 = г {г (х)),

будем иметь тождества

[[xlai, гз] = X, [[х,у]]21 = X, [[х, Паа = У,

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

IXi, Х2, . . ., Xg] = l...llXy, Х2], Xsl, . . ., Xs] (s = 3, 4, . . .),

получим взаимно однозначную нумерацию s-ок чисел. Решая уравнение

[ху, . . Xs] = X (4)

относительно х, . . ., Xs, будем иметь

Хх = [[... [а;]2х]21 • • • Idii 2 = [[ . . . [[3]2i]2i • • •] ггкз) • • •>

Xs = Ы22- (5)

Правые части этих равенств обозначим соответственно через [x]sx, . [x]ss- Тогда из (4), (5) получим тождества

Hx]sl, . . ., [x]ss] = X, [[Хх, . . ., Xs]]si = Xi.

Отметим еще тождество

[Хх, . • • , Xjnt Xjn+X • •> Xs\ -

= [[Хх, . . ., Хщ], Xjyi+Xf • • • Xs], (6)

непосредственно вытекающее пз (3).

Функции Кантора с [х, у), I (ж), г (х) - прилштивно рекурсивные функции, выражающиеся через свои аргументы при помощи элементарных арифметических операций -{-, X, [Y], I /2]. Формулы (1), (2) показывают, что такими же будут и функции [х, у], [x]ij.

Теперь мы вместо универсальных функций Т+ (xq, Хх, . . X Xs), построенных в п. 6.2, введем следующие

функции Клини:

(хо, Хх) = (1 (хо), с (г (жо), Хх)),

К {Хо, Xj, . . ., Xs) = К (Ixo, Хх\, Х2, . . ., x,) (s =

= 2,3,...). (7)

Из тождества (6) вытекает важное соотношение

Ю"-- (Хо, . . ., Xs+t) = ([Хо, . . ., Xs], Xs+i, . . ., Xs+i),

связывающее функции Клини, имеющие разное количество аргументов.

Лемма 1. Функция Клини {ху, . . ., Xs) связана с универсальной функцией Г (xq, Хх, . . ., Xs) тождеством

К (с [хо, Хх), Х2, . , ., Xs) = Т (жо, Хх, . . ., Xs). (9)

Прежде всего заметим, что нумерации с {х, у) и [х, у] удовлетворяют своеобразному закону ассоциативности

с (хо, с {Хх, Х2)) = [с {Хо, Хх), Х2], (10)

легко проверяемому с помощью тождеств, связывающих функции I {х), г {х), [х, у]. ,Цалее,

Ю (с {хо, Хх), Х2) = (хо, с {Хх, Х)) = Т (Хо, Хх, Х2).

Аналогично,

(с {Хо, Хх), Х2, Xs) = Ю ([с (Хо, Хх), Х], Xs) = = Ю (с (хо, с (Хх, Х2)), Хз) == (%, с {Хх, Х2), Хз) =

= [xq, Хх, Х2, Xs)

II т. д.

Теорема 1. Функция Клини К"" (жц, Ху, . . ., Хп) является частично рекурсивной функцией, универсальной для совокупности всех п-местных частично рекурсивных функций от ж,, . . ., Хп-

Пусть / [хх, . . ., Хп) - какая-нибудь частично рекурсивная функция. Из универсальности функции Г"*- следует, что при некотором фиксированном а будем иметь тождество

0-х + f {хх, . . ., Хп) = {а, x, Хх, . . ., Хп) =

= (с {а, х), Хх, . - -, Хп).

Полагая в не.м а; = Ои обозначая число с {а, 0) через Ь, ползшим тождество

f(xx, - - .,хп) = Я"-! {Ь, Хх, . . .,Хп),

которое и доказывает, что функция (а:, х, . . Хп)

универсальна для частично рекурсивных функций от переменных Xl, . . Хп.

7.2. Нумерация Клини. Ставя каждому натуральному числу п в соответствие одноместную функцию [п, х), получим отображение множества всех натуральных чисел У на совокупность всех одноместных частично рекурсивных функций. Это отображение будем далее называть i нумерацией Клини и обозначать через х. Там, где не воз-вшкнет опасность налонения обозначений, вместо Xl, . . ., Xs) будем писать просто Ж (жо,!, . . ., х). Число п называется клиниевским номером функции Б- [п, х), которая будет обозначаться также через %п и иногда через Z„.

Теорема 1. Для каждой, частично рекурсивной функции f {х) существует такое фиксированное число а, что все числа последовательности

[а, 0], [а, 1], . . ., [а, т], . . . (1)

будут клиниевскими номерами функции f{x).

По условию f (х) = К (п, х). Так как К (х, у, х) - универсальная функция, то найдется такое число а, что при любых значениях переменных у, х

0-У + f{x) = К (а, у, х)= К {[а, у], х).

Поэтому последовательность (1) действительно состоит из номеров / {х).

Рассмотрим следующую задачу: даны клиниевские номера функций f (х) и g [х). Требуется найти клиниевские номера их суммы и суперпозиции.

Рассуждав!*! так. Берем следующие функции от переменных и, V, х:

К (и, х) + К [и, х), К (и, К (V, х)).

Так как К {х, и, v, х) - универсальная функция, то найдутся такие числа а, Ъ, что тождественно относительно и, V, X

К [и, х) + К (у, х) = К (а, и, V, х) = К {{а, и, v], х), К (и, К {V, х)) = К{Ь, и, у, ж) = Ж {[Ь, и, V], X).

Следовательно, если т, п - номера функций /, g, то числа [а, т, п], [Ъ, т, п] заведомо будут номерами j + g ж f{g{x)).

Аналогичные утверждения имеют место для р,-опера-Ц1Ш, операции примитивной рекурсии и других операций.

Несмотря на простоту доказательства, следующая теорема играет значительную роль во многих рассуждениях.

Теорема 2 (теорема Клини о неподвижной точке). Для каждой частично рекурсивной функции h (xi, . . . [ . ., Хп, Xn+i) существует такая примитивно рекурсивная функция g {xi, . . ., Хп), что

%h{xi, . . ., Хп, g [Xi, . . ., Хп)) = KgiXi, . . ., Хп)*). (2)

В частности, для каждой частично рекурсивной функции h [х) существует такое число а {«.неподвижная точка» отображения К), что

%h (а) = ш. (3)

Докажем первое утверждение. Рассмотрим вспомогательную функцию К {h {xi, . . ., Хп, [у. У, Xl, . . ., Хп]), t). Из универсальности функции К {хд, у, Xi, . . ., Хп, t) следует, что при подходящем числе а имеем тождество

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

= К {h {xi, . . .,Хп, [у, у, Xl, . . ., Хп]), t).

Полагая здесь у = а, \а, а, Xi, . . ., а:„] = g (xj, . . . . . ., Хп), получим искомое тождество (2). Соотношение (3) можно рассматривать как частный случай соотношения (2) при и = 0.

В связи с нумерацией Клини естественно возникает вопрос о том, какие свойства частично рекурсивных функций можно эффективно распознать по номерам функций. Например, естественно спросить, существует ли алгоритм, позволяющий для произвольного п узнать, является ли функция с номером п нигде не определенной, тождественно равной нулю, примитивно рекурсивной и т.п. В точных терлшнах этот вопрос можно изложить следующем образом: является ли рекурсивной совокупность клиниевских Номеров нигде не определенной функции, тождественного нуля, всех примитивно рекурсивных функций? Нижеследующая теорема дает отрицательный ответ на все эти попросы: нпкакое нетривиальное (т. е. присущее некоторым, но не всем функциям) свойство одноместных частично рекурсивных функций не может быть эффективно

*) При этом, если h [xi, . . ., .т„, g (xi.....ж„)) не определено,

читается, что обе части (2) означают нигде не определенную функцию.