ПОМОЩИ преобразований вида

й.Ж-й.р.П (р,Л).

Отсюда, в частностп, следует, что все совокупности, порождаемые в регулярных снстеыах конечнылп! системами слов, являются рекурсивными.

§ 16. Диофаитовы уравнения

В 1900 г. на Международном математическом конгрессе Д. Г и л ь б е р- т [1] выделил 23 проблемы, решение которых представило бы особый интерес для развития математики.

Среди этих проблем помеш;ена и проблема № 10, сформулированная Гильбертом следу10Н];им образом:

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

Способ (Verfahren), об отыскании которого идет речь в этой проблеме, мы понимаем теперь как алгоритм. В 1900 г. теория алгоритмов еще не была создана и речь " могла идти лишь о положительном решении проблемы. Однако большие трудности, возникающие обычно при исследовании диофантовых уравнений, привели к предположению, что упомянутый алгоритм не существует. Ниже будут изложены результаты Девиса, Патне м а и Ю. Робинсон [1], показавших, что ряд арифметических проблем, близких по своему характеру 10-й проблеме Гпльберта, решается отрицательно. Что касается самой проблемы Гильберта, то она пока еще остается открытой *).

16.1. Дпофантовы предикаты и функцпп. В 10-й проблеме Гпльберта речь идет о существованнп целых рациональных решенпй, т. е. решенпй в числах О, ±1, ±2, . . . Покажем, что эта проблема равносильна проблеме сущест-вованпя решения в натуральных числах О, 1, 2, ... В самом деле, пусть для каждого уравнения

F (х, , Хг) = О, (1)

*) См. Приложение, с. 363. Из работы Ю. В. Матпясевича [1*] след5ет отрицательное решенпе десятой проблемы Гпльберта.- Црн.чеч. ред.

где F - многочлен с целыми рациональными коэффициентами, мы умеем решить вопрос, имеет оно или нет решение в натуральных числах. Спрашивается, имеет ли уравнение (1) решение в целых рациональных числах? Составляем уравнение

F {хх, . . ., Хг) F{-Xx, . . ., х„) . . . F {-Хх, . . ., -х„) = 0.

Ясно, что уравнение (1) разрешимо в целых рациональных числах когда уравнение (2) разрешимо в натуральных числах.

Обратно, пусть мы умеем решать вопрос, имеет ли произвольно заданное уравнение вида (1) решение в целых рациональных числах или нет. Спрашивается, имеет ли уравнение (1) решение в натуральных числах? Согласно общеизвестной теореме Лагранжа каждое натуральное число представимо в виде суммы квадратов четырех натуральных чисел. Поэтому уравнение (1) имеет решение в натуральных числах тогда и только тогда, когда уравнение

F (1 + 2/1 + ZI -Ь и\, . . ., х\ -Ь г/7г -f 4 -f 4) = О

имеет решение <Z] , Ух, Ux, . . ., х„, Уп, z,, ы„> в целых рациональных числах. Ввиду изложенного ниже будет рассматриваться лишь задача о существовании решений в натуральных числах и символы (Зх), (Ух), (Vxa) будут означать соответственно «существует натуральное число х», «для каждого натурального числа х», «для каждого натурального х из отрезка О, 1, 2, . . ., а».

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

Р{Хх,.. .,Жп)

(3.V1 • . Ут) (F{Xx, . . ., Х,,, Ух,..., Ут) = 0). (3)

Множество -1/ <7г-ок Хх, . . ., х„у натуральных чисел называется диофантовы.м, еслп диофантовым является 7г-.местный предикат Р, пстпнный на/г-ках пз Л/ и ложный на остальных /г-ках натуральных чпсел.

Из соотношения (3) видно, что каждое диофантово множество рекурсивно неречпслпмо. Если бы проблема Гпльберта решалась положительно, то каждое диофантово множество было бы рекурсивным. Поэтому для отрицательного решения проблемы Гильберта достаточно цока-

зать, что существуют нерекурсивные диофантовы множества. Однако пока неизвестно, существуют ли нерекурсивные диофантовы множества *).

