Десятая проблема Гильберта

Десятая проблема Гильберта — одна из 23 проблем, сформулированных немецким математиком Давидом Гильбертом в 1900 году на II Международном конгрессе математиков в Париже. Она относится к области теории чисел и состоит в нахождении общего метода, который позволял бы для любого диофантова уравнения (уравнения с целыми коэффициентами, решения которого ищутся в целых числах) определить, имеет ли оно целочисленные решения. Проблема была решена в 1970 году советским математиком Юрием Владимировичем Матиясевичем, который доказал алгоритмическую неразрешимость задачи: общего метода (алгоритма) для всех диофантовых уравнений не существует.

Формулировка проблемы

В оригинальной формулировке Гильберт поставил задачу следующим образом:

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

Ключевым словом здесь является «способ» — подразумевался единый алгоритм, применимый ко всем уравнениям, а не отдельные методы для каждого класса. Гильберт полагал, что такой алгоритм существует. Исторически проблема была связана с философским вопросом о пределах формального математического знания и с развитием теории алгоритмов.

Предыстория и ранние попытки

Диофантовы уравнения изучаются с античности. Например, уравнение Пифагора \(x^2 + y^2 = z^2\) имеет бесконечно много целочисленных решений (пифагоровы тройки), а уравнение \(x^3 + y^3 = z^3\) — не имеет ненулевых целых решений (частный случай Великой теоремы Ферма, доказанной Эндрю Уайлсом в 1994 году). Однако для каждого конкретного уравнения методы решения были уникальны. В XIX — начале XX века математики активно искали общие подходы.

Первые серьёзные попытки решения десятой проблемы относятся к 1930-м годам, когда Алонзо Чёрч и Алан Тьюринг заложили основы теории алгоритмов и доказали существование алгоритмически неразрешимых проблем. Стало понятно, что вопрос Гильберта — это вопрос существования алгоритма для распознавания разрешимости диофантовых уравнений.

История решения (ДПДУ — гипотеза Мартина Дэвиса и Хилари Патнема)

Решение проблемы было получено в несколько этапов, ключевую роль в которых сыграли американские математики Мартин Дэвис, Хилари Патнем, Джулия Робинсон и советский математик Юрий Матиясевич.

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

Основная идея решения заключалась в том, чтобы показать, что любое рекурсивно перечислимое множество (множество, которое можно сгенерировать алгоритмом) может быть задано диофантовым уравнением. Если это так, то алгоритмическая неразрешимость деся́той проблемы следует из неразрешимости проблемы остановки для машин Тьюринга.

Мартин Дэвис в 1953 году предложил гипотезу, позже известную как диофантова гипотеза Дэвиса — Патнема — Робинсон (ДПДУ). Он показал, что любое рекурсивно перечислимое множество можно представить как множество решений уравнения вида:

\[P(x, y_1, \ldots, y_n) = 0\]

где \(P\) — многочлен с целыми коэффициентами, а кванторы существования на \(y_i\) подразумеваются, но для полного контроля требуется ещё квантор «существует бесконечно много» или квантор «для некоторого \(k\) такого, что \(k\) является степенью двойки».

Роль экспоненциального роста (гипотеза Джулии Робинсон)

Джулия Робинсон в 1950-х годах активно работала над доказательством того, что функция экспоненциального роста может быть определена диофантовым уравнением. Она доказала, что если существует диофантово уравнение, задающее множество \(\{a^b\}\), то проблема будет решена. Робинсон также установила, что достаточно существования диофантового уравнения, которое задаёт множество чисел, растущих по экспоненте (например, последовательность чисел Фибоначчи или числа Мерсенна). Однако ей не удалось найти такое уравнение.

Решение Юрия Матиясевича

В 1970 году 22-летний аспирант Ленинградского университета Юрий Матиясевич совершил прорыв. Он построил явное диофантово уравнение, которое описывает рост чисел Фибоначчи, а именно — множество чисел Фибоначчи, являющихся степенями числа 2. Этот результат позволил доказать, что последовательность чисел Фибоначчи может быть определена диофантовым уравнением. Ключевой леммой стало доказательство того, что функция \(x^2\) является диофантовой относительно операции возведения в степень.

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

