Р (/ {ху, . . ., xJ, Х2, . . ., a;J представим в формах (6), (7) и, следовательно, этот предикат дважды диофантов.

Теорема 5. Каждый многочлен с целыми коэффициентами является дважды диофантовой функцией. Отношения х<.у, х = у и функции [xly], rest (ж, г/), I [х), г [х), г [х, у) дважды диофантовы.

Действительно,

2/= / (?) 2/ -/(?)= О (Vz) (z + 1 - (г/ - / Ш Ф 0),

х<у (3z) (а; + Z + 1 - г/ = 0) 44

(Vz) [х-у Z = [xly] {zy х & X < {z i) у)\/ [у = Q & Z = х), rest [х, у) = X - [xly] у, у = l{x){Jz)ic{y,z)-хО)

44 (Vzu) {с {z, и) ф х\/ Z = у), г {х, у) = rest (г (х), 1 +, (г/ + 1) г (х)).

Ясно, что если предикат Р (ху, . . ., х) дважды диофантов, то предикат (Hxi) Р [ху, . . ., a;„j) диофантов. Однако ввиду теоремы 3 последний предикат, вообще говоря, не будет дважды диофантовым.

16.2. Арифметическое представление. Уже говорилось, что существует гипотеза, согласно которой каждое рекурсивно перечислимое множество диофантово. Вопрос об истинности этой гипотезы пока открыт *). Однако можно доказать, что каждое рекурсивно перечислимое множество допускает арифметическое представление, отличающееся от диофантова лишь двумя кванторами. Это представление лежит в основе вывода ряда других представлений для рекурсивно перечислимых множеств.

Теорема1 (Девис [1]). Для каждого рекурсивно перечислимого множества М существует такой многочлен F [х, у, Z, Ху, . . ., Хп) с целыми коэффициенталш, что

<Н> (ЗУ) (Vz < у) (3X1 ...Хп) (F (х, у, Z, хг, . .., а;„) = 0), (1)

где кванторы 3, V, как и всюду, относятся к .множеству натуральные чисел.

Посмотрим сначала, что дает эта теорема для проблемы решения алгебраических уравнений в натуральных числах. Берем в качестве JJ какое-нибудь нерекурсивное ре-

*) См. сноску на с. 326.- Примеч. ред.

курсивно перечислимое множество и строим соответствующий многочлен F. Рассмотрим следующую задачу: для произвольно заданного натурального х узнать, будет ли разрешима в натуральных у, х система уравнений *)

F {х, у. О, Хо1, . . ., хоп) = О,

F [х, у, 1, Хп, . . ., хугг) = о, (2)

F (х, у, у, Xyi , . . ., Хуп) = 0.

Согласно теореме 1 разрешимость этой системы равносильна принадлежности числа х множеству М. Значит, задача о разрешимости указанной системы для произвольно заданного числа X не имеет алгоритма для своего решения.

Перейдем к доказательству теоремы 1. Рассмотрим функцию / (х), равную О для х 31 ж не определенную для X Ж. Эта функция частично рекурсивна и потому согласно теореме 2 из п. 14.3 существует операторный алгоритм, перерабатывающий 2 в 2 W и имеющий программу вида

где t,i означает одну из операций Х2, хЗ, Х5, :30. Эти операции перерабатывают число вида 2" •3-5" в число того же вида. Поэтому, начиная согласно указанной программе перерабатывать пару (2, 1), мы после п-го шага вычислений будем иметь пару вида (2"«-3«-5°«, с), где «о « - полученное число, а - но.мер приказа в

программе (3), который следует выполнить на следующем шаге.

Обозначим через Ру [и; v, w, с, и, v, w, с) предикат, истинный тогда и только тогда, когда пара (2"-3-5", с) переходит в пару (2"-3-5", с) в результате выполнения приказа с номером с из программы (3). При этом будем считать Pi (и, V, W, с, и, v, w, с) ложным для любых и ,v ,w, с, если с > п, а для с = О положим Ру пстин-ным лишь тогда, когда с = 0 и и = и, v = v, w = w.

Покажем, что предикат Ру диофантов. Для каждого i, 1 < i < п, введем предикат Pi [и, v, с; и, v, w, d),

*) Число уравненпй в этой системе, равное у -\- i, тоже является ПСКОИШ!.