Для краткости условимся символами ?("\ обозначать соответственно п-ки (ху, . . ., х„}, (Уи . . ., УпУ-

\ Из только что введенных определений непосредственно вытекает

Следствие 1. Если предикаты Р Q

R диофантовы, то предикаты Р (?•("))&(> (?•("),

Р V Q (?"), (Зг/1 . . . Ут) R (?("\ t)")) также диофантовы. Если F (г"-), G ((")) - многочлены с целыми коэффициентами, то предикаты S (fW), Т (f")), U {f">), определенные соотношениями

5 (?(")) = G(f(")),

Г(5(п))фф2?(5(п))-С(?(")), Г7(5("))фф(5("))<С (?(«)),

диофантовы.

В самом деле, пусть

Р (3t)("") (Я $)(")) = 0),

где Н, L - многочлены с целыми коэффициентами. Тогда Р (?(«)) &Q (gt)("V) (Я + Ь2 = 0), Р V (i-") (3?)"">5) (Я • L = 0).

Далее,

имеем

Га-("))ФФ(Зг/)((-е)2 = г/ + 1), tm44(32/)(l + J/ + i = G),

что и требовалось.

Числовая функция / {ху, . . ., а;„) называется диофан-товой, если (п -f 1)-местное отношение у = f {ху, . . . . . ., х„) диофантово. В частности, отсюда вытекает, что каждый многочлен с целыми коэффициентами является диофантовой функцией своих аргументов.

Теорема 1. Суперпозиция диофантовы функций есть функция диофантова. Если предикат Р (г) и всюду определенные функции Fy (г<")), . . ., Fn (f") диофантовы, то предикатР (Fy (?(")), . . ., F (j™)) тлкже диофантов.

*) См. Приложение, с. 355. Все рекурсивно перечислимые (в том числе нерекурсивные) множества и предикаты являются дпо-фантовыш!.- Примеч. ред.

Действительно, пусть функция F (i")) и Fi диофантовы. Так как отношение

y = F{Fy ...,Fn (?(™))

функции

для натуральных Ху, . . ., х равносильно отношению

а это последнее отношение в силу следствия 1 диофантово, то функция F (Fy, . . ., Fn) диофантова. Аналогично доказывается и второе утверждение теоремы.

Теорема 2. Функции х-у, [х/у], rest [х, у), с (х, у), I {х), г (ж), г [х, у) диофантовы.

В самом деле,

z = x -y-k{x<i,y&z = Q)\/x = z-\-y,

z = [xly] {y = 0&z = х)\/ (Зи) {x= yz + u & u<y),

{x + y) + Zx + y

rest (ж, y) = x--y-[x/y], g{x, y)--

z = I {x)4{3v) (c {z, v) == x), z = r {x) 4 {3v) (c (y, z) = x), г [x, y) = rest {I [x), i+f -f 1) r [x)).

Применяя следствие 1 и теор му 1, непосредственно убеждаемся, что стоящие справ от знака формулы представляют диофантовы преди хты.

Обозначим через совокуп сть всех степеней числа 2: А = {1, 2, 4, 8, . . .} и пусть А = Ж - А. Интересно отметить, что множество А диофантово, так как

а; е .4 44 (Зг;) [х = {2и + 3) v).

В то же время пока неизвестно, является лп диофантовым множество А. В частности, неизвестно, является ли диофантовой функция 2 (ср. Ю. Р о б и н с о п [2]). В настоящее время, по-видимому, неизвестен нп один конкретный диофантов предикат, имеющий недиофантово отрицание *), хотя очень просто доказывается (неконструктивно).

Теорема 3. Существуют диофантовы предикаты, отрицание которых недиофантово.

*) Си. Приложение, с. 363. Множество А и функция 2 диофантовы. Всякпй peKjpcHBHO перечпслшиып, нерекурсивный предпкат пмеет недиофантово отрпцанпе. -При.иеч. ред.

Допустим противное, т. е. допустим, что для каждого многочлена F [х, р) с целыми коэффициентами существует такой многочлен F* t)i) с целыми коэффициентами, что

~\m{F{h x))=o)mx){F*{i, oi)=o) (4)

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

m{F{h 5)0)4-(Vt)i)(F*(f, Х)г)фЩ. (5)

Покажем, что в таком случае каждое арифметическое мнонество (п. 13.3) будет диофантовым. Рассмотрим, например, предикат

(V«))(30(G(?, J), 0 = 0).

где G - многочлен. На основании (4), (5) имеем

(Vt))(gs)(G(?, J), S) = 0)-(Vt)h)(G*(?, «),

П(ЗШ)(е*(?, «)- h) = 0)4(3b)(G**(?, 52) = 0).

