Десятая проблема Гильберта - десятая в списке математических задач , поставленных немецким математиком Давидом Гильбертом в 1900 году. Это задача - предоставить общий алгоритм, который для любого данного диофантова уравнения ( полиномиальное уравнение с целыми коэффициентами и конечным числом неизвестные), может определить, имеет ли уравнение решение, в котором все неизвестные принимают целочисленные значения.
Например, диофантово уравнение имеет целочисленное решение: . Напротив, диофантово уравнение такого решения нет.
Десятая проблема Гильберта решена, и на нее есть отрицательный ответ: такого общего алгоритма не существует. Это результат совместной работы Мартина Дэвиса , Юрия Матиясевича , Хилари Патнэм и Джулии Робинсон, которая длится 21 год, Матиясевич завершил теорему в 1970 году. [1] Теорема теперь известна как теорема Матиясевича или теорема MRDP.
Задний план
Оригинальная рецептура
Гильберт сформулировал проблему следующим образом: [2]
Дано диофантово уравнение с любым числом неизвестных величин и с рациональными целыми числовыми коэффициентами: разработать процесс, согласно которому с помощью конечного числа операций можно определить, разрешимо ли уравнение в целых рациональных числах.
Слова «процесс» и «конечное число операций» означают, что Гильберт просил алгоритм . Термин «рациональное целое число» просто относится к целым числам, положительным, отрицательным или нулевым: 0, ± 1, ± 2, .... Итак, Гильберт просил разработать общий алгоритм, чтобы решить, имеет ли данное полиномиальное диофантово уравнение с целыми коэффициентами решение в целых числах.
Проблема Гильберта не связана с поиском решений. Он только спрашивает, можем ли мы вообще решить, существует ли одно или несколько решений. Ответ на этот вопрос отрицательный в том смысле, что «невозможно разработать процесс» для ответа на этот вопрос. Говоря современным языком, 10-я проблема Гильберта - неразрешимая проблема . Хотя маловероятно, что Гильберт предполагал такую возможность, прежде чем перейти к перечислению проблем, он прозорливо заметил: [3]
Иногда бывает, что мы ищем решение при недостаточных гипотезах или в неверном смысле, и по этой причине не достигаем успеха. Тогда возникает проблема: показать невозможность решения при данных гипотезах или в предполагаемом смысле.
Доказательство неразрешимости 10-й проблемы является правильным ответом даже в терминах Гильберта, поскольку это доказательство «невозможности решения».
Диофантовы множества
В диофантовом уравнении есть два типа переменных: параметры и неизвестные. Диофантово множество состоит из параметров, для которых разрешимо диофантово уравнение. Типичный пример - линейное диофантово уравнение с двумя неизвестными,
- ,
где уравнение разрешимо , когда наибольший общий делитель из разделяет . Значения для которые удовлетворяют этому ограничению, являются диофантовым множеством, а приведенное выше уравнение является его диофантовым определением.
Диофантовы определения могут быть даны как одновременными системами уравнений, так и отдельными уравнениями, поскольку система
эквивалентно единственному уравнению
Множества натуральных чисел, пар натуральных чисел (или даже n -комплектов натуральных чисел), которые имеют диофантовы определения, называются диофантовыми множествами . В этих терминах десятая проблема Гильберта спрашивает, существует ли алгоритм, чтобы определить, является ли данное диофантово множество непустым.
Работа над проблемой была в терминах решений в натуральных числах (понимаемых как неотрицательные целые числа), а не в произвольных целых числах. Эти две проблемы эквивалентны: любой общий алгоритм, который может решить, имеет ли данное диофантово уравнение целочисленное решение, может быть преобразован в алгоритм, который определяет, имеет ли данное диофантово уравнение решение в виде натурального числа, и наоборот. Это можно увидеть следующим образом: требование, чтобы решения были натуральными числами, можно выразить с помощью теоремы Лагранжа о четырех квадратах : каждое натуральное число является суммой квадратов четырех целых чисел, поэтому мы просто заменяем каждый параметр суммой квадраты четырех дополнительных параметров. Точно так же, поскольку каждое целое число можно записать как разность двух натуральных чисел, мы можем заменить каждый параметр, который варьируется в целых числах, разностью двух параметров, которые варьируются в натуральных числах. [4]
Рекурсивно перечислимые множества
Перечислимое множество можно охарактеризовать как один , для которого существует такой алгоритм , который будет в конечном счете , остановить , когда член набора обеспечивается в качестве входных данных, но может продолжаться до бесконечности , когда вход не является членом. Именно развитие теории вычислимости (также известной как теория рекурсии) обеспечило точное объяснение интуитивного понятия алгоритмической вычислимости, сделав таким образом понятие рекурсивной перечислимости совершенно строгим. Очевидно, что диофантовы множества рекурсивно перечислимы. Это связано с тем, что можно расположить все возможные кортежи значений неизвестных в последовательности, а затем для данного значения параметра (ов) протестировать эти кортежи один за другим, чтобы увидеть, являются ли они решениями соответствующего уравнения. Неразрешимость десятой проблемы Гильберта является следствием того удивительного факта, что верно обратное:
Любое рекурсивно перечислимое множество диофантово.
Этот результат известен как теорема Матиясевича (потому что он обеспечил решающий шаг, завершивший доказательство) и теорема MRDP (для Юрия Матиясевича , Джулии Робинсон , Мартина Дэвиса и Хилари Патнэм ). Поскольку существует рекурсивно перечислимое множество, которое не вычислимо, неразрешимость десятой проблемы Гильберта является немедленным следствием. На самом деле можно сказать больше: существует многочлен
с целыми коэффициентами такими, что множество значений для которого уравнение
имеет решения в натуральных числах, не вычислим. Таким образом, нет не только общего алгоритма для проверки разрешимости диофантовых уравнений, даже для этого однопараметрического семейства уравнений, нет никакого алгоритма.
История
Год | События |
---|---|
1944 г. | Эмиль Леон Пост заявляет, что десятая проблема Гильберта «требует доказательства неразрешимости». |
1949 г. | Мартин Дэвис использует метод Курта Гёделя для применения китайской теоремы об остатках в качестве уловки кодирования, чтобы получить свою нормальную форму для рекурсивно перечислимых множеств: где - многочлен с целыми коэффициентами. Чисто формально только ограниченный универсальный квантор препятствует тому, чтобы это определение было диофантовым. Используя неконструктивное, но простое доказательство, он выводит в качестве следствия этой нормальной формы, что множество диофантовых множеств не замкнуто относительно дополнения, показывая, что существует диофантово множество, дополнение которого не является диофантовым. Поскольку рекурсивно перечислимые множества также не закрываются при дополнении, он предполагает, что эти два класса идентичны. |
1950 | Джулия Робинсон , не зная о работе Дэвиса, исследует связь экспоненциальной функции с проблемой и пытается доказать, что EXP, набор троек для которого , является диофантовым. Не добившись успеха, она выдвигает следующую гипотезу (позже названную JR):
Используя свойства уравнения Пелла, она доказывает, что из JR следует, что EXP диофантово, а также биномиальные коэффициенты, факториал и простые числа. |
1959 г. | Работая вместе, Дэвис и Патнэм изучают экспоненциальные диофантовы множества : множества, определяемые диофантовыми уравнениями, в которых некоторые из показателей могут быть неизвестны. Используя нормальную форму Дэвиса вместе с методами Робинсона и предполагая тогда недоказанную гипотезу о том, что существуют сколь угодно длинные арифметические прогрессии, состоящие из простых чисел , они доказывают, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым. Они также доказывают в качестве следствия, что из JR следует, что каждое рекурсивно перечислимое множество является диофантовым, что, в свою очередь, означает неразрешимость десятой проблемы Гильберта. |
1960 г. | Робинсон упрощает доказательство условного результата для экспоненциальных диофантовых множеств и делает его независимым от гипотезы о простых числах и, следовательно, формальной теоремы. Это делает гипотезу JR достаточным условием неразрешимости десятой проблемы Гильберта. Однако многие сомневаются в истинности JR. [5] |
1961–1969 | В течение этого периода Дэвис и Патнэм находят различные предложения, которые подразумевают JR, и Робинсон, ранее показавший, что JR подразумевает, что множество простых чисел является диофантовым множеством, доказывает, что это условие тогда и только тогда, когда . Юрий Матиясевич публикует некоторые редукции десятой проблемы Гильберта. |
1970 г. | На основе недавно опубликованной работы Николая Воробьева о числах Фибоначчи [6] Матиясевич доказывает, что множество где является n- м числом Фибоначчи , является диофантовым и демонстрирует экспоненциальный рост. [7] Это доказывает гипотезу JR, которая к тому времени оставалась открытым вопросом в течение 20 лет. Объединение JR с теоремой о том, что каждое рекурсивно перечислимое множество является экспоненциально диофантовым, доказывает, что рекурсивно перечислимые множества диофантовы. Это делает неразрешимую десятую проблему Гильберта. |
Приложения
Теорема Матиясевича / MRDP связывает два понятия - одно из теории вычислимости, другое из теории чисел - и имеет некоторые удивительные следствия. Возможно, самым удивительным является существование универсального диофантова уравнения:
- Существует многочлентакое, что для любого диофантова множестваесть номертакой, что
Это верно просто потому, что диофантовы множества, будучи равными рекурсивно перечислимым множествам, также равны машинам Тьюринга . Хорошо известное свойство машин Тьюринга состоит в том, что существуют универсальные машины Тьюринга, способные выполнять любой алгоритм.
Хилари Патнэм отметила, что для любого диофантова множества натуральных чисел, существует многочлен
такой, что состоит в точности из положительных чисел среди значений, принимаемых как переменные
диапазон по всем натуральным числам. Это можно увидеть следующим образом: Если
дает диофантово определение , то достаточно положить
Так, например, существует многочлен, положительная часть диапазона которого - это в точности простые числа. (С другой стороны, ни один многочлен не может принимать только простые значения.) То же самое верно и для других рекурсивно перечислимых наборов натуральных чисел: факториала, биномиальных коэффициентов, чисел Фибоначчи и т. Д.
Другие приложения касаются того, что логики называют предложения, иногда также называемые предложениями типа Гольдбаха . [8] Это похоже на гипотезу Гольдбаха , утверждающую, что все натуральные числа обладают определенным свойством, которое алгоритмически проверяется для каждого конкретного числа. [9] Теорема Матиясевича / MRDP означает, что каждое такое предложение эквивалентно утверждению, что какое-то конкретное диофантово уравнение не имеет решений в натуральных числах. [10] Ряд важных и знаменитых проблем имеют такую форму: в частности, Великая теорема Ферма , гипотеза Римана и теорема о четырех цветах . Кроме того, утверждение, что определенные формальные системы, такие как арифметика Пеано или ZFC , непротиворечивы, может быть выражено какпредложения. Идея состоит в том, чтобы следовать Курту Гёделю в кодировании доказательств натуральными числами таким образом, чтобы свойство быть числом, представляющим доказательство, было алгоритмически проверяемым.
предложения обладают особым свойством: если они ложны, этот факт будет доказуем в любой из обычных формальных систем. Это потому, что ложность сводится к существованию контрпримера, который можно проверить простой арифметикой. Так что еслипредложение таково, что ни оно, ни его отрицание не могут быть доказаны ни в одной из этих систем, это предложение должно быть истинным. [ необходима цитата ]
Особенно яркая форма теоремы Гёделя о неполноте также является следствием теоремы Матиясевича / MRDP:
Позволять
дать диофантово определение невычислимого множества. Позволять быть алгоритмом, который выводит последовательность натуральных чисел такое, что соответствующее уравнение
не имеет решений в натуральных числах. Тогда есть номер который не выводится в то время как на самом деле уравнение
не имеет решений в натуральных числах.
Чтобы убедиться в истинности теоремы, достаточно заметить, что если бы такого числа не было , можно было бы алгоритмически проверить принадлежность числа в этом невычислимом множестве путем одновременного запуска алгоритма чтобы увидеть, есть ли выводится, а также проверяет все возможные -наборы натуральных чисел, ищущие решение уравнения
Мы можем связать алгоритм с любой из обычных формальных систем, таких как арифметика Пеано или ZFC , позволяя ей систематически генерировать следствия аксиом, а затем выводить число всякий раз, когда предложение формы
генерируется. Тогда теорема говорит нам, что либо ложное утверждение такой формы доказано, либо истинное остается недоказанным в рассматриваемой системе.
Дальнейшие результаты
Мы можем говорить о степени диофантова множества как о наименьшей степени многочлена в уравнении, определяющем это множество. Точно так же мы можем назвать размерность такого набора наименьшим количеством неизвестных в определяющем уравнении. Из-за существования универсального диофантова уравнения ясно, что существуют абсолютные верхние границы для обеих этих величин, и определение этих границ вызвало большой интерес.
Уже в 1920-х годах Торальф Сколем показал, что любое диофантово уравнение эквивалентно одному из степеней 4 или меньше. Его уловка заключалась в том, чтобы ввести новые неизвестные, задав уравнения, равные квадрату неизвестного или произведению двух неизвестных. Повторение этого процесса приводит к системе уравнений второй степени; тогда уравнение степени 4 получается суммированием квадратов. Таким образом, любое диофантово множество тривиально имеет степень 4 или меньше. Неизвестно, насколько возможен такой результат.
Юлия Робинсон и Юрий Матиясевич показали, что каждое диофантово множество имеет размерность не больше 13. Позже Матиясевич усовершенствовал свои методы, чтобы показать, что достаточно 9 неизвестных. Хотя вполне может быть, что это не самый лучший результат, дальнейшего прогресса нет. [11] Так, в частности, не существует алгоритма проверки диофантовых уравнений с 9 или менее неизвестными на разрешимость в натуральных числах. В случае рациональных целочисленных решений (как первоначально сформулировал Гильберт) трюк с четырьмя квадратами показывает, что не существует алгоритма для уравнений с не более чем 36 неизвестными. Но Чжи Вэй Сунь показал, что задача для целых чисел неразрешима даже для уравнений с не более чем 11 неизвестными.
Мартин Дэвис изучал алгоритмические вопросы, связанные с числом решений диофантова уравнения. Десятая проблема Гильберта спрашивает, равно ли это число 0. Пусть и разреши быть собственным непустым подмножеством . Дэвис доказал, что не существует алгоритма проверки данного диофантова уравнения, чтобы определить, является ли количество его решений членом множества.. Таким образом, не существует алгоритма определения того, является ли число решений диофантова уравнения конечным, нечетным, полным квадратом, простым числом и т. Д.
Доказательство теоремы MRDP формализовано в Coq . [12]
Расширения десятой проблемы Гильберта
Хотя Гильберт поставил проблему для целых рациональных чисел, ее можно также задать для многих колец (в частности, для любого кольца, число элементов которого счетно ). Очевидные примеры - кольца целых чисел полей алгебраических чисел, а также рациональные числа .
По десятой проблеме Гильберта для колец целых чисел полей алгебраических чисел было проведено много работы. Основываясь на более ранних работах Яна Денефа и Леонарда Липшица и используя теорию полей классов, Гарольд Н. Шапиро и Александра Шлапентох смогли доказать:
Десятая проблема Гильберта неразрешима для кольца целых чисел любого поля алгебраических чисел, группа Галуа которого над рациональными числами абелева .
Шлапентох и Танас Фейдас (независимо друг от друга) получили один и тот же результат для полей алгебраических чисел, допускающих ровно одну пару комплексно сопряженных вложений.
Проблема для кольца целых чисел полей алгебраических чисел, отличных от тех, которые охвачены приведенными выше результатами, остается открытой. Точно так же, несмотря на большой интерес, проблема для уравнений над рациональными числами остается открытой. Барри Мазур предположил, что для любого многообразия рациональных чисел топологическое замыкание вещественных чисел множества решений имеет только конечное число компонент. [13] Из этой гипотезы следует, что целые числа не диофантовы над рациональными числами, и поэтому, если эта гипотеза верна, отрицательный ответ на Десятую проблему Гильберта потребует другого подхода, чем тот, который используется для других колец.
Заметки
- ^ С. Барри Купер , Теория вычислимости , стр. 98
- ^ Гильберт 1902 , стр. 458.
- ^ Гильберт 1902 , стр. 444.
- ↑ Юрий Матиясевич (1993). 10-я проблема Гильберта . MIT Press.
- ^ Обзор совместной публикации Дэвиса, Патнэма и Робинсона в Mathematical Reviews ( MR.0133227 ) предположил, что JR был ложным.
- ^ Матиясевич, Юрий (1992). «Мое сотрудничество с Джулией Робинсон» . Математический интеллигент . 14 (4): 38–45. DOI : 10.1007 / bf03024472 .
- ^ Мешки, Джеральд Э. (2003). Математическая логика в ХХ веке . World Scientific. С. 269–273.
- ^ предложения находятся на одном из низших уровней так называемой арифметической иерархии .
- ^ Таким образом, сама гипотеза Гольдбаха может быть выражена следующим образом: для каждого натурального числа номер это сумма двух простых чисел. Конечно, существует простой алгоритм, позволяющий проверить данное число на предмет суммы двух простых чисел.
- ^ Фактически эквивалентность доказуема в арифметике Пеано .
- ^ На данный момент даже 3 не могут быть исключены как абсолютная верхняя граница.
- ^ Доминик Ларчи-Вендлинг и Янник Форстер (2019). Десятая проблема Гильберта в Coq (PDF) (Технический отчет). Саарский университет .
- ^ http://www-math.mit.edu/~poonen/papers/subrings.pdf
Рекомендации
- Гильберт, Дэвид (1901). "Математическая проблема". Archiv der Mathematik und Physik . 3-я серия (на немецком языке). 1 : 44–63, 213–247.
- Гильберт, Дэвид (июль 1902 г.). «Математические задачи» . Бык. Амер. Математика. Soc . 8 (10): 437–479.
- Юрий В. Матиясевич , Десятая проблема Гильберта , MIT Press, Кембридж, Массачусетс, 1993.
- Дэвис, Мартин ; Матиясевич Юрий ; Робинсон, Джулия (1976). «Десятая проблема Гильберта: диофантовы уравнения: положительные аспекты отрицательного решения». В Феликсе Э. Браудере (ред.). Математические разработки, возникающие из проблем Гильберта . Труды симпозиумов по чистой математике . XXVIII.2. Американское математическое общество . С. 323–378. ISBN 0-8218-1428-1. Zbl 0346.02026 .Перепечатано в Сборнике работ Джулии Робинсон , Соломон Феферман , редактор, стр. 269–378, Американское математическое общество, 1996.
- Мартин Дэвис , «Десятая проблема Гильберта неразрешима», American Mathematical Monthly , том 80 (1973), стр. 233–269; перепечатано в качестве приложения к книге Мартина Дэвиса, « Вычислимость и неразрешимость» , Dover reprint 1982.
- Дэвис, Мартин ; Херш, Рувим (1973). «10-я проблема Гильберта». Scientific American . 229 : 84–91. DOI : 10.1038 / Scientificamerican1173-84 .
- Ян Денеф , Леонард Липшиц, Танасес Фейдас, Ян ван Гил, редакторы, «Десятая проблема Гильберта: семинар в Гентском университете, Бельгия, 2–5 ноября 1999 г.». Современная математика . 270 (2000), Американское математическое общество.
- М. Рам Мёрти и Брэндон Фодден: «Десятая проблема Гильберта: введение в логику, теорию чисел и вычислимость», Americal Mathematical Society, ISBN 978-1-4704-4399-3 (июнь 2019 г.).
дальнейшее чтение
- Шлапентох, Александра (2007). Десятая проблема Гильберта. Диофантовы классы и расширения глобальных полей . Новые математические монографии. 7 . Кембридж: Издательство Кембриджского университета . ISBN 0-521-83360-4. Zbl 1196.11166 .
Внешние ссылки
- Десятая проблема Гильберта: история математических открытий
- Страница десятой проблемы Гильберта!
- Чжи Вэй Сунь: О десятой проблеме Гильберта и смежных темах
- Трейлер к «Десятой проблеме Гильберта и Джулии Робинсон» на YouTube