Так как все эти функции примитивно рекурсивны, то; функция Ф также примитивно рекурсивна.

3.3. Нумерация пар и п-ок чисел. Все пары натуральт1 ных чисел можно расположить в простую последовательность и притом многими способами. Для определенности : рассмотрим следующее расположение этих пар, которое мы будем называть канторовским:

<0, 0>; <0, 1>, <1,0>; <0,2>, <1, 1>, <2,0>; <0, 3>, ... (1)

В этой последовательности пары идут в порядке возрастания суммы их членов, а из пар с одинаковой суммой членов раньше идет пара с меньшим первым членом. Обозначим через с {х, у) номер пары <jx, г/> в последовательности (1), причем нумерацию начинаем с нуля. Таким образом,

с (О, 0) = О, с (О, 1) = 1, с (1, 0) = 2, . . .

Число с [х, у) будем называть {канторовским) номером пары {х, у). Через I {п) шг {п) обозначим левый и соответственно правый члены пары с номером п. Например,

I (2) = 1, г (2) = 0.

Мы хотим теперь выразить функции с, I, г через обыгч-ные арифметические функции. Начнем с функции с. Пара \х, уУ находится в отрезке

<0, х + уУ, (1,х + У- 1>, . . ., ix, уУ, ...,ix + y, 0>

на ж-м месте после пары <0, ж-Ь г/>. Перед парой <О, х + уУ в последовательности (1) находятся х + у отрезков, содержащих всего 1 -Ь 2 + . . . + (ж + г/) пар. Поэтому

е{х,у)= (- + y)i- + y + i) ix + y) + 3. + y

Обратно, пусть

X = I {п), у г {п)

и, следовательно, л = с (ж, у). Из формулы (2) имеем

2?г = (ж -f yf -I- Зж Ч- г/, 8/1 -Ы = (2ж + 2г/ -Ь 1)2 + 8ж = (2ж + 2у + 3) -

-8г/-

Отсюда вытекает, что

2ж + 2г/ + К I f 8?г + 1] < 2ж + 2г/ + 3,

Таким образом.

ж + г/ + 1 =

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

l{ii) = x = n-

1 г [,/8» Н-1] + 1

Из (3) и (4) получаем аналогичное выражение для 4 (п), В дальнейшем будет нужен не конкретный вид формул для с (ж, у), I (п), г {п), а лишь то, что эти функции выражаются с помощью подстановок через элементарные арифметические функции -f-, -, •, [У, 1/2].

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

с (г (ге), г {п)) = п, I {с (ж, у)) = х, г (с (ж, у)) = у. (5)

Ясно, что эти тождества не зависят от того, что рассматриваемая нумерация пар канторова. Например, пусть

{Хо, УоУ, <Ж1, У1>, . . ., <.Хп, УпУ, . • • (6)

- какое-нибудь другое расположение совокупности всех пар натуральных чисел в простую последовательность. Обозначая через С (ж, у) номер пары (ж, у) в последовательности (6) и полагая L (/г) = ж„, R {п) = Уп, получим снова функции, связанные тождествами

С (L {п), R {п)) = п, L{C (ж, у)) - ж, R {С (ж, у)) = у,

аналогичными тождествам (5). Обратно, если на тожестве натуральных чисел определены какие-то фзнкции С, L, R, связанные тождествами (7), то, называя номером пары <х,уУ число С{х,у), получим одно-однозначную нумерацию совокупности натуральных чисел. Связанные с этой нумерацией функции будут как раз функциями С, L, R,

с помощью нумерации нар натуральных чисел легко получить нумерации троек, четверок и т. д. натуральных чисел. С этой целью вводим следующие функции:

с* (Xi, Х2, Xz) = с (с (Xi, Х.2), Xz),

..................... (8)

С"+1 {Xi, X-i, . . . , Xn+i) = с"- (с {Xi, X-i), Xs, .. . , Xn+i),

и HO определению число с" (ж, . . ., а;„) называем канто-ровъш номером п-кш ([x-i, . . ., ж„>. Если

с (жх, . . ., Жп) = ж, то из тождеств (5), (8) получаем Хп = г{х), Хп-г = г1{х), . . ., Xi = rl.. .1{х),

xi = ll...l{x). (9)

Вводя обозначения сп [х), . . ., c„i (ж) для правых частей равенств (9), будем иметь

с"(с„1(ж), .. . ,с„„(ж)) = ж,

Спг (с" (a;i,..., ж„)) = Жг (i = 1,..., п).

Это аналоги тождеств (5) для канторовской нумерации ге-ок натуральных чисел.

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

По определению полагаем

Г (ж, у) = rest (Z (ж), i + {y + i)r (ж)). (10)

Отсюда впдно,что функция Гёделя примитивно рекурсивна. Основное свойство функции Гёделя выражает следующая

Теорема 1. Какова бы ни была конечная последовательность натуральных чисел а, а, . . ., Оп, система уравнений

Г (ж, 0) = ао, Г (ж, 1) = ai, . . ., Г (ж, п) = а (И)

имеет по меньшей мере одно решение х.

Итак, пусть чпсла а, ai, . . ., а заданы. Будем искать числа и, Ъ такие, чтобы число ж = с {и, Ъ) удовлетво-

ряло уравнениям (И). Вследствие соотношения (10) это значит, что нам надо подобрать числа и, Ъ так, чтобы выполнялись соотношения

rest (и, i +{у + i)b) = ау (z/ = О, 1, . . ., /г),

т. е. чтобы выполнялись неравенства

1 -Ь + 1)&>а„ (I/= О, 1, . . ., «) (12)

и чтобы разности и - йу делились на 1 + (г/ + 1) Ъ. Для краткости записей введем обозначения

ту = i + {у + i) Ь. (13)

Неравенства (12), очевидно, удовлетворятся, если положить

& = (1+ « + До + • • • + апУ- (14)

Однако такой выбор значения для b гарантирует нам и то важное обстоятельство, что числа т, т, . . ., т„ будут попарно взаимно просты. В самом деле, если О i <i < 7 < re, то

mj - mi = {] - i) b (0 < 7 - i < n). Согласно (14) число b делится на 7 - i. Поэтому, если бы числа mj, mi имели какой-нибудь общий простой делитель Ps, то на Ps должно было бы делиться и число Ь. Однако из (13) видно, что mi и Ъ обпщх простых делителей не имеют. Таким образом, числа mjB.mi действительно взаимно просты.

Вводим теперь числа М, . . ., М„, полагая Mi = . . . mi-imi+x . . . от„ (i = О, 1, . . ., п).

Так как числа т, mi, . . ., 7n„ попарно взашшо просты, то числа mi и Mi также взаимно просты. Поэтому согласно известной теореме арифметики найдутся натуральные числа Zj, Wi, удовлетворяющие соотношению

MiZi - miWi = 1. (15)

Нам оставалось еще подобрать число и так, чтобы каждое число и - Оу делилось на ту. Покажем теперь, что этим требованиям заведомо удовлетворяет число

и = aoMgZo -Ь aMiZx -Ь . . . -Ь a„ikf„z„. (16)

В самом деле, все члены этой суммы делятся на mj. За исключением члена аМiZi (так как на mi делятся Mj

для ]ф i). Соотношение (15) показывает, что произведе-j ние MiZi при делении на rtii дает остаток 1. Поэтому при Делении члена aiMiZi на получится остаток а;. Посколь- j ку остальные члены суммы (16) при делении на rrii дают остаток О, то rest (и, nii) = ttj, что и требовалось.

