операторного алгоритма, вычисляющего частичную характеристическую функцию / (х) множества 31, мы в принципе можем написать многочлены F ш G, удовлетворяющие требованиям теорем 1, 2. Однако эта возможность лишь принципиальная, так как если взять какую-нибудь из ныне известных программ, отвечающих нерекурсивным множествам 3/, и построить многочлены F, G но правилам, изложенным в доказательствах теорем 1, 2, то такие многочлены окажутся слишком сложными. Задача о нахождении более или менее простых многочленов (например, невысокой степени и с небольшим числом переменных), дающих нерекурсивное множество 3£, до сих нор, по-видимому, не решена.

16.3. Представимость натуральных чисел многочленами. Говорят, что число а представимо многочленом F (xi, . . .,Xni), если существуют такие натуральные числа й], . . ., а, что F (ai, . . ., Um) = а, т. е. если истинна формула

[3X1

Хт) [Р [Xl,

п) = а)-

Говорят, что совокупность натуральных чисел 31 представляется многочленом F, если 31 есть совокупность всех тех натуральных чисел, которые представимымногочленом F. В теории чисел для ряда многочленов F исследовался вопрос о том, представимы ли этим многочленом все натуральные числа. Например, теорема Лагранжа, которой мы уле пользовались, утверждает, что многочлен xl -j- xl ~\- xl + xl представляет каждое натуральное число. Естественно возникает вопрос: нельзя ли указать алгоритм, посредством которого для любого заданного многочлена с целыми коэффициентами можно было бы сказать, представляет п.чи нет этот многочлен все натуральные чпсла. Следуя П а т и е м у [1], покажем, что этот вопрос решается отрицательно. Сначала докажем следующую теорему:

Теорема 1 (П а т н е м [1]). Для каждого рекурсивно пвречислшюго множества 31 существует такой мно-гоч.1ен F {х, у, zi, . . ., z) с целыми коэффициентами, что

