Десятая проблема гильберта доклад

Обновлено: 15.06.2024

На последнем заседании Президиума РАН с докладом об успехах решения диофантовых уравнений в 20 веке выступил академик Юрий Матиясевич.

Юрий Матиясевич (Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН) известен тем, что завершил доказательство алгоритмической неразрешимости задачи – десятой проблемы Гильберта. Выступая на заседании президиума РАН, он рассказал историю вопроса.

В 1900 году на Втором международном конгрессе математиков немецкий математик Давид Гильберт огласил список из 23 самых важных, по его мнению, нерешенных математических проблем, которые оказали значительное влияние на дальнейшее развитие математики. Проблема под номером десять касалась так называемых диофантовых уравнений, трудность решения которых состоит в ограничении на допустимые значения неизвестных, которые должны быть целыми положительными числами. Такое условие возникает как в чисто теоретических математических задачах, так и в прикладных. (Примером может служить расчет зубчатой передачи). Уравнения названы в честь греческого математика Диофанта, который жил в третьем веке нашей эры. К концу 19-го века, были найдены решения большого количества диофантовых уравнений, и было доказано, что многие из них решений не имеют. Однако дальнейшее их рассмотрение имело большое значение, поскольку для их решения математикам приходилось изобретать все новые и новые методы. В 10-ой проблеме Гильберт просил решить не конкретные диофантовы уравнения, а найти общий, универсальный метод (алгоритм), который будучи применен к конкретному диофантову уравнению, давал ответ на вопрос, имеет ли это уравнение решения или нет. Сегодня, благодаря усилиям математиков, известно, что 10-ая проблема Гильберта неразрешима – требуемого в ней алгоритма не существует. Однако общее понятие алгоритма было выработано только в 30-ые годы 20-го века в результате исследований Курта Гёделя, Алана Тьюринга, Алонзо Чёрча и других математических логиков. В наши дни алгоритм можно отождествить с программой на любом языке программирования. Таким образом, полученное "отрицательное решение" 10-ой проблемы Гильберта состояло в доказательстве невозможности написать программу, которая говорила бы нам, имеет ли то или иное уравнение решения или нет.

Какая же может быть польза от этого доказательства невозможности? Академик Матиясевич сравнил ситуацию с законом сохранения энергии, который делает невозможным построение "вечного двигателя", избавляя тем самым изобретателей от заведомо бесполезной траты времени на его построения, а патентные бюро – от рассмотрения заявок горе-изобретателей. Аналогично доказанная неразрешимость 10-ой проблемы Гильберта дает математикам "моральное право" больше не тратить время на попытки найти универсальный метод решения диофантовых уравнений, а финансирующим органам – отказывать в поддержке проектов, обещающих разработать такой метод.

Однако у доказательства неразрешимости проблемы есть и другая польза, более важная, чем само ее решение. – это новые идеи и методы, разработанные для получения ее решения. В начале 50-ых годов американский математик Мартин Дейвис выдвинул гипотезу, которая утверждала, что одно из основополагающих понятий информатики – понятие перечислимого множества – совпадает с теоретико-числовым понятием диофантова множества, возникающим при изучении параметрических диофантовых уравнений. Гипотеза Дейвиса была доказана через два десятилетия после ее выдвижения, последний шаг в 1970 году сделал советский математик Юрий Матиясевич.

Гипотеза Дейвиса, став теоремой, позволила установить неразрешимость многих других проблем и получить другие интересные следствия. Например, на основе диофантовых уравнений была предложена новая криптографическая система.

Академик Юрий Матиясевич подчеркнул, что не следует думать, что с установлением неразрешимости 10-ой проблемы Гильберта закрыты все алгоритмические проблемы, связанные с диофантовыми уравнениями. Напротив, здесь имеется много открытых проблем, которые 21-ый век унаследовал от 20-го. Это направление продолжает развиваться.

В ходе обсуждения доклада президент РАН академик Юрий Осипов отметил, что именно Юрий Владимирович Матиясевич внес самый большой вклад в решение проблем Гильберта. На этой базе может быть построено решение многих проблем криптографии и теории чисел.

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

Содержание

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

В докладе Гильберта постановка десятой задачи самая короткая из всех:

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

Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen rationalen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem sich mittelst einer endlichen Anzahl von Operationen entscheiden läßt, ob die Gleichung in ganzen rationalen Zahlen lösbar ist [4] .

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

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

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

