Неразрешимость проблемы существования решения диофантова уравнения в целых числах

В 1900 году в Париже на втором Международном Конгрессе математиков выдающийся математик Давид Гильберт выступил с докладом, который назывался «Математические проблемы». Десятая из двадцати трех обозначенных в докладе проблем была сформулирована Гильбертом так:

Задача:

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

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

Определение:

Диофантово уравнение (англ. diophantine equation) имеет вид [math]P(x_1\ldots x_n)=0[/math], где [math]P[/math] — многочлен с целыми коэффициентами. [math](1)[/math]

Примеры диофантовых уравнений

Ниже приведены примеры наиболее известных частных случаев диофантовых уравнений:

• [math]x^n + y^n = z^n[/math],

• при [math]n=2[/math] решениями этого уравнения (обобщенного уравнения Пифагора) являются пифагоровы тройки,
• согласно Великой теореме Ферма это уравнение не имеет ненулевых целых решений при [math]n\gt 2[/math].

• уравнение Пелля;

[math]x^2 - n y^2 = 1[/math], где параметр [math]n[/math] не является точным квадратом;

• уравнение Каталана:

[math]x^z - y^t = 1[/math], где [math]z, t\gt 1[/math];

• уравнение Туэ:

[math]\sum_{i=0}^n a_i x^i y^{n-i} = c[/math] при [math]n \geqslant 3[/math] и [math]c\ne 0[/math].

Диофант искал решение этих уравнений в рациональных числах, Гильберт спрашивал про решение диофантовых уравнений в целых числах.

В современной терминологии десятая проблема Гильберта является примером массовой проблемы . Массовая проблема состоит из счетного количества вопросов на каждый из которых нужно дать ответ — да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.

Теорема о неразрешимости десятой проблемы Гильберта

Теорема (Неразрешимость десятой проблемы Гильберта):

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

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

Теорема:

Существует перечислимое, но неразрешимое множество натуральных чисел .

Теорема (DPRM-теорема):

Понятия «диофантово множество» и «перечислимое множество» совпадают.

Аббревиатура в названии последней теоремы образована из первых букв фамилий математиков Мартина Девиса (англ. Martin Davis), Хилари Патнэма (англ. Hilary Putnam), Джулии Робинсон (англ. Julia Robinson) и Юрия Матиясевича. Подробное доказательство неразрешимости десятой проблемы Гильберта можно прочитать здесь .

Ниже приведены основные идеи доказательства неразрешимости проблемы существования решения диофантова уравнения в целых числах.

Пусть дано множество [math]M[/math] натуральных чисел и нужно найти алгоритм, который по каждому натуральному [math]n[/math] определяет, принадлежит это [math]n[/math] множеству [math]M[/math] или нет.

В соответствии с тезисом Черча, такой алгоритм существует тогда и только тогда, когда множество [math]M[/math] разрешимо.

Для отрицательного решения десятой проблемы Гильберта достаточно доказать диофантовость каждого перечислимого множества, то есть по каждому перечислимому множеству [math]M[/math] уметь строить такое диофантово уравнение, [math]P(y,x_1\ldots x_k)=0[/math], которое имело бы натуральные решения [math]x_1\ldots x_k[/math] для всех [math]y[/math], принадлежащих [math]M[/math] и только для таких [math]y[/math].

Тогда, взяв в качестве [math]M[/math] перечислимое, но неразрешимое множество, можно было бы получить, что для соответствующего уравнения [math]P(y,x_1\ldots x_k)=0[/math] нет общего алгоритма, который по каждому натуральному [math]y[/math] давал бы ответ на вопрос о существовании у этого уравнения натуральных решений. Если бы этот алгоритм существовал, то можно было бы за конечное число шагов узнать, имеет ли уравнение [math]P(0,x_1\ldots x_k)=0[/math] решение, то есть принадлежит ли число [math]0[/math] множеству [math]M[/math], имеет ли уравнение [math]P(1,x_1\ldots x_k)=0[/math] решение и так далее. Получилось бы, что существует алгоритм, который по каждому натуральному [math]y[/math] за конечное число шагов определяет, принадлежит [math]y[/math] множеству [math]M[/math] или нет.

Тогда, в соответствии с тезисом Черча, множество [math]M[/math] было бы разрешимым вопреки выбору этого множества.

Этапы доказательства DPRM-теоремы

Гипотеза и нормальная форма Мартина Дэвиса