Х= 31 ФФ (Згу) (Y21. . . 2„) {F (Х, 7/, Z1, . . ., 2,0 Ф 0). (1)

Согласно теореме Девпса (п. 16.2) можно найтп такой многочлен G (х, у, z, Хх, . . ., Хт) с целыми коэффицпен-

тами, ЧТО

а: е Ж" (Эг/) (Vz < !/) (Зхъ . . x„,){G{x,y, z, xi, . . .,Хт)=0).

При заданных г/ и z г/ обозначим через xi натуральные числа, удовлетворяющие согласно (2) уравнению

G {х, у, Z, х,1, . . ., arm) = 0. По основному свойству функции Геделя Г (а, t) системы

Г (а;, z) = xi (z = О, 1, . . ., у) имеют натуральные решения ui, . . ., а з. потому ж е Ж <Н> (Эг/ai. . .aJ (Vz < у)

{G {х, у, Z, Г {аи z), . . ., Г (а,„, z)) = 0}

x3f<{3yai...am){Vz)

{Z > 2/ V G (а;, г/, Z, Г (ai, 2),. . ., Г (а,„, zj) = 0}. (3)

Согласно теоремам 4, 5 и. 16.1 выражение, стоящее в фигурных скобках, представляет дваяеды диофантов предикат и потому равносильно формуле впда

(Vzi . . . Zs-i) {Н{х, у, ffli, . . ., am, z, zi, . . ., г-х)Ф 0), (4)

где Н ~ многочлен с целыми коэффициентами. Подставляя (4) в (3), получим

X е Ж 44 {Зуаг. . .а,„) (Vzi. . .z,)

(Я {х, у, ai, . .., Um, 2i,. . ., г)Ф 0).

Вводя вместо строки <г/, ai, . . ., а} ее номер и = = с (у, аг, . . ., am), будем иметь

x3I-{3u){Wzx. . .fc,)

{Я [Х, Cmii{u), Cm+1 m+1 [и), Zi, . . ., Zj) ф 0}.

Предикат, стоящий в фигурных скобках, дважды диофантов и потому может быть заменен выражением вида

(Vzj+i . . . zJ {F {х, и, zi, . . ., z„ Zs+i, . . ., z„) Ф 0),

где F - П0ДХ0ДЯПЩЙ лшогочлен с целыми коэффициентами. После указанной замены формула приобретает требуемый вид (1).

Теорема 2. Для каждого рекурсивно 7геречислимого множества 31 существует такой многочлен с целыми

12 А. и. Мальцев

Следствие. Не существует алгоритма, позволяющего для любого заданного многочлена с целыми коэффициентами уэнатъ, представляет этот многочлен все натуральные числа или нет.

В самом деле, берем какое-нибудь нерекурсивное рекурсивно перечпслимое множество М и строим для него многочлен G, удовлетворяющий условию (5). Берем некоторое число а и рассматриваем многочлен G [а, zi, . . ., z„) от переменных Zi, . . ., z„. Формула (5) означает, что а (f М тогда и только тогда, когда многочлен G [а, Zi, . . . . . ., z„) представляет все натуральные числа. Если бы упомянутый алгоритм существовал, то при его помощи мы бы могли решать и вопросы о вхождении числа в Ж,-что противоречит нерекурсивности множества М.

16.4, Показательные уравнения. Показательными урав-нения.ии называются уравнения вида

F{xy, . . .,Хп,х1\хС , . . .,а;) = О, (1)

тле F (хг, . . ., х„, хгг, Хг2, , - некоторый многочлен от переменных Xi, Xjj (г, / = 1, . . ., n) с целыми рациональными коэффициентами. При этом полагают, что ж" = 1 для всех целых х, в частности. О" = 1. Обычно ищут натуральные решения уравнения (1). Типичными примерами показательных уравнений могут служить уравнения

туУ = z (2 - х) -Ь {хУ - г/)2 = О, 2 + П« = 5

уже рассматривавшиеся в литературе.

Из определения видно, что каждое диофантово уравнение является показательным. Выше отмечалось, что проблема существования алгоритма для ответа на вопрос о разрешимости произвольно заданного диофантова уравнения пока остается открытой *). Для показательных уравнений положение иное. Сравнительно недавно Девис, Патне м и Ю. Робинсон [1] показали, что проблема разрешимости в натуральных числах произвольно заданного показательного зравнения алгоритмически неразрешима. Ниже приводится доказательство этой замечательной теоремы, принадлежащее тхомянутым авторам.

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

См. Приложение, с. 363 п сноску на с. 324.

коэффициентами G (х, Zi, . . ., z„), что

хМ {Vy) (3zi. . .z J (G{x,zu..„ z,n) = (5)

Сначала согласно теореме 1 найдем такой многочлен F, чтобы

хМ (Зу) (Vzi.. .z„){F{X, у, zu ..., z„) ф0),

и, следовательно,

хМ4 (Уу) Ozi.. .z„){F{X, у, zi,.. z„) = 0).

Теорема 2, очевидно, будет доказана если будет доказана следующая формула Патнема:

(3h) {F {х, у, J) = 0) 44

Osi . . . Ui) {G {х, ui, и, Ug, Ui, i) = y), (6)

где 5 = <zi, . . ., z„> и G(a:,Mi, ...,U4,5)=

= (1 - {X, 4+ ul + ul+ ul s)) {ul + ul -f 4 -{-1) 1.

IIjfCTb для некоторых натуральных x, у левая часть эквивалентности (6) истинна и, следовательно, F{x, у, j) = = О для подходящих 5,. По теореме Лагранжа найдутся такие натуральные щ, щ, и, Ui, что y = i4 + "2 + "3 +

ul. Из (7) получаем G (х, иг, . . ., Ui, i) = (1 - Я {х, у, i)){l+y)-iy

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

Обратно, пусть для некоторых натуральных х, у правая часть эквивалентности (6) истинна и, следовательно,

(1 - F {X, ul-hul + ul -f ul 0) (ul +4 + ul + u\-b

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

F{x,uli?.u\vi,) = ,

и тогда из (8) дополнительно получаем -Ь "1 + + -\- иХ = у, откуда F (х, у, j) = О, что и требовалось.

l) (3= + l)!/- 2 3<2!.

Мы хотим, следуя Девису, Патнему и Робинсон, доказать, что показательно диофантовыми являются все частично рекурсивные фзнкции и рекурсивно перечислимые предикаты.

Лемма 1 (Ю. Робинсон [2]). Функция

Д(П - 1). . . (П-fe-L 1)

~ А;!

от переменных п, к показательно диофантова.

Пусть О < /с < п, тогда

Следовательно,

[2"=(1Ч-2-Т]=2(-)2"Л

ще [х] - наибольшее целое число, не превосходящее х.

При тех же предположениях О < /с < /г аналогичным путем получаем формулу

2" [2"("-« (1 + 2-")"] = S ( • ) 2""

. i=0

и, следовательно,

j = [2" (1 + 2-")"] - 2" [2"" (1 -f 2-")"]. (1)

Из справедливости формулы (1) для О <. к п вытекает, что для произвольных к, п имеет место эквивалентность

y = {ljin<:k&k>0&y = 0)\/{k = 0&y = l)\/

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

Лемма 2 (Ю. Робинсон [2]). Функция у = х\ показательно диофантова.

Докажем формулу

г>(2а:Га:!=[г()]. (2)

При X = О эта формула очевидна. Пусть а; > 0. Тогда

1/(1 е)<14-2е для о<е<4, (1 +е)< 1 + 2=9 для о<е<1,

.,<.>/(:)=7(-т)(-т)-(-)<

Xi, (jj 7 = 1, . . ., n) с целыми коэффициентами, что Р {хи .. ., а; j 4

ЩЗхтх.. .Хп) (F {хи .. ., Хп, х1\ х1\ ..., ж» = 0).

Числовая фунйция f {xi, . . ., х) называется показательно диофантовой, если отношение / {xi, . . ., х) = = Хт+1 показательно диофантово.

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

Теорема 1. Если предикаты Р [x-i, . . ., х),

Q {Xi, . . ., Хп) и фyнкЦUUf {Хх, . . ., Хп), gl (Xi, . . ., Х,п), •

gn [xi, . . ., Хт) показательно диофаитовы, то функция

f (gl (Xi, . . ., Хт), . . ., gn {Xl, . . ., Хт))

и предикаты

Р (Xi, . . ., Хп)\/ Q (xi, . . ., Хп), Р [xi, . . Xn)&Q [xi, . . :, Хп), (Зхп) Р [хи , Хп),

Хт), • • gn

{Хи . . ., Хт)), gl {Xi, . . ., Хт) = gz {Xi, . . ., Хт), gl {Xi, . . ., Хт) < 2 {Xl, . . .,Xm).

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

Доказательство такое же, как и доказательство соответствующей теоремы о диофантовых функциях и предикатах в п. 16.1.

Из теоремы 1, например, вытекает, что показательно диофантовыми являются следующие функции и отношения: