Русская Википедия:Десятая проблема Гильберта

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Деся́тая пробле́ма Ги́льберта — одна из 23 задач, которые Давид Гильберт предложил 8 августа 1900 года на II Международном конгрессе математиков. Она состоит в нахождении универсального метода определения разрешимости произвольного алгебраического диофантова уравнения. Доказательство алгоритмической неразрешимости этой задачи заняло около двадцати лет и было завершено Юрием Матиясевичем в 1970 году[1][2].

Постановка задачи

В докладе Гильберта постановка десятой задачи самая короткая из всех: Шаблон:Начало цитаты Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах[3]. Шаблон:Oq Шаблон:Конец цитаты

Формально речь идёт о целочисленном[4] решении уравнений вида

<math>P(x_1, x_2, \ldots, x_n) = 0,</math>

где <math>P</math> — многочлен с целыми коэффициентами и целыми показателями степеней[5]. Степень уравнения равна степени многочлена <math>P</math>.

Из всех 23 задач она единственная является проблемой разрешимости[6]. По-видимому, Гильберт считал, что искомый метод существует и рано или поздно будет найден[7]. Вопроса о том, что такого метода может в принципе не быть, во времена Гильберта не стояло[8][9].

Предпосылки

Целочисленное решение алгебраических уравнений интересовало математиков ещё с античных времён. Например, много внимания уделялось уравнению <math>x^2 + y^2 = z^2</math>: если его решением был набор из натуральных чисел <math>x_0, y_0, z_0</math>, то по теореме, обратной к теореме Пифагора, из отрезков длиной <math>x_0, y_0, z_0</math> можно было получить прямоугольный треугольник[10]. Евклид привёл формулы для нахождения всех целочисленных решений этого уравнения[11]. Некоторые виды уравнений второй степени и их системы рассмотрел Диофант Александрийский[12], его работы позднее использовали Леонард Эйлер, Пьер Ферма, Жозеф Луи Лагранж, Карл Фридрих Гаусс и другие математики, занимавшиеся теорией чисел. В частности, Ферма выдвинул свою знаменитую гипотезу. К 1768 году Лагранж полностью исследовал вопрос о целочисленных решениях любого уравнения второй степени с двумя неизвестными[13].

В течение XIX века многие математики, решая Великую теорему Ферма, предпринимали попытки исследования диофантовых уравнений степени выше второй. Тем не менее проблема решения таких уравнений оставалась открытой: какого-либо общего метода получено не было, находились лишь специальные приёмы для уравнений определённых типов. Скорее всего, Гильберт подозревал, что дальнейшее исследование этой области привело бы к созданию подробных и глубоких теорий, не ограниченных диофантовыми уравнениями, и это побудило его внести задачу в список для своего доклада[8].

История решения

Поиски алгоритма

До 1940-х годов исследования по десятой проблеме велись в направлении поиска требуемого алгоритма хотя бы для некоторых классов диофантовых уравнений. Через несколько лет после доклада Гильберта, в 1908 году, Аксель Туэ показал, что уравнение Туэ для двух неизвестных не может иметь бесконечно много целочисленных решений[14]. В 1938 году Туральф Скулем опубликовал метод исследования диофантовых уравнений вида <math>P(x_1, x_2, \ldots, x_n) = 0,</math> где <math>P</math> — неполная разложимая форма (неприводимый многочлен, разлагающийся в расширении поля рациональных чисел на произведение <math>m</math> линейных множителей, <math>m>n</math>), удовлетворяющая некоторым условиям[15]. Несмотря на результат Туэ, даже уравнения с двумя неизвестными не поддавались никаким усилиям математиков (алгоритм для решения уравнений с одним неизвестным следует из теоремы Безу).

В середине 1930-х годов формализуется понятие алгоритма, а также появляются первые примеры алгоритмически неразрешимых множеств в математической логике. Важным моментом стало доказательство Андреем Марковым и Эмилем Постом (независимо друг от друга) неразрешимости задачи Туэ в 1947 году[16][17]. Это было первое доказательство неразрешимости алгебраической задачи. Оно, а также трудности, с которыми столкнулись исследователи диофантовых уравнений, вызвали предположение, что требуемого Гильбертом алгоритма не существует. Чуть ранее, в 1944 году, Эмиль Пост в одной из своих работ уже писал, что десятая проблема «молит о доказательстве неразрешимости» (Шаблон:Lang-en)[18].

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

Слова Поста вдохновили студента Мартина Дэвиса на поиск доказательства неразрешимости десятой проблемы. Дэвис перешёл от её формулировки в целых числах к более естественной для теории алгоритмов формулировке в натуральных числах[19]. Это две разные задачи, однако каждая из них сводится к другой. В 1953 году он опубликовал работу, в которой наметил путь решения десятой проблемы в натуральных числах[20].

Дэвис, наряду с классическими диофантовыми уравнениями рассмотрел их параметрическую версию:

<math>P (a_1, \ldots, a_n, x_1, \ldots, x_m) = 0,</math>

где многочлен <math>P</math> с целыми коэффициентами можно разделить на две части — параметры <math>a_1, \ldots, a_n</math> и переменные <math>x_1, \ldots, x_m.</math> При одном наборе значений параметров уравнение может иметь решение, при другом решений может не существовать. Дэвис выделил множество <math>M</math>, которое содержит все наборы значений параметров (<math>n</math>-ки), при которых уравнение имеет решение:

<math>\{ a_1, \ldots, a_n \} \in M \Longleftrightarrow \exists x_1, \ldots, x_m \colon P(a_1, \ldots, a_n, x_1, \ldots, x_m) = 0.</math>

Такую запись он назвал диофантовым представлением множества, а само множество также назвал диофантовым. Для доказательства неразрешимости десятой проблемы нужно было лишь показать диофантовость любого перечислимого множества, то есть показать возможность построения уравнения, которое имело бы натуральные корни <math>x_1, \ldots, x_m</math> только при всех <math>\{a_1, \ldots, a_n\}</math>, принадлежащих этому перечислимому множеству: поскольку среди перечислимых множеств содержатся неразрешимые, то, взяв неразрешимое множество <math>M</math> за основу, невозможно было бы получить общий метод, который бы по <math>n</math>-ке определял, имеет ли на этом наборе уравнение натуральные корни. Всё это привело Дэвиса к следующей гипотезе: Шаблон:Теорема Дэвис также сделал первый шаг — доказал, что любое перечислимое множество <math>M</math> можно представить в виде:

<math>\{ a_1, \ldots, a_n \} \in M \Longleftrightarrow \exists z \forall y<z \exists x_1, \ldots, x_m \colon P(a_1, \ldots, a_n, x_1, \ldots, x_m, y, z) = 0.</math>

Это представление получило название «нормальная форма Дэвиса». Доказать свою гипотезу, избавившись от квантора всеобщности, ему на тот момент не удалось.

Гипотеза Робинсон

Независимо от Дэвиса над десятой проблемой в те же года начала работать Джулия Робинсон. Первоначально она пыталась доказать гипотезу Альфреда Тарского о том, что множество всех степеней двойки не диофантово, но успеха не достигла[21]. После этого Робинсон перешла к исследованию вопроса о том, является ли диофантовым множество, состоящее из троек <math>\{ a, b, c = a^b \}</math>. Найти диофантово представление для операции возведения в степень ей не удалось, но тем не менее в своей работе[22] она показала достаточное условие для его существования:

<math>\{ u, v \} \in R \Longleftrightarrow \exist x_1, \ldots, x_m \colon P(u, v, x_1, \ldots, x_m) = 0,</math>

причём:

  • если <math>\{ u, v \} \in R </math>, то <math>u < v^v,</math>
  • для любого <math>k</math> существуют <math>u</math> и <math>v</math> такие, что <math>\{ u, v \} \in R </math> и <math>u > v^k.</math>

Связь между <math>u</math> и <math>v</math> Робинсон назвала «зависимостью экспоненциального роста», однако позднее эту зависимость стали называть в её честь — «зависимость Робинсон», «предикаты Робинсон» или просто «J. R.».

Объединение усилий

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

<math>E_L(x_1, \ldots, x_m) = E_R(x_1, \ldots, x_m),</math>

где <math>E_L</math> и <math>E_R</math> — экспоненциальные многочлены, то есть выражения, полученные из переменных и рациональных чисел с применением операций сложения, умножения и возведения в степень, а также показали диофантово представление для таких уравнений. Однако доказательство Дэвиса и Патнема содержало пробел — они использовали гипотезу о существовании произвольно длинных арифметических прогрессий, состоящих только из простых чисел (теорема Грина — Тао), которая была доказана только в 2004 году.

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

<math>\{ a_1, \ldots, a_n \} \in M \Longleftrightarrow \exist x_1, \ldots, x_m\colon E_L(a_1, \ldots, a_n, x_1, \ldots, x_m) = E_R(a_1, \ldots, a_n, x_1, \ldots, x_m).</math>

Одним из следствий работы стала возможность сведения любого показательно-диофантова уравнения к экспоненциально-диофантову уравнению с фиксированным числом переменных (как минимум, с тремя[25]).

Чтобы перенести результат Дэвиса, Патнема и Робинсон на «обычные» диофантовы уравнения, нужно было доказать, что множество, состоящее из троек <math>\{ a, b, c = a^b\}</math>, является диофантовым. Тогда стало бы возможным ценой введения дополнительных неизвестных перевести экспоненциально-диофантово представление в диофантово представление:

<math>c = a^b \Longleftrightarrow \exist x_1, \ldots, x_m \colon P(a, b, c, x_1, \ldots, x_m) = 0.</math>

Другими словами, для полного доказательства гипотезы Дэвиса необходимо было лишь доказать один её частный случай, а ещё точнее — доказать гипотезу Робинсон (найти многочлен <math>P(u, v, x_1, \ldots, x_m)</math>, удовлетворяющий всем условиям).

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


Влияние

  • В 2008 году состоялась премьера часового документального фильма режиссёра Джорджа Чичери (Шаблон:Lang-en) «Julia Robinson and Hilbert’s Tenth Problem». Фильм посвящён Джулии Робинсон и её вкладу в решение десятой проблемы[26]. Фильм получил отзывы и обзоры от американских математических журналов и сообществ[27][28].

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Проблемы Гильберта

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Статья
  2. ↑ Шаблон:Книга
  3. ↑ Перевод доклада Гильберта с немецкого — М. Г. Шестопал и А. В. Дорофеева, опубликован в книге Шаблон:Cite webШаблон:Cite web
  4. ↑ «Рациональное целое» является синонимом «целое», см. Шаблон:MathWorld
  5. ↑ Шаблон:Книга
  6. ↑ Шаблон:Cite web
  7. ↑ Об этом свидетельствует также сама формулировка задачи в позитивном ключе: «man soll ein Verfahren angeben» («указать порядок действий», а не, например, «указать, существует ли порядок действий»).
  8. ↑ 8,0 8,1 Шаблон:Книга Шаблон:Cite web
  9. ↑ Шаблон:Статья
  10. ↑ Шаблон:Книга
  11. ↑ Шаблон:Книга
  12. ↑ Шаблон:Cite webШаблон:Cite web
  13. ↑ Шаблон:КнигаШаблон:Ref-en
  14. ↑ Шаблон:Статья
  15. ↑ Шаблон:Книга
  16. ↑ Статья Маркова — Шаблон:Статья, см. также монографию Шаблон:Статья
  17. ↑ Результат Поста был опубликован в статье Шаблон:Статья
  18. ↑ Шаблон:Статья
  19. ↑ В американской математической традиции 0 является натуральным числом.
  20. ↑ Шаблон:Статья
  21. ↑ Шаблон:КнигаШаблон:Ref-en
  22. ↑ Шаблон:Статья
  23. ↑ Шаблон:Статья
  24. ↑ Шаблон:Статья
  25. ↑ Шаблон:Статья
  26. ↑ Шаблон:Cite web
  27. ↑ Шаблон:Статья
  28. ↑ Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Десятая_проблема_Гильберта&oldid=9717379