Предпосылки

Целочисленное решение алгебраических уравнений интересовало математиков ещё с античных времён. Например, много внимания уделялось уравнению : если его решением был набор из натуральных чисел , то по теореме, обратной к теореме Пифагора, из отрезков длиной можно было получить прямоугольный треугольник [11] . Евклид привёл формулы для нахождения всех целочисленных решений этого уравнения [12] . Некоторые виды уравнений второй степени и их системы рассмотрел Диофант Александрийский [13] , его работы позднее использовали Леонард Эйлер, Пьер Ферма, Жозеф Луи Лагранж, Карл Фридрих Гаусс и другие математики, занимавшиеся теорией чисел. В частности, Ферма выдвинул свою знаменитую гипотезу. К 1768 году Лагранж полностью исследовал вопрос о целочисленных решениях любого уравнения второй степени с двумя неизвестными [14] .

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

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

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

До 40-х годов XX века исследования по десятой проблеме велись в направлении поиска требуемого алгоритма хотя бы для некоторых классов диофантовых уравнений. Через несколько лет после доклада Гильберта, в 1908 году, Аксель Туэ показал, что уравнение , где — целое число, а — неприводимый многочлен с одинаковой степенью () всех членов не может иметь бесконечно много целых решений [15] . В 1938 году Туральф Сколем (англ.) опубликовал метод исследования диофантовых уравнений вида где — неполная разложимая форма (неприводимый многочлен, разлагающийся в расширении поля рациональных чисел на произведение линейных множителей, ), удовлетворяющая некоторым условиям [16] . Несмотря на результат Туэ, даже уравнения с двумя неизвестными не поддавались никаким усилиям математиков (алгоритм для решения уравнений с одним неизвестным следует из теоремы Безу).

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

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

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

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

Такую запись он назвал диофантовым представлением множества, а само множество также назвал диофантовым. Для доказательства неразрешимости десятой проблемы нужно было лишь показать диофантовость любого перечислимого множества, то есть показать возможность построения уравнения, которое имело бы натуральные корни только при всех a_1, \ldots, a_n\mathcal " width="" height="" />
, принадлежащих этому перечислимому множеству: поскольку среди перечислимых множеств содержатся неразрешимые, то, взяв неразрешимое множество за основу, невозможно было бы получить общий метод, который бы по -ке определял, имеет ли на этом наборе уравнение натуральные корни. Всё это привело Дэвиса к следующей гипотезе:

Понятия диофантового и перечислимого множества совпадают. Это значит, что множество диофантово тогда и только тогда, когда оно перечислимо.

Дэвис также сделал первый шаг — доказал, что любое перечислимое множество можно представить в виде:

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

. Найти диофантово представление для операции возведения в степень ей не удалось, но, тем не менее, в своей работе [23] она показала достаточное условие для его существования:

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

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

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

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

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

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

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

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

Десятая проблема Гильберта решена, и на нее есть отрицательный ответ: такого общего алгоритма не существует. Это результат совместной работы Мартина Дэвиса , Юрия Матиясевича , Хилари Патнэм и Джулии Робинсон, которая длится 21 год, Матиясевич завершил теорему в 1970 году. [1] Теорема теперь известна как теорема Матиясевича или теорема MRDP.

Оригинальная рецептура

Гильберт сформулировал проблему следующим образом: [2]

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

Иногда бывает, что мы ищем решение при недостаточных гипотезах или в неверном смысле, и по этой причине не достигаем успеха. Тогда возникает проблема: показать невозможность решения при данных гипотезах или в предполагаемом смысле.

Диофантовы множества

В диофантовом уравнении есть два типа переменных: параметры и неизвестные. Диофантово множество состоит из параметров, для которых разрешимо диофантово уравнение. Типичный пример - линейное диофантово уравнение с двумя неизвестными,

Диофантовы определения могут быть даны как одновременными системами уравнений, так и отдельными уравнениями, поскольку система

п 1 знак равно 0 , … , п k знак равно 0 = 0, \ ldots, p_ = 0>

эквивалентно единственному уравнению

Множества натуральных чисел, пар натуральных чисел (или даже n -комплектов натуральных чисел), которые имеют диофантовы определения, называются диофантовыми множествами . В этих терминах десятая проблема Гильберта спрашивает, существует ли алгоритм, чтобы определить, является ли данное диофантово множество непустым.

Работа над проблемой была в терминах решений в натуральных числах (понимаемых как неотрицательные целые числа), а не в произвольных целых числах. Эти две проблемы эквивалентны: любой общий алгоритм, который может решить, имеет ли данное диофантово уравнение целочисленное решение, может быть преобразован в алгоритм, который определяет, имеет ли данное диофантово уравнение решение в виде натурального числа, и наоборот. Это можно увидеть следующим образом: требование, чтобы решения были натуральными числами, можно выразить с помощью теоремы Лагранжа о четырех квадратах : каждое натуральное число является суммой квадратов четырех целых чисел, поэтому мы просто заменяем каждый параметр суммой квадраты четырех дополнительных параметров. Точно так же, поскольку каждое целое число можно записать как разность двух натуральных чисел, мы можем заменить каждый параметр, который варьируется в целых числах, разностью двух параметров, которые варьируются в натуральных числах. [4]

Рекурсивно перечислимые множества

Перечислимое множество можно охарактеризовать как один , для которого существует такой алгоритм , который будет в конечном счете , остановить , когда член набора обеспечивается в качестве входных данных, но может продолжаться до бесконечности , когда вход не является членом. Именно развитие теории вычислимости (также известной как теория рекурсии) обеспечило точное объяснение интуитивного понятия алгоритмической вычислимости, сделав таким образом понятие рекурсивной перечислимости совершенно строгим. Очевидно, что диофантовы множества рекурсивно перечислимы. Это связано с тем, что можно расположить все возможные кортежи значений неизвестных в последовательности, а затем для данного значения параметра (ов) протестировать эти кортежи один за другим, чтобы увидеть, являются ли они решениями соответствующего уравнения. Неразрешимость десятой проблемы Гильберта является следствием того удивительного факта, что верно обратное:

Любое рекурсивно перечислимое множество диофантово.

Этот результат известен как теорема Матиясевича (потому что он обеспечил решающий шаг, завершивший доказательство) и теорема MRDP (для Юрия Матиясевича , Джулии Робинсон , Мартина Дэвиса и Хилари Патнэм ). Поскольку существует рекурсивно перечислимое множество, которое не вычислимо, неразрешимость десятой проблемы Гильберта является немедленным следствием. На самом деле можно сказать больше: существует многочлен

с целыми коэффициентами такими, что множество значений а для которого уравнение

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

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

Используя свойства уравнения Пелла, она доказывает, что из JR следует, что EXP диофантово, а также биномиальные коэффициенты, факториал и простые числа.

Теорема Матиясевича / MRDP связывает два понятия - одно из теории вычислимости, другое из теории чисел - и имеет некоторые удивительные следствия. Возможно, самым удивительным является существование универсального диофантова уравнения:

Это верно просто потому, что диофантовы множества, будучи равными рекурсивно перечислимым множествам, также равны машинам Тьюринга . Хорошо известное свойство машин Тьюринга состоит в том, что существуют универсальные машины Тьюринга, способные выполнять любой алгоритм.

Хилари Патнэм отметила, что для любого диофантова множества S натуральных чисел, существует многочлен

диапазон по всем натуральным числам. Это можно увидеть следующим образом: Если

Так, например, существует многочлен, положительная часть диапазона которого - это в точности простые числа. (С другой стороны, ни один многочлен не может принимать только простые значения.) То же самое верно и для других рекурсивно перечислимых наборов натуральных чисел: факториала, биномиальных коэффициентов, чисел Фибоначчи и т. Д.

Другие приложения касаются того, что логики называют Π 1 0 ^ > предложения, иногда также называемые предложениями типа Гольдбаха . [8] Это похоже на гипотезу Гольдбаха , утверждающую, что все натуральные числа обладают определенным свойством, которое алгоритмически проверяется для каждого конкретного числа. [9] Теорема Матиясевича / MRDP означает, что каждое такое предложение эквивалентно утверждению, что какое-то конкретное диофантово уравнение не имеет решений в натуральных числах. [10] Ряд важных и знаменитых проблем имеют такую ​​форму: в частности, Великая теорема Ферма , гипотеза Римана и теорема о четырех цветах . Кроме того, утверждение, что определенные формальные системы, такие как арифметика Пеано или ZFC , непротиворечивы, может быть выражено как Π 1 0 ^ > предложения. Идея состоит в том, чтобы следовать Курту Гёделю в кодировании доказательств натуральными числами таким образом, чтобы свойство быть числом, представляющим доказательство, было алгоритмически проверяемым.

