Войти
Десятая проблема Гильберта - десятая в списке математических задач, поставленных немецким математиком Давидом Гильбертом в 1900 году. Это задача - предоставить общий алгоритм, который для любого данного диофантова уравнения ( полиномиальное уравнение с целыми коэффициентами и конечным числом неизвестные), может определить, имеет ли уравнение решение, в котором все неизвестные принимают целочисленные значения.
Например, диофанты уравнение имеет целочисленное решение:. Напротив, диофантово уравнение не имеет такого решения.
Десятая проблема Гильберта решена, и на нее есть отрицательный ответ: такого общего алгоритма не существует. Это результат совместной работы Мартина Дэвиса, Юрия Матиясевича, Хилари Патнэм и Джулии Робинсон, которая длится 21 год, Матиясевич завершил теорему в 1970 году. Теорема теперь известна как теорема Матиясевича или теорема MRDP.
Гильберт сформулировал проблему следующим образом:
Дано диофантово уравнение с любым количеством неизвестных величин и с рациональными целыми числовыми коэффициентами: разработать процесс, согласно которому с помощью конечного числа операций можно определить, разрешимо ли уравнение в целых рациональных числах.
Слова «процесс» и «конечное число операций» означают, что Гильберт просил алгоритм. Термин «рациональное целое число» просто относится к целым числам, положительным, отрицательным или нулевым: 0, ± 1, ± 2,.... Итак, Гильберт просил разработать общий алгоритм, чтобы решить, имеет ли данное полиномиальное диофантово уравнение с целыми коэффициентами решение в целых числах.
Проблема Гильберта не связана с поиском решений. Он только спрашивает, можем ли мы вообще решить, существует ли одно или несколько решений. Ответ на этот вопрос отрицательный в том смысле, что «невозможно разработать процесс» для ответа на этот вопрос. Говоря современным языком, 10-я проблема Гильберта - неразрешимая проблема. Хотя маловероятно, что Гильберт предполагал такую возможность, прежде чем перейти к перечислению проблем, он прозорливо заметил:
Иногда бывает, что мы ищем решение при недостаточных гипотезах или в неверном смысле, и по этой причине не достигаем успеха. Тогда возникает проблема: показать невозможность решения при данных гипотезах или в предполагаемом смысле.
Доказательство неразрешимости 10-й проблемы является правильным ответом даже в терминах Гильберта, поскольку это доказательство «невозможности решения».
В диофантовом уравнении есть два типа переменных: параметры и неизвестные. Диофантово множество состоит из параметров, для которых разрешимо диофантово уравнение. Типичный пример - линейное диофантово уравнение с двумя неизвестными,
где уравнение разрешимо, когда наибольший общий делитель из водоразделов. Значения, удовлетворяющие этому ограничению, являются диофантовым множеством, а приведенное выше уравнение является его диофантовым определением.
Диофантовы определения могут быть даны как одновременными системами уравнений, так и отдельными уравнениями, поскольку система
эквивалентно единственному уравнению
Множества натуральных чисел, пар натуральных чисел (или даже n -комплектов натуральных чисел), которые имеют диофантовы определения, называются диофантовыми множествами. В этих терминах десятая проблема Гильберта спрашивает, существует ли алгоритм, чтобы определить, является ли данное диофантово множество непустым.
Работа над проблемой была в терминах решений в натуральных числах (понимаемых как неотрицательные целые числа), а не в произвольных целых числах. Эти две проблемы эквивалентны: любой общий алгоритм, который может решить, имеет ли данное диофантово уравнение целочисленное решение, может быть преобразован в алгоритм, который определяет, имеет ли данное диофантово уравнение решение в виде натурального числа, и наоборот. Это можно увидеть следующим образом: требование, чтобы решения были натуральными числами, можно выразить с помощью теоремы Лагранжа о четырех квадратах : каждое натуральное число является суммой квадратов четырех целых чисел, поэтому мы просто заменяем каждый параметр суммой квадраты четырех дополнительных параметров. Точно так же, поскольку каждое целое число может быть записано как разность двух натуральных чисел, мы можем заменить каждый параметр, который варьируется в целых числах, разностью двух параметров, которые варьируются в натуральных числах.
Перечислимое множество можно охарактеризовать как один, для которого существует такой алгоритм, который будет в конечном счете, остановить, когда член набора обеспечивается в качестве входных данных, но может продолжаться до бесконечности, когда вход не является членом. Именно развитие теории вычислимости (также известной как теория рекурсии) обеспечило точное объяснение интуитивного понятия алгоритмической вычислимости, сделав таким образом понятие рекурсивной перечислимости совершенно строгим. Очевидно, что диофантовы множества рекурсивно перечислимы. Это связано с тем, что можно расположить все возможные кортежи значений неизвестных в последовательности, а затем для данного значения параметра (ов) протестировать эти кортежи один за другим, чтобы увидеть, являются ли они решениями соответствующего уравнения. Неразрешимость десятой проблемы Гильберта является следствием того удивительного факта, что верно обратное:
Любое рекурсивно перечислимое множество диофантово.
Этот результат известен как теорема Матиясевича (потому что он обеспечил решающий шаг, завершивший доказательство) и теорема MRDP (для Юрия Матиясевича, Джулии Робинсон, Мартина Дэвиса и Хилари Патнэм ). Поскольку существует рекурсивно перечислимое множество, которое не вычислимо, неразрешимость десятой проблемы Гильберта является немедленным следствием. На самом деле можно сказать больше: существует многочлен
с целыми коэффициентами такими, что множество значений, для которых уравнение
имеет решения в натуральных числах, не вычислим. Таким образом, нет не только общего алгоритма для проверки разрешимости диофантовых уравнений, даже для этого однопараметрического семейства уравнений нет алгоритма.
| Год | События |
|---|---|
| 1944 г. | Эмиль Леон Пост заявляет, что десятая проблема Гильберта «требует доказательства неразрешимости». |
| 1949 г. | Мартин Дэвис использует метод Курта Гёделя для применения китайской теоремы об остатках в качестве уловки кодирования, чтобы получить свою нормальную форму для рекурсивно перечислимых множеств: где - многочлен с целыми коэффициентами. Чисто формально только ограниченный универсальный квантор препятствует тому, чтобы это определение было диофантовым. Используя неконструктивное, но простое доказательство, он выводит в качестве следствия этой нормальной формы, что множество диофантовых множеств не замкнуто относительно дополнения, показывая, что существует диофантово множество, дополнение которого не является диофантовым. Поскольку рекурсивно перечислимые множества также не закрываются при дополнении, он предполагает, что эти два класса идентичны. |
| 1950 | Джулия Робинсон, не зная о работе Дэвиса, исследует связь экспоненциальной функции с проблемой и пытается доказать, что EXP, набор троек для которых является диофантовым. Не добившись успеха, она выдвигает следующую гипотезу (позже названную JR):
Используя свойства уравнения Пелла, она доказывает, что из JR следует, что EXP диофантово, а также биномиальные коэффициенты, факториал и простые числа. |
| 1959 г. | Работая вместе, Дэвис и Патнэм изучают экспоненциальные диофантовы множества: множества, определяемые диофантовыми уравнениями, в которых некоторые из показателей могут быть неизвестны. Используя нормальную форму Дэвиса вместе с методами Робинсона и предполагая тогда недоказанную гипотезу о том, что существуют сколь угодно длинные арифметические прогрессии, состоящие из простых чисел, они доказывают, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым. Они также доказывают в качестве следствия, что из JR следует, что каждое рекурсивно перечислимое множество является диофантовым, что, в свою очередь, означает неразрешимость десятой проблемы Гильберта. |
| 1960 г. | Робинсон упрощает доказательство условного результата для экспоненциальных диофантовых множеств и делает его независимым от гипотезы о простых числах и, следовательно, формальной теоремы. Это делает гипотезу JR достаточным условием неразрешимости десятой проблемы Гильберта. Однако многие сомневаются в истинности JR. |
| 1961–1969 | В течение этого периода Дэвис и Патнэм находят различные предложения, которые подразумевают JR, и Робинсон, ранее показавший, что JR подразумевает, что множество простых чисел является диофантовым множеством, доказывает, что это условие тогда и только тогда, когда. Юрий Матиясевич публикует некоторые редукции десятой проблемы Гильберта. |
| 1970 г. | Основываясь на недавно опубликованной работе Николая Воробьева о числах Фибоначчи, Матиясевич доказывает, что множество, где является n- м числом Фибоначчи, является диофантовым и демонстрирует экспоненциальный рост. Это доказывает гипотезу JR, которая к тому времени оставалась открытым вопросом в течение 20 лет. Объединение JR с теоремой о том, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым, доказывает, что рекурсивно перечислимые множества диофантовы. Это делает неразрешимую десятую проблему Гильберта. |
Теорема Матиясевича / MRDP связывает два понятия - одно из теории вычислимости, другое из теории чисел - и имеет некоторые удивительные следствия. Возможно, самым удивительным является существование универсального диофантова уравнения:
Это верно просто потому, что диофантовы множества, будучи равными рекурсивно перечислимым множествам, также равны машинам Тьюринга. Хорошо известное свойство машин Тьюринга состоит в том, что существуют универсальные машины Тьюринга, способные выполнять любой алгоритм.
Хилари Патнэм указала, что для любого диофантова множества натуральных чисел существует многочлен
такой, который состоит из ровно положительных чисел среди значений, принимаемых в качестве переменных
диапазон по всем натуральным числам. Это можно увидеть следующим образом: Если
дает диофантово определение, тогда достаточно положить
Так, например, существует многочлен, положительная часть диапазона которого - это в точности простые числа. (С другой стороны, ни один многочлен не может принимать только простые значения.) То же самое верно и для других рекурсивно перечислимых наборов натуральных чисел: факториала, биномиальных коэффициентов, чисел Фибоначчи и т. Д.
Другие приложения касаются того, что логики называют предложениями, иногда также называемыми предложениями типа Гольдбаха. Это похоже на гипотезу Гольдбаха, утверждающую, что все натуральные числа обладают определенным свойством, которое алгоритмически проверяется для каждого конкретного числа. Теорема Матиясевича / MRDP означает, что каждое такое предложение эквивалентно утверждению, которое утверждает, что какое-то конкретное диофантово уравнение не имеет решений в натуральных числах. Ряд важных и знаменитых проблем имеют такую форму: в частности, Великая теорема Ферма, гипотеза Римана и теорема о четырех цветах. Кроме того, утверждение, что определенные формальные системы, такие как арифметика Пеано или ZFC, непротиворечивы, может быть выражено в виде предложений. Идея состоит в том, чтобы следовать Курту Гёделю в кодировании доказательств натуральными числами таким образом, чтобы свойство быть числом, представляющим доказательство, было алгоритмически проверяемым.
предложения обладают особым свойством: если они ложны, этот факт будет доказуем в любой из обычных формальных систем. Это потому, что ложность сводится к существованию контрпримера, который можно проверить простой арифметикой. Итак, если предложение таково, что ни оно, ни его отрицание не могут быть доказаны в одной из этих систем, это предложение должно быть истинным.
Особенно яркая форма теоремы Гёделя о неполноте также является следствием теоремы Матиясевича / MRDP:
Позволять
дать диофантово определение невычислимого множества. Позвольте быть алгоритм, который выводит последовательность натуральных чисел, такую что соответствующее уравнение
не имеет решений в натуральных числах. Тогда есть число, которое не выводится, хотя на самом деле уравнение
не имеет решений в натуральных числах.
Чтобы убедиться, что теорема верна, достаточно заметить, что, если бы такого числа не было, можно было бы алгоритмически проверить принадлежность числа к этому невычислимому набору, одновременно запустив алгоритм, чтобы увидеть, выводится ли он, а также проверив все возможные - наборы натуральных чисел, ищущие решение уравнения
Мы можем связать алгоритм с любой из обычных формальных систем, таких как арифметика Пеано или ZFC, позволяя ему систематически генерировать следствия аксиом, а затем выводить число всякий раз, когда предложение формы
генерируется. Тогда теорема говорит нам, что либо ложное утверждение такой формы доказано, либо истинное остается недоказанным в рассматриваемой системе.
Мы можем говорить о степени диофантова множества как о наименьшей степени многочлена в уравнении, определяющем это множество. Точно так же мы можем назвать размерность такого набора наименьшим количеством неизвестных в определяющем уравнении. Из-за существования универсального диофантова уравнения ясно, что существуют абсолютные верхние границы для обеих этих величин, и определение этих границ вызвало большой интерес.
Уже в 1920-х годах Торальф Сколем показал, что любое диофантово уравнение эквивалентно одному из степеней 4 или меньше. Его уловка заключалась в том, чтобы ввести новые неизвестные, задав уравнения, равные квадрату неизвестного или произведению двух неизвестных. Повторение этого процесса приводит к системе уравнений второй степени; тогда уравнение степени 4 получается суммированием квадратов. Таким образом, любое диофантово множество тривиально имеет степень 4 или меньше. Неизвестно, является ли такой результат наилучшим.
Юлия Робинсон и Юрий Матиясевич показали, что каждое диофантово множество имеет размерность не больше 13. Позже Матиясевич усовершенствовал свои методы, чтобы показать, что достаточно 9 неизвестных. Хотя вполне может быть, что это не самый лучший результат, дальнейшего прогресса нет. Так, в частности, не существует алгоритма проверки диофантовых уравнений с 9 или менее неизвестными на разрешимость в натуральных числах. В случае рациональных целочисленных решений (как первоначально сформулировал Гильберт) трюк с четырьмя квадратами показывает, что не существует алгоритма для уравнений с не более чем 36 неизвестными. Но Чжи Вэй Сунь показал, что проблема для целых чисел неразрешима даже для уравнений с не более чем 11 неизвестными.
Мартин Дэвис изучал алгоритмические вопросы, связанные с числом решений диофантова уравнения. Десятая проблема Гильберта спрашивает, является ли это число 0. Позвольте и let быть собственным непустым подмножеством. Дэвис доказал, что не существует алгоритма проверки данного диофантова уравнения, чтобы определить, является ли количество его решений членом множества. Таким образом, не существует алгоритма определения того, является ли число решений диофантова уравнения конечным, нечетным, полным квадратом, простым числом и т. Д.
Доказательство теоремы MRDP формализовано в Coq.
Александра Шлапентох (в центре) в 2003 году Хотя Гильберт поставил проблему для целых рациональных чисел, ее можно также задать для многих колец (в частности, для любого кольца, число элементов которого счетно ). Наглядные примеры - кольца целых чисел полей алгебраических чисел, а также рациональные числа.
По десятой проблеме Гильберта для колец целых чисел полей алгебраических чисел было проведено много работы. Основываясь на более ранних работах Яна Денефа и Леонарда Липшица и используя теорию полей классов, Гарольд Н. Шапиро и Александра Шлапентох смогли доказать:
Десятая проблема Гильберта неразрешима для кольца целых чисел любого поля алгебраических чисел, группа Галуа которого над рациональными числами абелева.
Шлапентох и Танас Фейдас (независимо друг от друга) получили один и тот же результат для полей алгебраических чисел, допускающих ровно одну пару комплексно сопряженных вложений.
Проблема для кольца целых чисел полей алгебраических чисел, отличных от тех, которые охвачены приведенными выше результатами, остается открытой. Точно так же, несмотря на большой интерес, проблема для уравнений над рациональными числами остается открытой. Барри Мазур предположил, что для любого многообразия рациональных чисел топологическое замыкание вещественных чисел множества решений имеет только конечное число компонент. Эта гипотеза подразумевает, что целые числа не являются диофантовыми над рациональными числами, и поэтому, если эта гипотеза верна, отрицательный ответ на Десятую проблему Гильберта потребует другого подхода, чем тот, который используется для других колец.
,
![S = \ {\, a \ mid \ exists x_ {1}, \ ldots, x_ {k} [p (a, n_ {0}, x_ {1}, \ ldots, x_ {k}) = 0] \, \}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1f9d623436e8c344911650e2fea17df2a729127)
![{\ displaystyle q (x_ {0}, x_ {1}, \ ldots, x_ {n}) = x_ {0} [1-p (x_ {0}, x_ {1}, \ ldots, x_ {n})) ^ {2}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9233a68b8b8f4414dc29d56ef48a955caa1801fc)
![{\ Displaystyle \ neg \ существует x_ {1}, \ ldots, x_ {k} [p (n, x_ {1}, \ ldots, x_ {k}) = 0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5da04caabd441b185e9d103c919907ac5565679a)