3.4. Зависимости между операторалга примитивной рекурсии и йшнимизации. Согласно § 2 каждую функцию, примитивно рекурсивную относительно системы функций ©, можно получить из функций © и простейших функций о, S, Тт операциями подстановки и примитивной рекурсии. Однако, если исходить не только из простейших функций, а и из нумерационных функций с, I, г, то для получения иримитивнб рекурсивных относительно © функций нет необходимости пользоваться операциями примитивной рекзфсии в их обпцем виде. Достаточно применять лишь некоторый весьма специальный вид этих операций.

Аналогичное положение имеет место и для частично рекурсивных относительно © функций. Чтобы получить эти функции из функций системы © и функций о, S, Г, с, I, г, нет нужды пользоваться операциями примитивной рекурсии и минимизации в обш;ем виде, а достаточно употреблять лишь некоторые частные виды этих операций. Более детально эти вопросы будут изучены в п. 3.5 и 5.4, а пока мы докажем лишь несколько предварительных теорем.

Теорема 1. Частичная функция f {xi, . . ., Хп, у), возникающая из частичных функций g [xi, . . ., х) и h [xi, . . ., Хп, у, z) примитивной рекурсией:

f {Xi, . . ., Хп,0) g {Xi, . . ., Хп), (1)

/ {xj , . . ., Хп, у + I) = h {xj , . . ., Хп, У, f {xi, . . ., Хп, у)), может быть получена специальной рекурсией вида

Ф {х, 0) = х, ф {х, I/ -Ы) = Ф (Ф {х, у)) (2)

и подстановками из функций g, h, с, I, >, о, s, Г.

В частности, каждая функция, примитивно рекурсивная относительно системы © частичных функций, может бить получена из функций & и функций с,1, ), о, S, 1т операциями подстановки и специальными рекурсиями вида (2).

Вводим функцию

(it, у) = С"2 (t), . . . , с„„ {t), у, f (С„1 (t), С„„ (t), у)),

р . нумерационные функции, определенные в предыдущем разделе и получающиеся подстановками из фикций с, 1,г. Из соотношения (3) непосредственно следует

/ {хг, ...,Хп,у) = Сп2 п.2 (1 (с" {XI,..., X,,), у)). (4)

Первое из равенств (1) дает

,, t, 0) = С+2 (С„1 {t), Спп {t), о, g (Cnl {t), Cnn («)))•

Из (3) и (1) непосредственно следует {К У + 1) = С»- {Cnl (i),... , Спп {t), t/ + 1,

h {Cnl {t), ...,Cnn {t), y, Cn-,2 ПН 2 ( {i, y))))- (6)

Так как

Снг {t) = Cn2 i {- {t, y)), У = СП4-2 71+1 {\> {t, y)),

TO равенство (6) можно переписать в виде

{t,y + i) = 0{{t,y)), (7)

где I

ф(ы) = с"+2(с„.2 1(ы),... ,C„4.2n+l(w) + 1,

h {Сп+2 1 {и), . .., С„+2,г+2 {и))).

Итак, функция/ползгчается из функций g, h, I, г, с, о, s, Im подстановками и рекурсией

11) {х, 0) = G {X), -ф (ж, у -Ы) = Ф (я1) {х, у)). Вместо фзш:кции вводим теперь функцию ф посредством рекурсии

Ф {х, 0) = ж, ф (ж, I/ -Ы) = Ф (ф {х, у)),

имеющей требуемый вид (2). Так как

01) (ж, г/) = Ф (Ф (. . . Ф {G {х)) ...)), Ф {х, у) = Ф{Ф{. . .Ф{х) . . . )),

а) {х, у) = (p{G {х), у) и, следовате.льно, функция / получается из функций с,1, г, 1т, g, подстановками и рекурсией вида (2). Полагая в теореме I п = О, g = О, получим следующий частный случай: функция / {у), возникающая из

А тт 1\Тп-ттггоП