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

Эта статья находится в разработке

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

Задача:

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

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

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

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

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

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

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

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

Таким образом, можно говорить об отрицательном решении десятой проблемы Гильберта.

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

Некотрые определения и теоремы

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

Множество [math]M[/math] натуральных чисел называется перечислимым, если оно совпадает со множеством значений некоторой примитивно-рекурсивной функции.

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

Множество [math]M[/math] называется разрешимым, если оно перечислимо вместе со своим дополнением [math]\mathbb N-M[/math], где [math]\mathbb N[/math] — множество всех натуральных чисел.

Теорема:

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

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

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

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

[math] \left\{ \begin{array}{lcr}P(x_1...x_n)=0; \\ x_1=y_{1,\;1}^2+y_{1,\;2}^2+y_{1,\;3}^2+y_{1,\;4}^2;\\...\\...\\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,..., x_n[/math] найдутся целочисленные значения [math]y_{1,\;1},..., y_{n,\;4}[/math], дающие решение системы [math](2)[/math] , так как, согласно известной теореме Лагранжа, каждое неотрицательное целое число представимо в виде суммы квадратов четырёх целых чисел.

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

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

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

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

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

[math]\left \{ P(a_1, a_2, ..., a_m, x_1, x_2, ..., 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,..., x_n[/math] только при всех [math]\left \langle a_1, a_2, ..., a_m\right \rangle[/math], принадлежащих этому перечислимому множеству. Исходя из этого, Дэвис сформулировал следующую гипотезу:

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

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

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

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

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

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

Основополагающий вклад в решение десятой проблемы Гильберта внесла американский математик Джулия Робинсон. Ее учитель, Альфред Тарский, предположил, что даже множество всех степеней числа [math]2[/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,..., x_n\[/math]

[math]\left \{ P(a, b, x_1, x_2, ..., 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,...,x_n) = E_2(x_1,x_2,...,x_n)[/math],

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

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

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

[math]\left \{E_1(a_1,a_2,...,a_m,x_1,x_2,...,x_n) = E_2(a_1,a_2,...,a_m,x_1,x_2,...,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,...,x_n \left \{ P(a, b,c, x_1, x_2, ..., x_n)=0\right \} [/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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