Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

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

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


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

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

P(x1,x2,,xn)=0,
 где P — многочлен с целыми коэффициентами и целыми показателямистепеней. Степень уравнения равна степени многочлена P.
 Из всех 23 задач она единственная является проблемой разрешимости.По-видимому, Гильберт считал, что искомый метод существует и рано илипоздно будет найден. Вопроса о том, что такого метода может в принципене быть, во времена Гильберта не стояло.

Предпосылки


 Целочисленное решение алгебраических уравнений интересовало математиковещё с античных времён. Например, много внимания уделялось уравнениюx2+y2=z2: если его решением был набор из натуральных чиселx0,y0,z0, то по теореме, обратной к теореме Пифагора, из отрезковдлиной x0,y0,z0 можно было получить прямоугольный треугольник.Евклид привёл формулы для нахождения всех целочисленных решений этогоуравнения. Некоторые виды уравнений второй степени и их системырассмотрел Диофант Александрийский, его работы позднее использовалиЛеонард Эйлер, Пьер Ферма, Жозеф Луи Лагранж, Карл Фридрих Гаусс идругие математики, занимавшиеся теорией чисел. В частности, Фермавыдвинул свою знаменитую гипотезу. К 1768 году Лагранж полностьюисследовал вопрос о целочисленных решениях любого уравнения второйстепени с двумя неизвестными.
 В течение XIX века многие математики, решая Великую теорему Ферма,предпринимали попытки исследования диофантовых уравнений степени вышевторой. Тем не менее, проблема решения таких уравнений оставаласьоткрытой: какого-либо общего метода получено не было, находились лишьспециальные приёмы для уравнений определённых типов. Скорее всего,Гильберт подозревал, что дальнейшее исследование этой области привело бык созданию подробных и глубоких теорий, не ограниченных диофантовымиуравнениями, и это побудило его внести задачу в список для своегодоклада.

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


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


 До 1940-х годов исследования по десятой проблеме велись в направлениипоиска требуемого алгоритма хотя бы для некоторых классов диофантовыхуравнений. Через несколько лет после доклада Гильберта, в 1908 году,Аксель Туэ показал, что уравнение P(x,y)=C, где C — целое число,а P — неприводимый многочлен с одинаковой степенью (3)всех членов не может иметь бесконечно много целых решений. В 1938 годуТуральф Скулем опубликовал метод исследования диофантовых уравнений видаP(x1,x2,,xn)=0, где P — неполная разложимая форма(неприводимый многочлен, разлагающийся в расширении поля рациональныхчисел на произведение m линейных множителей, m>n), удовлетворяющаянекоторым условиям. Несмотря на результат Туэ, даже уравнения с двумянеизвестными не поддавались никаким усилиям математиков (алгоритм длярешения уравнений с одним неизвестным следует из теоремы Безу).
 В середине 1930-х годов формализуется понятие алгоритма, а такжепоявляются первые примеры алгоритмически неразрешимых множеств вматематической логике. Важным моментом стало доказательство АндреемМарковым и Эмилем Постом (независимо друг от друга) неразрешимостизадачи Туэ в 1947 году. Это было первое доказательство неразрешимостиалгебраической задачи. Оно, а также трудности, с которыми столкнулисьисследователи диофантовых уравнений, вызвали предположение, чтотребуемого Гильбертом алгоритма не существует. Чуть ранее, в 1944 году,Эмиль Пост в одной из своих работ уже писал, что десятая проблема «молито доказательстве неразрешимости» .

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


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

P(a1,,an,x1,,xm)=0,
 где многочлен P с целыми коэффициентами можно разделить на двечасти — параметры a1,,an и переменные x1,,xm.При одном наборе значений параметров уравнение может иметь решение, придругом решений может не существовать. Дэвис выделил множество M,которое содержит все наборы значений параметров (n-ки), при которыхуравнение имеет решение:

ha1,,aniMx1,,xmfP(a1,,an,x1,,xm)=0g.
 Такую запись он назвал диофантовым представлением множества, а самомножество также назвал диофантовым. Для доказательства неразрешимостидесятой проблемы нужно было лишь показать диофантовость любогоперечислимого множества, то есть показать возможность построенияуравнения, которое имело бы натуральные корни x1,,xm толькопри всех ha1,,ani, принадлежащих этомуперечислимому множеству: поскольку среди перечислимых множествсодержатся неразрешимые, то, взяв неразрешимое множество M за основу,невозможно было бы получить общий метод, который бы по n-ке определял,имеет ли на этом наборе уравнение натуральные корни. Всё это привелоДэвиса к следующей гипотезе: Дэвис также сделал первый шаг — доказал,что любое перечислимое множество M можно представить в виде:

 $\mathcal {h} a_1, \ldots, a_n \mathcal {i} \in M \Longleftrightarrow \exists z \forall y Это представление получило название «нормальная форма Дэвиса». Доказатьсвою гипотезу, избавившись от квантора всеобщности, ему на тот момент неудалось.

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


 Независимо от Дэвиса над десятой проблемой в те же года начала работатьДжулия Робинсон. Первоначально она пыталась доказать гипотезу АльфредаТарского о том, что множество всех степеней двойки не диофантово, ноуспеха не достигла. После этого Робинсон перешла к исследованию вопросао том, является ли диофантовым множество, состоящее из троекha,b,c=abi. Найти диофантовопредставление для операции возведения в степень ей не удалось, но, темне менее, в своей работе она показала достаточное условие для егосуществования:

hu,viR\existx1,,xmfP(u,v,x1,,xm)=0g,
 причём:

  • если hu,viR, то u<vv,
  • для любого k существуют u и v такие, что hu,viR и u>vk.

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

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


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

EL(x1,,xm)=ER(x1,,xm),
 где EL и ER — экспоненциальные многочлены, то есть выражения,полученные из переменных и рациональных чисел с применением операцийсложения, умножения и возведения в степень, а также показали диофантовопредставление для таких уравнений. Однако доказательство Дэвиса иПатнема содержало пробел — они использовали гипотезу о существованиипроизвольно длинных арифметических прогрессий, состоящих только изпростых чисел (теорема Грина — Тао), которая была доказана только в2004 году.
 В 1961 году этот пробел смогла восполнить Джулия Робинсон. В ихсовместной работе было получено экспоненциально-диофантово представлениедля любого перечислимого множества:

ha1,,aniM\existx1,,xmEL(a1,,an,x1,,xm)=ER(a1,,an,x1,,xm).
 Одним из следствий работы стала возможность сведения любогопоказательно-диофантова уравнения к экспоненциально-диофантову уравнениюс фиксированным числом переменных (как минимум, с тремя).
 Чтобы перенести результат Дэвиса, Патнема и Робинсон на «обычные»диофантовы уравнения, нужно было доказать, что множество, состоящее изтроек ha,b,c=abi, является диофантовым.Тогда стало бы возможным ценой введения дополнительных неизвестныхперевести экспоненциально-диофантово представление в диофантовопредставление:

a,b,c=ab\existx1,,xmfP(a,b,c,x1,,xm)=0g.
 Другими словами, для полного доказательства гипотезы Дэвиса необходимобыло лишь доказать один её частный случай, а ещё точнее — доказатьгипотезу Робинсон (найти многочлен P(u,v,x1,,xm),удовлетворяющий всем условиям).
 Несмотря на глубокое изучение двухпараметрических диофантовых уравненийсо времён самого Диофанта, на тот момент не было известно уравнения,выражающего зависимость экспоненциального роста. Попытки егоискусственно сконструировать также потерпели неудачу.

Влияние



  • В 2008 году состоялась премьера часового документального фильма режиссёра Джорджа Чичери «Julia Robinson and Hilbert's Tenth Problem». Фильм посвящён Джулии Робинсон и её вкладу в решение десятой проблемы. Фильм получил отзывы и обзоры от американских математических журналов и сообществ.