равносильный утверждению

с = i & Pi {и, V, с; и, v\ w, с),

и покажем, что предикаты Р?, р1, . . ., Р1 диофаитовы. Для Р\ это очевидно, так как согласно сказанному

Р1 [и, V, W, с; и, v, w, с)

с = с = 0& u = u&v = v&w = w.

Рассмотрим Р1 для i i. В соответству101цем приказе символ t,i может иметь одно из четырех значе-

НИИ: Х2, хЗ, Х5, :30. Допустим, что упомянутый приказ имеет вид

Следовательно, если с = i и число 2"-3"-5" делится на 30, то пара (г-Зб, с) перейдет в пару (2"-i-3-i-5-i, ui). Если же указанное число не делится на 30, то упомянутая пара перейдет в пару (2"-3-5, bi). Иначе говоря, в рассматриваемом случае отношение Р] (и, v, w, с; и, v, w, с) равносильно выражению

c = i&(u>0&y>0&w>0->u=u - 1&г = = v - [&w=w - i&c = ai)& [u-v-w =

= 0->ы = u&v =v&w = w&c = bi),

эквивалентному формуле

с = i& (u-v-w ==0\/iu = u+i&v = v + i&i) = = u; + 1 & c = Ui)) &((ц>0&г;>0&1У>

yO)\/iu = u&v = v&w = w&c = bi)).

Согласно предшествующед1у пункту предикаты с = i, ц О, U = и -г 1 и т. п. дпофантовы, конъюнкции и и дизъюнкции пх также дпофантовы. Следовательно, предикат Pi дпофантов.

Допустим теперь, что рассматриваемый приказ имеет вид

В ЭТОМ случае пара (2"-3-5", с) переходит в пару (2"+1.3"-5", Ui), л-рецдкат Pi [и, V, W, с; и, v, w, с) записывается в виде

c = i&u = u + i&v = v&w = w&c = ai

и потому является диофантовым.

Случаи Сг=.хЗ, х5 рассматриваются аналогично. Поэтому можно считать, что диофантовость всех предикатов Pi доказана. Но

Pi Pi У Р\\/ ... V Pi,

поэтому предикат Pi также диофантов.

Обозначим через Р (ц, v, w, с; и, v, w, с) предикат, который при с истинен тогда и только тогда, когда пара(2"-3-5", с) переходит в пару (2«-3"-5", с) после S шагов переработки по программе (3). Вводя обозначения fi = Xi2,, Xis, хцУ и принимая во внимание смысл отношения Pi, видим, что отношение P+i (f, t)) равносильно форА1уле

(3fif2.. . f.) (Pi (f, fl) & Pi (fl, f2) & . . . & Pi (fs, ?))). (4)

Согласно основному свойству функции Гёделя Г (z, х) (и. 2.3) для любых натуральных Xij (t = О, 1, . . ., s -f 1; j = 1, 2, 3, 4) су1цествует такое a, что

Г (а, i) = с* {хц, жгз, Xis, Хц) (i = О, I, . . ., s + 1), п, следовательно,

Xij = c,j (Г (а, 0) (i = О, 1, . . ., S + 1; / = 1, 2, 3, 4), (5)

где с*, С41, С42, С43, С44- нумерационные функции, определенные в п. 3.3, причем fо = f, fs+i = t). Все эти функции являются суперпозициями функций с, I, г, диофантовость которых была установлена в предшествуюп];ем пункте. Отсюда вытекает, что функцпп cj (Г (ж, у)) также дпофантовы.

Из разрешимости системы (5) относпте.чьно а следует, что формла (4) равносп.чьна утверждению

(За) (Vi < s) (Pi {di [a, i), . . ., 4 (a, i), di [a, J + 1), . . . . . ., di [a, i 4- 1)) &xi = di{a, 0) & . . . & Xi = = d [a, 0) & 2/1 = (a, s -fl) & . . . & 2/4 =

= d, {a, s + 1)), (6)

где dj [a, i) = cj (Г (a, i)).