Фактически это означает, что не существует алгоритма, который для любого диофантова уравнения за конечное время отвечал бы «да» или «нет», имеет ли оно целочисленные решения.

Следствия и значение

Для теории чисел и математической логики

• Неразрешимость: Десятая проблема Гильберта стала первым значительным примером естественной математической проблемы, оказавшейся алгоритмически неразрешимой. Она показала границы формальных методов в арифметике.
• Связь с теоремой Гёделя: Результат Матиясевича даёт новое конструктивное доказательство первой теоремы Гёделя о неполноте для арифметики Пеано: существуют недоказуемые истинные утверждения, формулируемые в виде диофантовых уравнений.
• Новые классы уравнений: Доказательство показало, что для любого рекурсивно перечислимого множества существует соответствующее диофантово уравнение. Это привело к изучению диофантовых множеств и к построению «полинома Матиясевича» — конкретного многочлена от 9 переменных (позднее число переменных было уменьшено до 9, а степень — до порядка 25), множество целочисленных решений которого перечисляет все простые числа. Существуют варианты с 9 переменными, степенью ~ 1.6×10^45.

Для компьютерных наук

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

Обобщения (варианты проблемы)

Хотя исходная проблема решена отрицательно, существуют её варианты для других колец и полей:

• Десятая проблема Гильберта для рациональных чисел: До сих пор не решена. Неизвестно, существует ли алгоритм, определяющий, имеет ли диофантово уравнение решение в рациональных числах. В 2007 году Бьорн Пунен предположил, что ответ также отрицательный, но доказательство не найдено.
• Для кольца целых чисел алгебраических числовых полей: В значительной степени решена. Для многих числовых полей доказана неразрешимость (работы Матиясевича, Шлапентока, Корнфельдера и других). Однако для полей, которые содержат корни из единицы, ситуация может быть иной.
• Для подмножеств, заданных ограничением степени: Например, для уравнений степени 4 и выше задача в общем виде неразрешима, а для квадратных и линейных уравнений существуют эффективные методы (диофантов анализ).

Интересные факты

• Полином Матиясевича: Существует конкретный многочлен \(P(a, b, c, d, e, f, g, h, i, j)\) с 10 переменными, множество положительных целых значений которого при целых значениях переменных в точности совпадает с множеством простых чисел. Это означает, что можно «вычислить» все простые числа, подставляя все возможные целые числа в переменные: если значение больше 0, то это простое число. Однако для практического вычисления простых чисел этот метод неприменим из-за экспоненциального роста числа попыток.
• Число переменных: Первоначально у Матиясевича было уравнение с 26 переменными. Позднее число переменных удалось сократить до 9 для некоторых вариантов. Минимальное известное на сегодня число переменных для полинома, задающего простые числа, — 9.
• Признание: Юрий Матиясевич получил за своё решение премию имени А. М. Ляпунова Академии наук СССР (1970) и премию имени Дьёрдя Пойя (Society for Industrial and Applied Mathematics, 1972). Его работа была признана одним из крупнейших достижений математики XX века.

Критика и ограничения

Отрицательное решение десятой проблемы часто воспринималось некоторыми математиками как пессимистичный результат, показывающий принципиальные границы математического знания. Однако в математическом сообществе оно воспринимается скорее как обогащение теории алгоритмов и понимания сложности арифметики. Критика в основном касалась практической ценности результата: он не даёт методов для решения конкретных диофантовых уравнений, а утверждает невозможность общего метода. Для многих важных классов уравнений (например, бинарных квадратичных, однородных) существуют эффективные алгоритмы, и результат не отменяет их поиска.

Источники

• Гильберт, Д. «Математические проблемы». Доклад на II Международном конгрессе математиков. Париж, 1900.
• Матиясевич, Ю. В. «Диофантовость перечислимых множеств». Доклады Академии наук СССР, 1970, том 191, № 2, с. 279–282.
• Дэвис, М. «Лекции по десятой проблеме Гильберта». — М.: Мир, 1975.
• Роджерс, Х. «Теория рекурсивных функций и эффективная вычислимость». — М.: Мир, 1972.