Изменения

=== Примеры диофантовых уравнений ===Ниже приведены примеры наиболее известных частных случаев диофантовых уравнений:* <tex>x^n + y^n = z^n</tex>,:** При при <tex>n=2</tex> решениями этого уравнения (обобщенного уравнения Пифагора) являются пифагоровы тройки.,*:* согласно Великой теореме Ферма это уравнение не имеет ненулевых целых решений при <tex>n>2</tex>.* уравнение Пелля;: <tex>x^2 - n y^2 = 1</tex>, где параметр <tex>n</tex> не является точным квадратом — ;*уравнение Пелля.Каталана:* :<tex>x^z - y^t = 1</tex>, где <tex>z, t>1</tex>, — ;*уравнение Каталана.Туэ:* : <tex>\sum_{i=0}^n a_i x^i y^{n-i} = c</tex> при <tex>n\ge geqslant 3</tex> и <tex>c\ne 0</tex> — уравнение Туэ.

В современной терминологии десятая проблема Гильберта является примером ''массовой проблемы''<ref>Матиясевич Ю.В. Десятая проблема Гильберта. — М.: , Физматлит, 1993. {{--- }} Математическая логика и основания математики, {{---}} с.8.</ref>. Массовая проблема состоит из счетного количества вопросов на каждый из которых нужно дать ответ {{---}} да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.