М. Дэвис перешёл от формулировки десятой проблемы Гильберта в целых числах к естественной для теории алгоритмов формулировке в целых неотрицательных числах. Для конкретного диофантова уравнения задача о нахождении целочисленных решений и задача о нахождении решений в целых неотрицательных числах — разные задачи. Однако если мы интересуемся сразу всеми уравнениями (как, например, в 10-й проблеме Гильберта), то эти две задачи совпадают. Действительно, если рассмотреть систему уравнений [math](2)[/math]

[math] \left\{ \begin{array}{lcr}P(x_1\ldots x_n)=0; \\ x_1=y_{1,\;1}^2+y_{1,\;2}^2+y_{1,\;3}^2+y_{1,\;4}^2;\\\ldots \\\ldots \\x_n=y_{n,\;1}^2+y_{n,\;2}^2+y_{n,\;3}^2+y_{n,\;4}^2 \end{array}\right. [/math],

то станет понятно, что:

• любое решение системы [math](2)[/math] в произвольных целых числах содержит решение уравнения [math](1)[/math] в неотрицательных целых числах;

• для любого решения уравнения [math](1)[/math] в неотрицательных целых числах [math]x_1,x_2,\ldots , x_n[/math] найдутся целочисленные значения [math]y_{1,\;1},\ldots , y_{n,\;4}[/math], дающие решение системы [math](2)[/math] , так как, согласно известной теореме Лагранжа, каждое неотрицательное целое число представимо в виде суммы квадратов четырёх целых чисел.

Система уравнений [math](2)[/math] может быть свёрнута в одно уравнение : [math]E(x_1, x_2, \ldots , x_n, y_{1,\;1}, \ldots , y_{n,\;4})[/math], разрешимое в целых числах тогда и только тогда, когда исходное уравнение [math](1)[/math] разрешимо в неотрицательных целых числах.

Утверждение:

Таким образом, массовая проблема распознавания разрешимости диофантовых уравнений в целых числах сводится к массовой проблеме распознавания разрешимости диофантовых уравнений в целых неотрицательных числах.

Наряду с отдельными диофантовыми уравнениями, Дэвис рассмотрел семейства диофантовых уравнений вида: [math]P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0[/math], где [math]P[/math] – многочлен с целыми коэффициентами, [math]a_1, a_2, \ldots , a_m\in\mathbb{Z}[/math] — параметры, [math]x_1, x_2,\ldots , x_n\in\mathbb{Z}[/math] — переменные. Каждое такое семейство определяет некоторое множество [math]M[/math] тех значений параметров, при которых уравнение разрешимо относительно переменных [math]x_1, x_2,\ldots , x_n[/math] :

[math]\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow x_1, x_2,\ldots , x_n\[/math]

[math]\left \{ P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0 \right \}[/math]

Такие множества называются диофантовыми.

Исследования Мартина Дэвиса, направленные на доказательство неразрешимости десятой проблемы Гильберта, привели его к постановке задачи, когда описано некоторое множество и требуется узнать, является ли оно диофантовым. В простейших случаях диофантовость множества очевидна — ясно, например, что диофантовым является множество всех положительных нечетных чисел. Однако совсем нелегко ответить на такие вопросы, как: «диофантово ли множество всех степеней числа [math]2[/math]?», «диофантово ли множество всех простых чисел?», «диофантово ли множество всех совершенных чисел?» С первого взгляда кажется, что на эти вопросы следует дать отрицательный ответ. Тем не менее все эти множества являются диофантовыми. Приведем примеры диофантовых множеств:

• множество всех полных квадратов, представлено уравнением [math]a-x^2=0[/math];
• множество всех составных чисел, представлено уравнением [math]a-(x_1+2)(x_2+2)=0[/math];
• множество всех нестепеней числа [math]2[/math], представлено уравнеием [math]a-(2x_1+3)x_2=0[/math].

Для доказательства неразрешимости десятой проблемы Гильберта нужно было лишь показать диофантовость любого перечислимого множества, то есть нужно показать возможность построения уравнения, которое имело бы натуральные корни [math]x_1,x_2,\ldots , x_n[/math] только при всех [math]\left \langle a_1, a_2, \ldots , a_m\right \rangle[/math], принадлежащих этому перечислимому множеству. Исходя из этого, Дэвис сформулировал следующую гипотезу:

Гипотеза (Мартина Дэвиса):

Понятия диофантового и перечислимого множества совпадают. Это значит, что множество диофантово тогда и только тогда, когда оно перечислимо.

Доказать гипотезу Дэвису не удалось, но он получил близкий к доказательству результат, показав , что любое перечислимое множество можно представить в виде, названном нормальной формой Дэвиса:

[math]\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow \exists z \quad \forall y \lt z \quad \exists x_1, x_2,\ldots , x_n\[/math]

[math]\left \{ P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0 \right \}[/math]

Предикат Робинсон. Совместный результат М. Дэвиса и Х. Патнема и Д. Робинсон.

Джулия Робинсон исследовала вопрос о том, является ли диофантовым множество, состоящее из троек :

[math]\left \langle a, b, c= a^b\right \rangle[/math]

Найти диофантово представление для операции возведения в степень ей не удалось, но она нашла достаточное условие для его существования:

[math]\left \langle a, b \right \rangle\in\mathbb{M}\Leftrightarrow \exists x_1, x_2,\ldots , x_n\[/math]

[math]\left \{ P(a, b, x_1, x_2, \ldots , x_n)=0 \right \}[/math]

Его определяет отношение [math]J(a,b)[/math] со следующими свойствами:

• для любых [math]a[/math] и [math]b[/math] из [math]J(a,b)[/math] следует, что [math]a \lt b^b[/math];
• для любого [math]k[/math] существуют [math]a[/math] и [math]b[/math], удовлетворяющие [math]J(a,b)[/math] и такие, что [math]a \gt b^k[/math].

Джулия Робинсон назвала отношения, обладающие этими двумя свойствами, отношениями экспоненциального роста; сейчас такие отношения носят также имя предикатов Джулии Робинсон.

В 1958 году М. Дэвис и Х. Патнем опубликовали работу, в которой они рассмотрели класс так называемых экспоненциально-диофантовых уравнений.Такие уравнения имеют вид:

[math]E_1(x_1,x_2,\ldots ,x_n) = E_2(x_1,x_2,\ldots ,x_n)[/math],

где [math]E_1[/math] и [math]E_2[/math] — выражения, построенные из [math]x_1, x_2,\ldots , x_m[/math] и конкретных натуральных чисел с помощью сложения, умножения и возведения в степень.

В 1961 году в совместной работе Робинсон, Дэвиса и Патмена было получено экспоненциально - диофантово представление для любого перечислимого множества:

[math]\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow \exists x_1, x_2,\ldots , x_n\[/math]

[math]\left \{E_1(a_1,a_2,\ldots ,a_m,x_1,x_2,\ldots ,x_n) = E_2(a_1,a_2,\ldots ,a_m,x_1,x_2,\ldots ,x_m)\right \}[/math]

Одним из следствий работы стала возможность сведения любого показательно-диофантова уравнения к экспоненциально-диофантову уравнению с фиксированным числом переменных. Чтобы перенести результат Дэвиса, Патнема и Робинсон на обычные диофантовы уравнения, нужно было доказать, что множество, состоящее из троек [math]\left \langle a, b, c= a^b\right \rangle[/math], является диофантовым. Тогда стало бы возможным ценой введения дополнительных неизвестных перевести экпоненциально-диофантово представление в диофантово представление: [math]a, b, c= a^b\Leftrightarrow \exists x_1,x_2,\ldots ,x_n \left \{ P(a, b,c, x_1, x_2, \ldots , x_n)=0\right \} [/math]

Джулия Робинсон показала, что для этого достаточно построить конкретное уравнение

[math]P(a, b, x_1, x_2, \ldots , x_n)=0 [/math],

• недопускающее решение с [math]a\gt b^b[/math];
• для каждого [math]k[/math] имеющее решение с [math]a\gt b^k[/math].

Вклад Ю.В. Матиясевича

Такого рода уравнение удалось построить Ю.В. Матеясевичу в 1970 году. Обратившись к рассмотрению последовательности Фибоначчи, Матиясевич заметил, что если за [math]b[/math] взять половину номера четного члена последовательности Фибоначчи, а за [math]a[/math] — сам член, то неравенство [math]a\gt b^b[/math] будет всегда неверно; для любого [math]k[/math] можно найти такой четный член последовательности, что неравенство [math]a\gt b^k[/math] будет верно. Это обстоятельство иллюстрируется приведенной ниже таблицей (в ней выделены те клетки, в которых числа [math]b^k[/math] оказываются меньше соответствующих чисел [math]a[/math]).

Номер члена последовательности Фибоначчи	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Член последовательности Фибоначчи [math]a[/math]	[math]0[/math]	[math]1[/math]	[math]1[/math]	[math]2[/math]	[math]3[/math]	[math]5[/math]	[math]8[/math]	[math]13[/math]	[math]21[/math]	[math]34[/math]	[math]55[/math]	[math]89[/math]	[math]144[/math]	[math]233[/math]	[math]377[/math]
Половина номера четного члена последовательности [math]b[/math]	[math]0[/math]		[math]1[/math]		[math]2[/math]		[math]3[/math]		[math]4[/math]		[math]5[/math]		[math]6[/math]		[math]7[/math]
[math]b^b[/math]	[math]1[/math]		[math]1[/math]		[math]4[/math]		[math]27[/math]		[math]64[/math]		[math]3125[/math]		[math]47256[/math]		[math]823649[/math]
[math]b^0[/math]	[math]1[/math]		[math]1[/math]		[math]1[/math]		[math]1[/math]		[math]1[/math]		[math]1[/math]		[math]1[/math]		[math]1[/math]
[math]b^1[/math]	[math]0[/math]		[math]1[/math]		[math]2[/math]		[math]3[/math]		[math]4[/math]		[math]5[/math]		[math]6[/math]		[math]7[/math]
[math]b^2[/math]	[math]0[/math]		[math]1[/math]		[math]4[/math]		[math]9[/math]		[math]16[/math]		[math]25[/math]		[math]36[/math]		[math]49[/math]
[math]b^3[/math]	[math]0[/math]		[math]1[/math]		[math]8[/math]		[math]27[/math]		[math]64[/math]		[math]125[/math]		[math]216[/math]		[math]343[/math]

Далее Матеясевич рассмотрел последовательность, состоящую из четных членов первоначальной последовательности. Оставалось построить уравнение, такое, что [math]P(a,b,x_1,\ldots ,x_k)=0[/math], которое имело бы натуральное решение тогда и только тогда, когда [math]b=\varphi_a[/math], далее сослаться на описанный выше результат Джулии Робинсон. Для этого достаточно было построить систему диофантовых уравнений [math]P_1=0,\ldots,P_n=0[/math] в переменных [math]a,b,x_1,\ldots ,x_k[/math], имеющую решение тогда и только тогда, когда [math]b=\varphi_a[/math]. Такая система имеет в точнсти те же решения, что и единственное уравнение [math]P_1^2+\ldots +P_n^2=0[/math]. Матиясевич получил требуемую систему в виде:

[math]1)\quad b+(z-1)=a[/math]

