342 ГЛ. VI. ВАРИАНТЫ МАШИН И АЛГОРИТМОВ

Полагая в формуле (2) г = (2 (ж + 1))*+, получим

На основании теоремы 1 и леммы 1 заключаем, что функция х1 показательно диофантова.

Л е м м а 3. Отношение между числами х, у, р, q, к, выражаемое формулой

f=(*)&p>,*.

является показательно diwфантовым.

Пусть а = p/q, а > /с. По формуле Тейлора с остаточным членом в форме Лагранжа имеем

а2+1 (1 + a-f= 2 ( " 11) a-(i + Qa-f--=

= S () a"- + eV+ia-i2«-\ (3) где 0 < Э < 1, 0 < Э < 1. Положим

и будем искать такое целое а, чтобы

S, (а) = [a+i (1 -j- а-2)«], Sj,.! (а) = [fl-i (1 + a-Yl

(4) (6)

Допустим, что а делится на qk\. Тогда 5)t (с) и (о) будут целыми числами (см. формулу (4)). С другой стороны, если а > 2~р-, то остаточные члены в формуле (3) и в аналогичной форьгуле для к - 1 будут меньше чем 1. Таким образом, формулы (5) и (6) истинны для а = = 2Рр*дЧ\. Но из (4) следует

[Pl)===a-S,(a)-aS,,{a).

Все функции, встречаюш;иеся в этой форму.ле справа от знака равенства, являются показательно диофантовыми и лемма 3 доказана.

фантювой.

Это непосредственное следствие предыдущих лемм и

формулы П {а + Ы) = (\+ Л aWy\.

Перейдем к доказательству основного результата.

Теорема 2 (Девис, Патне м, Ю. Робин с о н 111). Каждый рекурсивно перечислимый предикат пОказа/Шльно диофантов.

Достаточно рассмотреть случай, когда предикат одноместен и потому эквивалентен отношению х М, где М рекурсивно перечислимое множество чисел. Согласно теореме Девиса (п. 16.2) суш;ествует такой многочлен G (ж, г/, Z, «1, . . ., Хт) с целыми коэффициентами, что

ж е Ж 44 (Зг/) (V2 < у) (ЗЖ1 < I/). . . {ЗХт <y)(G = 0).

Поэтому остается лишь доказать, что отношение (Vz < у) {Jxi < у).. .(Эа;„ < у) {G {х, у, z,xi.....ж = 0)

показательно диофантово.

Пусть и - степень G, s - сумма абсолютных величин коэффициентов G. Полагая

Н (ж, y) = {s+ 1) (ж i- 1)" (у + 1)", будем иметь

Н {х, у) > У,

(Vz < у) (Vжl < у). . . (Vx„< у) (i G (ж, у, Z, ж1, . . ., ж„) <

<Н{х,у)).

Докажем, что имеет место эквивалентность (Vz < у) (Зж1 < у).. .(Эж„ < у) {G (ж, у, Z, Ж1, ...,£j = 0) 44{Jctat. ..aj[t = n(ж,у)\ &i-\-{i + c)t = y+i

= П {i. + it)&{i+{i+c)t)\G{x,y,c,ai,...,arr,)&

&(l-f(l + c)i ]l{ai-i)&...&{i + {i + c)t) П(ат-0.

Лемма 4. Функция ф {а, Ъ, у), определенная равен-

ством ф(а, Ь, y)=Y[{0 + bi)> является показательно дио-

Пусть для некоторых х, у правая часть этой эквивалентности истинна. Покажем, что левая часть также истинна. Рассмотрим какое-нибудь натуральное z, не пре-восходяш;ее у, и пусть рг - простое число, деляш;ее 1 -f-+ (z + i)t. Тогда, полагая

rest [aj, р,) = x,j (/ = 1, . . ., га).

достаточно показать, что

Xzj < У

G {х, у, Z, Хг, . . ., Х,т) = 0.

(8) (9)

Согласно (7) р делит П {c-j - i) я потому р, Uj - г

для подходяш;его i, О < г < у. Следовательно,

rest {aj, Рг) = rest (i, р,) у и (8) доказано.

Далее, ш {р, t) = I и t = Н {х, у)] следует р > > Н {х, у). Так как xj < г/, z < , то

I G {х, у, Z, х,1, . . ., х,т)\<Н {х, у) < р,. (10)

Но 1 + {c + i)t~0 (mod 1 -Ь (z -I- 1) t), поэтому с ~ z (mod 1 -Ь (z 4- 1) г) и с = z (mod pj). Так как

x,i Ез ai (mod p,) и {i + {i + с) t) \ G {x, y,

C, fli, . am),

G {x, y, z, xi, . . ., xm) = G {x, y, c, ai, . . ., a) =

= 0 (mod Рг),

Из (10) и (11) получаем (9).

Обратно, предположим, что для фиксированных х, у левая часть эквивалентности (7) истинна и, следовательно, для каждого Z = О, 1,. . ., i/суш;ествуют числа xi, . . . • • •, хтК У такие, что

G {х, у, Z, Х,у, . . ., Хгт) = 0.

Полагаем Н {х, у)\ =; f и определяем с из условия

i + {c + i)t=Y[{i+it).

Тогда для каждых i, / < у, 1ф /, числа i + {i + I) t и i + {j + i) t взаимно просты.

Действительно, если простое число р делит одновременно указанные числа, то р делит и (; - i) t. Но

И - / 1 < г/ <Н {х, у), t = H {X, у)\,

поэтому р делит и число t, что невозможно, так как р не может делить одновременно f и 1 -f- (г -Ь 1) it.

Итак, числа i + {i + i) t для i = О, 1, . . ., у попарно взаимно просты. Согласно известной теореме об остатках (см. п. 3.3) отсюда следует сухцествование натуральных чисел Д1, . . ., ffim, удовлетворя10ш;их сравнениям

ai ~ x,i (mod (1 + (z -Ь 1) t))

(z = О, 1, . . у, i =1, 2, . . га). (12)

Как и прежде, с = z (mod (1 -Ь (z -f- 1) t)), поэтому

G {x, у, с, at, . . ., a) = G {x, y, z, xi, . . ., x) =

= 0 (mod (1 -b (z -b 1) t))

для z = 0, . . ., y. Так как модули взаимно просты, то I + {с + i) t \ G {х, у, с, ai, . . ., am).

Аналогично, из (12) имеем

i + {z + 1) t \ ai - xi, Хг1 < у,

и потому

i + (z + i)« liii-i)

для каждого z у. Так как эти делители попарно взаимно просты, то

у+1 у

П (i + U) ПК-7)

i=0 j=0

И потому правая часть эквивалентности (7) истинна.

Для окончания доказательства теоремы остается лишь проверить, что все отношения, находящиеся в правой части эквивалентности (7), показательно дпофантовы. Показательная диофантность первых трех отношений, участ-вуюпщх в этой части, была установлена выше. Что касается остальных отношений, то они также показательно

W {Зи)(аг = у + и + l&i + {i + c)t Uiu + i + j))-

i=0

Теорема доказана. Дополнения и примеры

1. Для любого целого ш > 2 совокупность натуральных чисел, не являющихся степеняьш w, диофантова. Будет ли для какого-нибудь U) 2 совокупность всех степеней w диофантовой - пока не рещенная проблема (Ю. Робинсон [2])*).

2. Для каждого и > 1 отнощение

Р (ао, ai,.. ., а J 4Ф (Эх) (ао" +... + а х + а„ = 0)

дважды диофантово. Б частности, дважды диофантово отнощение (y)(F (х у) = 0), где F - многочлен от переменных х, у, имеющий целые коэффициенты (Тарский, см. Ю.Робинсон [2]).

3. п-я суперстепень х, символически х * п, определяется рекурсией

г. О =1, х*(п+ 1) = о;**".

Ю.Робинсон [2] показала, что если существует диофантово отношение Р {х, j), удовлетворяющее требованиям

(Bn)(Vxy){P (х,у)-*у<:х* п), (Уп)(аху)(Р (х, у)&у х"),

то отношение z = хУ диофантово.

4. В теореме 2 п. 16.2 число т не фиксировано. Р.Робинсон [2] дал другое доказательство, пз которого следует, что в упомянутой теореме можно взять m = 4, то есть что для каждого ре-jtypcHBHO перечислимого множества М существует многочлен F от семи переменных с целыми коэффициентами, для которого

хеМ (Эу) (Vz < у) (3x1 <У)...

. . . (SZi < у) {F {Х, у, Z, XI, Xi, Хз, = 0).

о. Не существует алгоритма, позволяющего для любого многочлена с целыми коэффициентами сказать, представляет ли он все натуральные числа, начиная с некоторого, или нет (И а т н е м [1]).

6. Для каждого рек5фсивпо перечпслимого лшожества М существует такой многочлен F с цельпш коэффициентами, что

X S 3f 44 (3!/ > X) (Vxi < у).. .(Vx„ < у) [F {X, у,хг,..., х) = 0).

7. 10-я проблема Гильберта неразрешима, если для каждого целого положительного к существуют а, Ъ, х, у такие, что ох -

. - Ъу= 1 и хотя бы одно из чисел х, у больше, чем (я -- Ь)* (Д е-висиПатнем 1], Девис [2]).

8. Б кольце N [t, всех многочленов от одной переменной & с целыми коэффициентами каждое рекурсивное перечислимое множество М положительных чисел диофантово. Это означает, что существует многочлен F (X, Yy, . .., У„) с коэффициентами из N {О такой, что

а е ilf ФФ (ЗГь . . Г„) {F (a,Yy, ...,YJ = 0),

где кванторы относятся к совокупности всех Гэлементов кольца iV (С) (Девис иПатнем [1]).

*) См. Приложение, с. 363.

диофантовы, так как