|statement=Существует перечислимое, но неразрешимое множество натуральных чисел<ref>[http://www.lirmm.fr/~ashen/part3.pdf Н. К. Верещагин, А. Шень, Вычислимые функции. {{---}} М. Издательство МЦНМО, 2008 {{---}} с.22]</ref>.}}

Davis Martin Hilbert's tenth problem is unsolvable . {{---}} Amer. tex. Monthly., V.80, №3 1973,{{---}} p. 233–269.</ref>. Пусть дано множество <tex>M</tex> натуральных чисел и нужно найти алгоритм, который по каждому натуральному <tex>n</texref> определяет, принадлежит это <tex>n</tex> множеству <tex>M</tex> или нетМанин Ю.Такой алгоритм существует тогда и только тогда, когда множество <tex>M</tex> разрешимоИ. Для отрицательного решения десятой проблемы Гильберта достаточно было доказать диофантовость каждого перечислимого множества, то есть по каждому перечислимому множеству <tex>M</tex> уметь строить такое диофантово уравнение, <tex>P(y,x_1\ldots x_k)=0</tex>, которое имело бы натуральные решения <tex>x_1\ldots x_k</tex> для всех <tex>y</tex>, принадлежащих <tex>M</tex> Вычислимое и только для таких <tex>y</tex>. Тогда, взяв в качестве <tex>M</tex> перечислимое, но неразрешимое множество, можно было бы получить, что для соответствующего уравнения <tex>P(y,x_1\ldots x_k)=0</tex> нет общего алгоритма, который по каждому натуральному <tex>y</tex> давал бы ответ на вопрос о существовании у этого уравнения натуральных решенийневычислимое. Если бы этот алгоритм существовал, то можно было бы за конечное число шагов узнать, имеет ли уравнение <tex>P(0,x_1\ldots x_k)=0</tex> решение, то есть принадлежит ли число <tex>0</tex> множеству <tex>M</tex>, имеет ли уравнение <tex>P(1,x_1\ldots x_k)=0</tex> решение и так далее— М. Получилось бы, что существует алгоритмСоветское Радио, который по каждому натуральному <tex>y</tex> за конечное число шагов определяет, принадлежит <tex>y</tex> множеству <tex>M</tex> или нет1980 {{---}} c. Тогда, в соответствии с тезисом Черча, множество <tex>M46-64</texref> было бы разрешимым вопреки выбору этого множества.

Ниже приведены основные идеи доказательства неразрешимости проблемы существования решения диофантова уравнения в целых числах. {| | bgcolor="Lavender" | <font color=Этапы доказательства неразрешимости "black"> Пусть дано множество <tex>M</tex> натуральных чисел и нужно найти алгоритм, который по каждому натуральному <tex>n</tex> определяет, принадлежит это <tex>n</tex> множеству <tex>M</tex> или нет.|} :В соответствии с тезисом Черча, такой алгоритм существует тогда и только тогда, когда множество <tex>M</tex> разрешимо.  :Для отрицательного решения десятой проблемы Гильбертадостаточно доказать диофантовость каждого [[Перечислимые языки|перечислимого множества]], то есть по каждому перечислимому множеству <tex>M</tex> уметь строить такое диофантово уравнение, <tex>P(y,x_1\ldots x_k)=0</tex>, которое имело бы натуральные решения <tex>x_1\ldots x_k</tex> для всех <tex>y</tex>, принадлежащих <tex>M</tex> и только для таких <tex>y</tex>.  :Тогда, взяв в качестве <tex>M</tex> перечислимое, но [[Разрешимые (рекурсивные) языки # Примеры неразрешимых множеств | неразрешимое множество]], можно было бы получить, что для соответствующего уравнения <tex>P(y,x_1\ldots x_k)=0</tex> нет общего алгоритма, который по каждому натуральному <tex>y</tex> давал бы ответ на вопрос о существовании у этого уравнения натуральных решений. Если бы этот алгоритм существовал, то можно было бы за конечное число шагов узнать, имеет ли уравнение <tex>P(0,x_1\ldots x_k)=0</tex> решение, то есть принадлежит ли число <tex>0</tex> множеству <tex>M</tex>, имеет ли уравнение <tex>P(1,x_1\ldots x_k)=0</tex> решение и так далее. Получилось бы, что существует алгоритм, который по каждому натуральному <tex>y</tex> за конечное число шагов определяет, принадлежит <tex>y</tex> множеству <tex>M</tex> или нет. :Тогда, в соответствии с тезисом Черча, множество <tex>M</tex> было бы разрешимым вопреки выбору этого множества. ==Этапы доказательства DPRM-теоремы=====Гипотеза и нормальная форма Мартина Дэвиса===М. Дэвис перешёл от формулировки десятой проблемы Гильберта в целых числах к естественной для теории алгоритмов формулировке в целых неотрицательных числах.

Также Дэвис доказалДоказать гипотезу Дэвису не удалось, но он получил близкий к доказательству результат, показав <ref>[http://www.jstor.org/stable/2266325?seq=1#page_scan_tab_contents M. Davis. Arithmetical problems and recursively enumerable predicates. {{---}} The Journal of Symbolic Logic 18 (1), 1953 {{---}} p. 33–41]</ref>, что любое перечислимое множество можно представить в виде, названном ''нормальной формой Дэвиса'':

Основополагающий вклад в решение десятой проблемы Гильберта внесла американский математик Джулия Робинсон. Ее учитель, Альфред Тарский, предположил, что даже множество всех степеней числа <tex>2</tex> не является диофантовым. Джулия Робинсон исследовала вопрос о том, является ли диофантовым множество, состоящее из троек :

В 1961 году в совместной работе Робинсон, Дэвиса и Патмена <ref>Martin Davis, Hilary Putnam, Julia Robinson The decision problem for exponential Diophantine equations. {{---}} Annals of Mathematics — 1961. — Vol. 74, № 3 — p. 425—436</ref> было получено экспоненциально - диофантово представление для любого перечислимого множества:

Если возвести обе части всех этих уравнений в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система.  В результате совместной работы Дэвиса, Робинсон, Патнема, Матиясевича было доказано, что по заданию перечислимого множества в любой стандартнойформе можно построить его диофантово представление:* построить арифметическую формулу со многими ограниченными кванторами общности;* преобразовать эту формулу в нормальную форму Дейвиса с одним ограниченным квантором общности; * устранить этот ограниченный квантор общности ценой перехода к экспоненциально-диофантовым уравнениям;* устранить возведение в степень. Таким образом, теорема о неразрешимости десятой проблемы Гильберта была доказанаправильность гипотезы Мартина Дэвиса, которая стала называться DPRM-теоремой. Из этой теоремы следует, что десятая проблема Гиль­берта является неразрешимой.

*Матиясевич Ю.В. Десятая проблема Гильберта. — М.: , Физматлит, 1993. - — Математическая логика и основания математики.*Проблемы Гильберта, . Сборник под редакцией П. С. Александрова, М., Наука, 1969 г.*Ю. В. Матиясевич. Диофантовы множества. — УМН, 1972, том 27, выпуск 5(167), — с. 185–222*[http://kvant.ras.ru/1970/07/o_reshenii_desyatoj_problemy_g.htm П. Варпаховский, А. Н. Колмогоров О решении десятой проблемы Гильберта // , журнал Квант. — 1970. — № 7. — С. 38—44.]