Особенно яркая форма теоремы Гёделя о неполноте также является следствием теоремы Матиясевича / MRDP:

Мы можем связать алгоритм А с любой из обычных формальных систем, таких как арифметика Пеано или ZFC , позволяя ей систематически генерировать следствия аксиом, а затем выводить число п всякий раз, когда предложение формы

генерируется. Тогда теорема говорит нам, что либо ложное утверждение такой формы доказано, либо истинное остается недоказанным в рассматриваемой системе.

Мы можем говорить о степени диофантова множества как о наименьшей степени многочлена в уравнении, определяющем это множество. Точно так же мы можем назвать размерность такого набора наименьшим количеством неизвестных в определяющем уравнении. Из-за существования универсального диофантова уравнения ясно, что существуют абсолютные верхние границы для обеих этих величин, и определение этих границ вызвало большой интерес.

Уже в 1920-х годах Торальф Сколем показал, что любое диофантово уравнение эквивалентно одному из степеней 4 или меньше. Его уловка заключалась в том, чтобы ввести новые неизвестные, задав уравнения, равные квадрату неизвестного или произведению двух неизвестных. Повторение этого процесса приводит к системе уравнений второй степени; тогда уравнение степени 4 получается суммированием квадратов. Таким образом, любое диофантово множество тривиально имеет степень 4 или меньше. Неизвестно, насколько возможен такой результат.

Юлия Робинсон и Юрий Матиясевич показали, что каждое диофантово множество имеет размерность не больше 13. Позже Матиясевич усовершенствовал свои методы, чтобы показать, что достаточно 9 неизвестных. Хотя вполне может быть, что это не самый лучший результат, дальнейшего прогресса нет. [11] Так, в частности, не существует алгоритма проверки диофантовых уравнений с 9 или менее неизвестными на разрешимость в натуральных числах. В случае рациональных целочисленных решений (как первоначально сформулировал Гильберт) трюк с четырьмя квадратами показывает, что не существует алгоритма для уравнений с не более чем 36 неизвестными. Но Чжи Вэй Сунь показал, что задача для целых чисел неразрешима даже для уравнений с не более чем 11 неизвестными.

Доказательство теоремы MRDP формализовано в Coq . [12]

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

По десятой проблеме Гильберта для колец целых чисел полей алгебраических чисел было проведено много работы. Основываясь на более ранних работах Яна Денефа и Леонарда Липшица и используя теорию полей классов, Гарольд Н. Шапиро и Александра Шлапентох смогли доказать:

Десятая проблема Гильберта неразрешима для кольца целых чисел любого поля алгебраических чисел, группа Галуа которого над рациональными числами абелева .

Шлапентох и Танас Фейдас (независимо друг от друга) получили один и тот же результат для полей алгебраических чисел, допускающих ровно одну пару комплексно сопряженных вложений.

Проблема для кольца целых чисел полей алгебраических чисел, отличных от тех, которые охвачены приведенными выше результатами, остается открытой. Точно так же, несмотря на большой интерес, проблема для уравнений над рациональными числами остается открытой. Барри Мазур предположил, что для любого многообразия рациональных чисел топологическое замыкание вещественных чисел множества решений имеет только конечное число компонент. [13] Из этой гипотезы следует, что целые числа не диофантовы над рациональными числами, и поэтому, если эта гипотеза верна, отрицательный ответ на Десятую проблему Гильберта потребует другого подхода, чем тот, который используется для других колец.

Пролог
Диофант – последний великий
математик античности.
Основным
произведением
Диофанта была "Арифметика".
В
этой
книге
произошел
окончательный отказ от так
называемой
"геометрической
алгебры"и переход к новому
математическому
языку,
так
называемой "буквенной алгебре".
Диофант Александрийский
3 в. н.э.

Диофантовы уравнения
Основные направления деятельности Диофанта:
1) Арифметико – алгебраическое направление;
2) Исследование неопределенных уравнений.
Уравнение вида:
Р(х1, х2, …, хn)=0,
где
Р – многочлен с целыми коэффициентами, а
х1,х2,…хn∊ℤ, называется диофантовым уравнением.