Условие а; 6 ж означает, что процесс переработки четверки ix, О, О, 1) обрывается на подходящем (s -\- 1)-м шаге, т. е. найдется такое s, что в получающейся на (s + 1)-м шаге четверке (г/i, у, у, г/4) имеем г/4 = 0. Иначе говоря, формула (6) дает

ж б Ж 44 (3sa) iVi < s) {Pi (di (a, i), • • •

. . 4 (a, i), ci (a, i + i), . . ., d, (a, i + !))-& x = = di (a, 0) & 0 = 2 (a, 0) & 0 = ds (a, 0) & 1 =

= d, {a, 0) & 0 = 4 (a, s + 1)}. (7)

Мы уже видели, что предикат Pi, функции {а, i) и отношения х = di [а, 0), . . ., О = d (а, s -f 1) диофантовы. Поэтому выражение, стоящее в формуле (7) внутри фигурных скобок, представляет диофантов предикат от переменных х, i, а, s. Обозначая этот предикат через Q, имеем

ж б Ж 44 ilsa) (Vi < s) (х, а, i, s). (8)

Но утверждение о существовании пары чисел s, а равносильно утверждению о существовании числа у = с {s, а), являющегося номером этой пары. Поэтому из соотношения (8) получаем

х б Ж 44 Ш (Vi < I (у)) Q {х, г (у), i, I (у)) 44

44 Ш (Vi < у) ((? (х, г (у), i, I [у)) [у)). (9)

Предикат Q {х, г (у), i, I (г/))\/> {у) диофантов и, следовательно, его можно представить в виде

(3a;i . . .Хп) {F {х, у, i, ху, . . ., х) = 0), (10)

где F - подходящий многочлен с целыми коэффициентами. Соединяя формулы (9) и (10), приходим к требуемой формуле (1).

С помощью небольших формальных преобразований (Девис [1]) из теоремы 1 легко получается

Теорема 2. Для каждого рекурсивно перечислшю-го множества Ж существует такой многочлен G с целыми коэффициентами, что

х(еМ (Зу) (Vz < у) (3X1 < г/).. .

• • • {3Xm<y){G{x,y,Z, Xi, . . .,Хп) = Щ.

Согласно теореме 1" существует многочлен F, удовлетворяющий соотношению (1), и потому утверждение х М равносильно разрешимости при некотором у системы

уравнений (2) относительно х (i = О, . . ., у; j = i, . . . . . ., п). Обозначая через и число, большее каждого числа Xij, видим, что соотношение (1) влечет

а; е Ж 44 (Зуи) (Vz < у) (Зху < и) . . . (За;„ <, и) {F = 0).

Вводя вместо пары чисел у, и ее номер v = с (у, и), приходим к заключению, что отношение х<=31 равносильно формуле

{3v){Vzl{v)){3x,r{v))...

... [ЗХп < г (V)) {F (х, I [v), Z,Xi,.. .,Хп) = 0),

которая, в свою очередь, равносильна выражению

(Эг;) (Vz < V) (Зхг < V).. . (Зх < г;) (3u;i < v) {3w2 < v) (с {wi, W2) = v& [{F[x, w:i, z, Xu . . ., x) = 0) \/

\/{Wi<Zv)]&XiW2&.. .&XnW2). (11)

Так как внутри формулы (11) < z < г; 44

44 (Зг«з < v) {3Wi v) {wi + Wa + i = z & z Wi = v), < u;„ 44 (ЗУг < v) (ж,- + = w),

"i < z < г; 44 (Згз < v) (3u4 <v) {U 0), XiW2&...&Xn< W2 44 (I yi <v){V = 0), (12)

где через (3 yiv) обозначено слово (3?/i < v) . . . • • (ЗУп v) II положено

и ={Wy + W,+ i-z) + {z + Ш4 - vf,

V ={хг+уг- W) + + {Хп + Уп- wf-

При помощи соотношений (12) формулу (И) приводим к виду

(3i)(Vz<j;)(3 Xiv){3 Ziv){3 Wi<v)

i=l i=l i=l

(4 (c {wy, uo) -vf+U [F {x, w,, z, xi, . . ., Xn) +

+ = 0)),

удовлетворяющему теореме 2.

Приведенные выше доказательства теорем 1 и 2 являются конструктивными. Это значит, что, имея программу