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

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

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

Задача:

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

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

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