4. Пример 1:

если
тройка
x y z
натуральных
2
2
чисел
2
(x0,y0,z0)
ему
удовлетворяет то по теореме, обратной к теореме
Пифагора, из отрезков длины x0, y0 и z0 можно сложить
прямоугольный
треугольник
и,
таким
образом,
построить прямой угол.
y=2mnl
Решение: x=(m2-n2)l
z=(m2+n2)l m Ν,n Ν,l Ν

5. Великая теорема Ферма

Пример 2:
x y z ,n
n
n
n
Великая
теорема Ферма
Это уравнение при n>2 не
имеет решений в целых
числах.
Пьер Ферма
(1601 - 1665)
Эта задача, казалось бы, не
слишком
отличается
от
предыдущей, на самом дела
оказалась чудовищно трудной.

6. Возникает вопрос:

Нет ли какого-нибудь способа по виду
уравнения, по его коэффициентам
определять, имеет ли это уравнение
решение в целых числах?

7. Десятая проблема

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

9. Задача о разрешении диофантовых уравнений

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

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

Гипотеза Дэвиса
С другой стороны, пусть
Р(х1, х2, …, хn)=0 (1) - произвольное диофантово
уравнение, и мы интересуемся наличием у него
неотрицательных решений.
а
Рассмотрим систему уравнений
:
P ( x1 , x 2 . x n ) 0
2
2
2
2
x
y
y
y
y
1,1
1, 2
1, 3
1, 4
1
2
2
2
2
x 2 y 2,1 y 2, 2 y 2,3 y 2, 4
.
x n y n2,1 y n2, 2 y n2,3 y n2, 4
(2)

P ( x1 , x 2 . x n ) 0
2
2
2
2
x
y
y
y
y
1,1
1, 2
1, 3
1, 4
1
2
2
2
2
x 2 y 2,1 y 2, 2 y 2,3 y 2, 4 (2)
.
x n y n2,1 y n2, 2 y n2,3 y n2, 4
P( x1 , x2 . xn ) 0
(1)
Понятно, что:
1)что любое решение системы (2) в произвольных целых числах
содержит решение уравнения (1) в неотрицательных целых
числах.
2) что для любого решения уравнения (1) в неотрицательных
целых числах х1, х2, …, xn найдутся целочисленные значения y1,1,
…, yn,4, дающие решение системы (2) , так как каждое
неотрицательное целое число представимо в виде суммы
квадратов четырёх целых чисел (Теорема о четырех квадратах).

P ( x1 , x 2 . x n ) 0
2
2
2
2
x
y
y
y
y
1,1
1, 2
1, 3
1, 4
1
2
2
2
2
x 2 y 2,1 y 2, 2 y 2,3 y 2, 4
.
x n y n2,1 y n2, 2 y n2,3 y n2, 4
(2)
P( x1 , x2 . xn ) 0
(1)
Система (2) может быть свёрнута в одно уравнение :
Е(х1, х2, …, xn , y1,1, …, yn,4)
-разрешимое в целых числах тогда и только тогда, когда исходное
уравнение (1) разрешимо в неотрицательных целых числах.
Таким образом, проблема распознавания наличия решений в
неотрицательных целых числах сводится к массовой проблеме
распознавания наличия решений в целых числах.

Гипотеза Дэвиса
Тем
самым
установлено,
что
для
доказательства
неразрешимости
10-й
проблемы Гильберта в её оригинальной
постановке
достаточно
доказать
неразрешимость её аналога, касающегося
наличия или отсутствия решений в
неотрицательных целых – в числах
натуральных.

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

наряду с классическими диофантовыми уравнениями:
Р(х1, х2, …, хn)=0, где Р – многочлен с целыми
коэффициентами, х1, х2, …, хn∊ℤ
Дэвис рассмотрел их параметрическую версию:
Р(а1, а2, …, аm, х1, х2, …, хn)=0, где Р – многочлен с
целыми коэффициентами, а1, а2, …, аm ∊ℤ - параметры,
х1, х2 ,…, хn∊ℤ - переменные.

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