Изложенные преобразования показывают, что и в формулах с более сложными приставками вида V3, ЭУЭ и т. д. кванторы всеобщности можно ностененно заменить кванторами существования и тем самым каждый арифметический предикат представить в диофантовой виде. Мы пришли к противоречию, так как все диофаитовы предикаты рекурсивно перечислимы, а среди арифметических предикатов согласно п. 13.3 есть и не рекурсивно неречислимые.

Существует предположение, что все рекурсивно неречислимые предикаты диофаитовы *). Указанные в теореме 2 функции имеют медленный рост. Ю. Робинсон [2] показала, что еслп существует хотя бы одна диофантова фзнкцпя, растущая не медленнее 2, то важный рекурсивно перечпслпмый предикат z = ху является диофантовым.

В связи с теоремой 3 введем следующее понятие, которое будет нам полезно ниже.

Предикат Р [х-,, . . ., х,,) условпмся называть дважды диофантовым, если он сам и его отрицание дпофантовы. Соответственно этому, функцшо / [х,, .... ж,,) бдем называть дважды диофантовой, если отношенпе / [х, . . . . . ., Хп) = дважды диофантово.

Из этого онределенпя видно, что предикат Р [х,, . . . . . ., Хт) тогда и только тогда дважды дпофантов, когда стцествуют такие многочлены F, G с целыми коэффпцпен-

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

тами, что

Р{Хх, . . ., Х„)4г

4Ф (Эг/1... 2/.) {F [xi, . .., уг, . . ., у) = 0), (6) P{xi, . . ., х,„)

{Vzi...Zt){G{Xi, . . ., Хт, Zi, . . ., Zi)0). (7)

Так как дважды диофантово множество и его дополнение дпофантовы, а диофаитовы множества рекурсивно перечислимы, то каждое дважды диофантово множество рекурсивно. Верно ли обратное - неизвестно *). Теорема 3 утверждает существование диофантова множества, не являющегося дважды диофантовым. Если бы все рекурсивные множества были дважды дпофантовы, то упомянутое диофантово множество с недиофантовым дополнением было бы нерекурсивным и проблема Гильберта решалась бы отрицательно. Изложим несколько простых свойств дважды диофантовых множеств и функций.

Теорема 4. Конъюнкция, дизъюнкция и отрицание дважды диофантовых предикатов являются дважды диофантовыми предикатами. Суперпозиция дважды диофантовых всюду определенных функций есть дважды диофантова функция. Если предикат Р {х,, . . ., х) и всюду определенная функция / {х,, . . ., х„) дважды диофаитовы, то предикат Р {j {х, . . ., х„), х, . ., х) также дважды диофантов.

Докажем, например, последнее утверждение. Имеем Р{1{хг, . . ., х,п), . . ., а;,„)е=ф

{Зи){/{Хи ...,Х„,) = и&Р {и, Х.2, х,п)), (8)

Pifixi, xJ, . . . .т,„)Ф»

4Ф (Vu) (/ (Xi, ...,Хт)фи\/Р {и, Ж2, . . ., Хт)). (9)

По условию существуют такие многочлены F, G с целыми коэффициентами, что

/ {Xi, Х,п) = и&Р {и, Хо, х,„) щ-

(Зг/1. . . г/,){F{и, xi, . . ., х,; уи . . ., г/,) = 0),

f{Xi, . . ., Хт)фи\/ Р {и,

(Vzi... г,) (G {и, Хг, . . ., х, Zi, . .., z) ф 0).

Сравнивая эти эквивалентности с соответственными эквпвалентностямп (8), (9), видим, что предикат

*) Верно: всякое рекурспвное множество является дважды диофантовым. См. Приложение, с. 363.- При.иеч. ред.