[math]2)\quad a+u=l[/math]

[math]3) \quad l^2-lk-k^2=1[/math]

[math]4)\quad g^2-gh-h^2=1[/math]

[math]5) \quad l^2c=g[/math]

[math]6) \quad ld=r-2[/math]

[math]7) \quad (2h+g)e=r-3[/math]

[math]8) \quad x^2-rxy+y^2=1[/math]

[math]9) \quad lp=x-b[/math]

[math]10)\quad(2h+g)q=x-a[/math]

Если возвести обе части всех этих уравнений в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система.

В результате совместной работы Дэвиса, Робинсон, Патнема, Матиясевича было доказано, что по заданию перечислимого множества в любой стандартной форме можно построить его диофантово представление:

• построить арифметическую формулу со многими ограниченными кванторами общности;
• преобразовать эту формулу в нормальную форму Дейвиса с одним ограниченным квантором общности;

• устранить этот ограниченный квантор общности ценой перехода к экспоненциально-диофантовым уравнениям;
• устранить возведение в степень.

Таким образом, была доказана правильность гипотезы Мартина Дэвиса, которая стала называться DPRM-теоремой. Из этой теоремы следует, что десятая проблема Гиль­берта является неразрешимой.

См. также

• Неразрешимость исчисления предикатов первого порядка
• Задача о выводе в полусистеме Туэ
• Задача о замощении
• Однозначность грамматики
• Неразрешимость задачи об эквивалентности КС-грамматик

Источники информации

• Матиясевич Ю.В. Десятая проблема Гильберта. — М., Физматлит, 1993 — Математическая логика и основания математики
• Проблемы Гильберта. Сборник под редакцией П.С. Александрова, М., Наука, 1969 г.
• Ю. В. Матиясевич. Диофантовы множества. — УМН, 1972, том 27, выпуск 5(167), — с. 185–222
• П. Варпаховский, А. Н. Колмогоров О решении десятой проблемы Гильберта, журнал Квант — 1970 — № 7. — С. 38—44
• Лекции Ю.В. Матиясевича в Computer Science клубе при ПОМИ РАН