Р(а1, а2, …, аm, х1, х2, …, хn)=0, где Р – многочлен с
целыми коэффициентами, а1, а2, …, аm ∊ℤ параметры, х1, х2 ,…, хn∊ℤ - переменные.
При одном наборе значений параметров уравнение
может иметь решение, при другом решений может не
существовать.
Дэвис выделил множество М, которое содержит все наборы
значений параметров при которых уравнение имеет
решение:
〈 а1, а2, …, аm 〉∊М⇔ ∃ х1, х2 ,…, хn
<Р(а1, а2, …, аm, х1, х2, …, хn)=0>

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

〈 а1, а2, …, аm 〉∊М⇔∃ х1, х2 ,…, хn
<Р(а1, а2, …, аm, х1, х2, …, хn)=0>
(1) – диофантово представление множества
М – диофантово множестово
Для доказательства неразрешимости десятой
проблемы Гильберта нужно было лишь показать
диофантовость любого перечислимого множества.
Перечеслимое множество - множество конструктивных объектов, все
элементы которого могут быть получены с помощью некоторого
алгоритма.

Для доказательства неразрешимости десятой
проблемы Гильберта нужно было лишь показать
диофантовость любого перечислимого множества.
то есть нужно показать возможность
построения уравнения, которое имело
бы натуральные корни х1, х2, …, хn
только при всех 〈 а1, а2, …, аm 〉,
принадлежащих этому перечислимому
множеству.

24. Дэвис и Патнем: объединение усилий

В 1958 году М. Дэвис и Х. Патнем
публикуют работу в которой они
рассмотрели класс экспоненциальнодиофантовых уравнений, имеющих
вид:
ЕL (х1, х2 ,…, хn )=ER(х1, х2 ,…, хn )
Хилари Патнем
род. 1926г.
где ЕL , ER — экспоненциальные многочлены,
то есть выражения, полученные из
переменных и рациональных чисел с
применением операций сложения, умножения
и возведения в степень.

25. Дэвис, Патнем и Робинсон: объединение усилий

Гипотеза Робинсон
Для этого достаточно построить
конкретное уравнение
Р(a, b, х1, х2, …, хn)=0
недопускающее решение с a>bb
для каждого k имеющее решение с
а>bk

27. Что сделал Ю.В. Матиясевич?

Именно такого рода уравнение
удалось
построить
22-летнему
аспиранту Юрию Матиясевичу. в
начале 1970 года…
…обратившись к рассмотрению
последовательности Фибоначчи.
Числа Фибоначчи , бесконечная
последовательность , которая
определяется рекуррентной формулой:
Юрий Владимирович
Матиясевич
род .в 1947г.
ψn+1=ψn-1+ψn
0, 1, 1, 2, 3, 5, 8, 13, 21, …

Р(a, b, х1, х2, …, хn)=0
• недопускающее решение с a>bb
• для каждого k имеющее решение с а>bk
Ю.В. Матиясевич заметил, что если:
1) за а взять половину номера четного члена
последовательности Фибоначчи, а за b —
сам член, то неравенство a>bb будет всегда
неверно;
2) для любого k можно найти такой четный
член последовательности, что неравенство
а>bk будет верно.

Ю.В. Матиясевич рассмотрел последовательность,
задаваемую соотношениями:
φ0=0, φ1=1, n+1=3 n– n-1
Получилось в точности последовательность из четных
членов первоначальной последовательности:
0=0, 1=1, 2=3, 3=8, 4=21, 5=55, 6 =144, 7 = 377…
Приняв теперь за а номер члена последовательности, а
за b — член последовательности с номером a, т. е. a,
мы получаем, что снова выполняется требуемое
свойство для a и b.

Осталось построить уравнение Р(а, b, x1, . xk)=0,
которое имело бы натуральное решение тогда и
только тогда, когда b
= a
Для этого достаточно было построить систему
диофантовых уравнений Р1 =0, …, Рn = 0 в
переменных a, b, x1 . , xn, имеющую решение тогда
и только тогда, когда b = a— ведь такая система
имеет в точности те же решения, что и единственное
уравнение
Р21+ .. +Р2n=0

Читайте также:

  
• Доклад о корнях орхидеи
  
• Доклад про среднеазиатскую черепаху
  
• Рыцари столетней войны доклад
  
• Доклад на тему роспись камней
  
• Этические нормы профконсультанта доклад