Изменения

<table class="lm-plashka" style="clear: both; width: {{{width|80%}}}; background-color: #fefefe; border-color:#ff0000 #ff0000 #ff0000 #ff0000; border-style: solid; border-width: 1px 1px 1px 10px; padding: 4px; margin: 1px auto; vertical-align: middle; text-align: left;"><tr><td style="vertical-align: middle"><!-- -->'''Эта статья находится в разработке'''</td></tr></table>В 1900 году в Париже на втором Международном Конгрессе математиков выдающийся математик Давид Гильберт выступил с докладом, который назывался "Математические проблемы"«Математические проблемы». Десятая из двадцати трех обозначенных в докладе проблем была сформулирована Гильбертом так:

|definition='''Диофантово уравнение ''' (англ. ''diophantine equation'') имеет вид<tex>MP(x_1...x_m\ldots x_n)=0</tex>, где <tex>MP</tex> {{---}} многочлен с целыми коэффициентами.<tex>(1)</tex>

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

|statement=Не существует алгоритма, который узнавал бы по произвольному диофантову уравнению, имеет ли оно решенияв целых числах или нет.

Доказательство неразрешимости этой проблемы вытекает из тезиса Черча и следующих двух теорем:{{Теорема |statement=Существует перечислимое, но неразрешимое множество натуральных чисел <ref>[http://www.lirmm.fr/~ashen/part3.pdf Н. К. Верещагин, А. Шень, Вычислимые функции. {{---}} М. Издательство МЦНМО, 2008 {{---}} с.22]</ref>.}}{{Теорема|author=DPRM-теорема |statement=Этапы доказательства Понятия «диофантово множество» и «перечислимое множество» совпадают.}}Аббревиатура в названии последней теоремы образована из первых букв фамилий математиков Мартина Девиса (англ. Martin ''Davis''), Хилари Патнэма (англ. ''Hilary Putnam''), Джулии Робинсон (англ. ''Julia Robinson'') и Юрия Матиясевича. Подробное доказательство неразрешимости десятой проблемы Гильбертаможно прочитать здесь <ref>Davis Martin Hilbert's tenth problem is unsolvable. {{---}} Amer. tex. Monthly., V.80, №3 1973 {{---}} p.233–269</ref> <ref>Манин Ю. И. Вычислимое и невычислимое. — М., Советское Радио, 1980 {{---}} c. 46-64</ref>.  Ниже приведены основные идеи доказательства неразрешимости проблемы существования решения диофантова уравнения в целых числах. {| | 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-теоремы=====Гипотеза и нормальная форма Мартина Дэвиса===М. Дэвис перешёл от формулировки десятой проблемы Гильберта в целых числах к естественной для теории алгоритмов формулировке в целых неотрицательных числах. Для конкретного диофантова уравнения задача о нахождении целочисленных решений и задача о нахождении решений в разрешимость этой проблемыцелых неотрицательных числах {{---}} разные задачи. Однако если мы интересуемся сразу всеми уравнениями (как, например, в этом смысле задача была сформулирована им вполне корректно10-й проблеме Гильберта), то эти две задачи совпадают. Действительно, если рассмотреть систему уравнений <tex>(2)</tex> <tex> \left\{ \begin{array}{lcr}P(x_1\ldots x_n)=0; \\ x_1=y_{1,\;1}^2+y_{1,\;2}^2+y_{1,\;3}^2+y_{1,\;4}^2;\\\ldots \\\ldots \\x_n=y_{n,\;1}^2+y_{n,\;2}^2+y_{n,\;3}^2+y_{n,\;4}^2 \end{array}\right. Понятие алгоритма было сформулировано </tex>, то станет понятно, что:*любое решение системы <tex>(2)</tex> в произвольных целых числах содержит решение уравнения <tex>(1)</tex> в неотрицательных целых числах; *для любого решения уравнения <tex>(1)</tex> в неотрицательных целых числах <tex>x_1,x_2,\ldots , x_n</tex> найдутся целочисленные значения <tex>y_{1,\;1},\ldots , y_{n,\;4}</tex>, дающие решение системы <tex>(2)</tex> , так как, согласно известной теореме Лагранжа, каждое неотрицательное целое число представимо в тридцатые годы двадцатого века виде суммы квадратов четырёх целых чисел.Система уравнений <tex>(2)</tex> может быть свёрнута в работах матлогиков Черчаодно уравнение :<tex>E(x_1, x_2, \ldots , x_n, y_{1,\;1}, \ldots , y_{n, Клини\;4})</tex>, Тьюринга разрешимое в целых числах тогда и только тогда, Геделякогда исходное уравнение <tex>(1)</tex> разрешимо в неотрицательных целых числах. Важную роль {{Утверждение|statement=Таким образом, массовая проблема распознавания разрешимости диофантовых уравнений в целых числах сводится к массовой проблеме распознавания разрешимости диофантовых уравнений в решении целых неотрицательных числах. }} Наряду с отдельными диофантовыми уравнениями, Дэвис рассмотрел семейства диофантовых уравнений вида:<tex>P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0</tex>, где <tex>P</tex> – многочлен с целыми коэффициентами, <tex>a_1, a_2, \ldots , a_m\in\mathbb{Z}</tex> {{---}} параметры,<tex>x_1, x_2,\ldots , x_n\in\mathbb{Z}</tex> {{---}} переменные. Каждое такое семейство определяет некоторое множество <tex>M</tex> тех значений параметров, при которых уравнение разрешимо относительно переменных <tex>x_1, x_2,\ldots , x_n</tex> : <tex>\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow x_1, x_2,\ldots , x_n\</tex> <tex>\left \{ P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0 \right \}</tex> Такие множества называются ''диофантовыми''. Исследования Мартина Дэвиса, направленные на доказательство неразрешимости десятой проблемы Гильберта сыграл Эмиль Пост, привели его к постановке задачи, когда описано некоторое множество и требуется узнать, является ли оно диофантовым. В одной простейших случаях диофантовость множества очевидна {{---}} ясно, например, что диофантовым является множество всех положительных нечетных чисел. Однако совсем нелегко ответить на такие вопросы, как: «диофантово ли множество всех степеней числа <tex>2</tex>?», «диофантово ли множество всех простых чисел?», «диофантово ли множество всех совершенных чисел?» С первого взгляда кажется, что на эти вопросы следует дать отрицательный ответ. Тем не менее все эти множества являются диофантовыми. Приведем примеры диофантовых множеств:*множество всех полных квадратов, представлено уравнением <tex>a-x^2=0</tex>;*множество всех составных чисел, представлено уравнением <tex>a-(x_1+2)(x_2+2)=0</tex>;*множество всех нестепеней числа <tex>2</tex>, представлено уравнеием <tex>a-(2x_1+3)x_2=0</tex>.Для доказательства неразрешимости десятой проблемы Гильберта нужно было лишь показать диофантовость любого перечислимого множества, то есть нужно показать возможность построения уравнения, которое имело бы натуральные корни <tex>x_1,x_2,\ldots , x_n</tex> только при всех <tex>\left \langle a_1, a_2, \ldots , a_m\right \rangle</tex>, принадлежащих этому перечислимому множеству. Исходя из своих работ этого, Дэвис сформулировал следующую гипотезу:{{Гипотеза |author=Мартина Дэвиса|statement=Понятия диофантового и перечислимого множества совпадают. Это значит, что множество диофантово тогда и только тогда, когда оно перечислимо.}}Доказать гипотезу Дэвису не удалось, но он написалполучил близкий к доказательству результат, показав <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>\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow \exists z \quad \forall y < z \quad \exists x_1, x_2,\ldots , x_n\</tex> <tex>\left \{ P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0 \right \}</tex> ===Предикат Робинсон. Совместный результат М. Дэвиса и Х. Патнема и Д. Робинсон.===Джулия Робинсон исследовала вопрос о том, является ли диофантовым множество, состоящее из троек :  <tex>\left \langle a, b, c= a^b\right \rangle</tex> Найти диофантово представление для операции возведения в степень ей не удалось, но она нашла достаточное условие для его существования: <tex>\left \langle a, b \right \rangle\in\mathbb{M}\Leftrightarrow \exists x_1, x_2,\ldots , x_n\</tex> <tex>\left \{ P(a, b, x_1, x_2, \ldots , x_n)=0 \right \}</tex> Его определяет отношение <tex>J(a,b)</tex> со следующими свойствами:*для любых <tex>a</tex> и <tex>b</tex> из <tex>J(a,b)</tex> следует, что <tex>a < b^b</tex>; *для любого <tex>k</tex> существуют <tex>a</tex> и <tex>b</tex>, удовлетворяющие <tex>J(a,b)</tex> и такие, что <tex>a > b^k</tex>. Джулия Робинсон назвала отношения, обладающие этими двумя свойствами, отношениями экспоненциального роста; сейчас такие отношения носят также имя ''предикатов Джулии Робинсон''. В 1958 году М. Дэвис и Х. Патнем опубликовали работу, в которой они рассмотрели класс так называемых экспоненциально-диофантовых уравнений.Такие уравнения имеют вид:  <tex>E_1(x_1,x_2,\ldots ,x_n) = E_2(x_1,x_2,\ldots ,x_n)</tex>,  где <tex>E_1</tex> и <tex>E_2</tex> — выражения, построенные из <tex>x_1, x_2,\ldots , x_m</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> было получено экспоненциально - диофантово представление для любого перечислимого множества: <tex>\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow \exists x_1, x_2,\ldots , x_n\</tex> <tex>\left \{E_1(a_1,a_2,\ldots ,a_m,x_1,x_2,\ldots ,x_n) = E_2(a_1,a_2,\ldots ,a_m,x_1,x_2,\ldots ,x_m)\right \}</tex> Одним из следствий работы стала возможность сведения любого показательно-диофантова уравнения к экспоненциально-диофантову уравнению с фиксированным числом переменных.Чтобы перенести результат Дэвиса, Патнема и Робинсон на обычные диофантовы уравнения, нужно было доказать, что множество, состоящее из троек <tex>\left \langle a, b, c= a^b\right \rangle</tex>, является диофантовым. Тогда стало бы возможным ценой введения дополнительных неизвестных перевести экпоненциально-диофантово представление в диофантово представление:<tex>a, b, c= a^b\Leftrightarrow \exists x_1,x_2,\ldots ,x_n \left \{ P(a, b,c, x_1, x_2, \ldots , x_n)=0\right \} </tex> Джулия Робинсон показала, что для этого достаточно построить конкретное уравнение <tex>P(a, b, x_1, x_2, \ldots , x_n)=0 </tex>, *недопускающее решение с <tex>a>b^b</tex>; *для каждого <tex>k</tex> имеющее решение с <tex>a>b^k</tex>. === Вклад Ю.В. Матиясевича===Такого рода уравнение удалось построить Ю.В. Матеясевичу в 1970 году. Обратившись к рассмотрению последовательности Фибоначчи, Матиясевич заметил, что если за <tex>b</tex> взять половину номера четного члена последовательности Фибоначчи, а за <tex>a</tex> — сам член, то неравенство <tex>a>b^b</tex> будет всегда неверно; для любого <tex>k</tex> можно найти такой четный член последовательности, что неравенство <tex>a>b^k</tex> будет верно. Это обстоятельство иллюстрируется приведенной ниже таблицей (в ней выделены те клетки, в которых числа <tex>b^k</tex> оказываются меньше соответствующих чисел <math>a</math>).  {| border="1" class="wikitable" width="20%" style="color: black; background-color:#ffffcc;" cellpadding="10"; float: left;" !Номер члена последовательности Фибоначчи! 0! 1! 2! 3! 4! 5! 6! 7! 8! 9! 10! 11! 12! 13! 14|-!Член последовательности Фибоначчи <tex>a</tex>|align="center"|<tex>0</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>2</tex>|align="center"|<tex>3</tex>|align="center"|<tex>5</tex>|align="center"|<tex>8</tex>|align="center"|<tex>13</tex>|align="center"|<tex>21</tex>|align="center"|<tex>34</tex>|align="center"|<tex>55</tex>|align="center"|<tex>89</tex>|align="center"|<tex>144</tex>|align="center"|<tex>233</tex>|align="center"|<tex>377</tex>|-!Половина номера четного члена последовательности <tex>b</tex>|align="center"|<tex>0</tex>||align="center"|<tex>1</tex>||align="center"|<tex>2</tex>||align="center"|<tex>3</tex>||align="center"|<tex>4</tex>||align="center"|<tex>5</tex>||align="center"|<tex>6</tex>||align="center"|<tex>7</tex>|-!<tex>b^b</tex>|align="center"|<tex>1</tex>||align="center"|<tex>1</tex>||align="center"|<tex>4</tex>||align="center"|<tex>27</tex>||align="center"|<tex>64</tex>||align="center"|<tex>3125</tex>||align="center"|<tex>47256</tex>||align="center"|<tex>823649</tex>|-align="center" ! <tex>b^0</tex>|align="center"|<tex>1</tex>||align="center"|<tex>1</tex>||style="background:#ffcc00"|<tex>1</tex>||style="background:#ffcc00"|<tex>1</tex>||style="background:#ffcc00"|<tex>1</tex>||style="background:#ffcc00"|<tex>1</tex>||style="background:#ffcc00"|<tex>1</tex>||style="background:#ffcc00"|<tex>1</tex>|-align="center"! <tex>b^1</tex>|align="center"|<tex>0</tex>||align="center"|<tex>1</tex>||style="background:#ffcc00"|<tex>2</tex>||style="background:#ffcc00"|<tex>3</tex>||style="background:#ffcc00"|<tex>4</tex>||style="background:#ffcc00"|<tex>5</tex>||style="background:#ffcc00"|<tex>6</tex>||style="background:#ffcc00"|<tex>7</tex>|-align="center"! <tex>b^2</tex>|align="center"|<tex>0</tex>||align="center"|<tex>1</tex>||align="center"|<tex>4</tex>||align="center"|<tex>9</tex>||style="background:#ffcc00"|<tex>16</tex>||style="background:#ffcc00"|<tex>25</tex>||style="background:#ffcc00"|<tex>36</tex>||style="background:#ffcc00"|<tex>49</tex>|-align="center"! <tex>b^3</tex>|align="center"|<tex>0</tex>||align="center"|<tex>1</tex>||align="center"|<tex>8</tex>||align="center"|<tex>27</tex>||align="center"|<tex>64</tex>||align="center"|<tex>125</tex>||align="center"|<tex>216</tex>||style="background:#ffcc00"|<tex>343</tex>|-|}Далее Матеясевич рассмотрел последовательность, состоящую из четных членов первоначальной последовательности. Оставалось построить уравнение, такое, что <tex>P(a,b,x_1,\ldots ,x_k)=0</tex>, которое имело бы натуральное решение тогда и только тогда, когда <tex>b=\varphi_a</tex>, далее сослаться на описанный выше результат Джулии Робинсон. Для этого достаточно было построить систему диофантовых уравнений <tex>P_1=0,\ldots,P_n=0</tex> в переменных <tex>a,b,x_1,\ldots ,x_k</tex>, имеющую решение тогда и только тогда, когда <tex>b=\varphi_a</tex>. Такая система имеет в точнсти те же решения, что и единственное уравнение <tex>P_1^2+\ldots +P_n^2=0</tex>.Матиясевич получил требуемую систему в виде: <tex>1)\quad b+(z-1)=a</tex> <tex>2)\quad a+u=l</tex> <tex>3) \quad l^2-lk-k^2=1</tex> <tex>4)\quad g^2-gh-h^2=1</tex> <tex>5) \quad l^2c=g</tex> <tex>6) \quad ld=r-2</tex> <tex>7) \quad (2h+g)e=r-3</tex> <tex>8) \quad x^2-rxy+y^2=1</tex> <tex>9) \quad lp=x-b</tex> <tex>10)\quad(2h+g)q=x-a</tex>  Если возвести обе части всех этих уравнений в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система.  В результате совместной работы Дэвиса, Робинсон, Патнема, Матиясевича было доказано, что по заданию перечислимого множества в любой стандартнойформе можно построить его диофантово представление:* построить арифметическую формулу со многими ограниченными кванторами общности;* преобразовать эту формулу в нормальную форму Дейвиса с одним ограниченным квантором общности; * устранить этот ограниченный квантор общности ценой перехода к экспоненциально-диофантовым уравнениям;* устранить возведение в степень. Таким образом, была доказана правильность гипотезы Мартина Дэвиса, которая стала называться DPRM-теоремой. Из этой теоремы следует, что десятая проблема Гиль­берта является неразрешимой. == См. также ==* [[Неразрешимость исчисления предикатов первого порядка]]* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]* [[Неразрешимость задачи об эквивалентности КС-грамматик]]== Примечания == <references />==Источники информации==*Матиясевич Ю.В. Десятая проблема Гильберта. — М., Физматлит, 1993 — Математическая логика и основания математики*Проблемы Гильберта. Сборник под редакцией П.С. Александрова, М., Наука, 1969 г.*Ю. В. Матиясевич. Диофантовы множества. — УМН, 1972, том 27, выпуск 5(167), — с. 185–222*[http://kvant.ras.ru/1970/07/o_reshenii_desyatoj_problemy_g.htm П. Варпаховский, А. Н. Колмогоров О решении десятой проблемы Гильберта "молит о доказательстве неразрешимости", журнал Квант — 1970 — № 7. — С. 38—44]*[https://www.lektorium.tv/lecture/12974 Лекции Ю.В.Матиясевича в Computer Science клубе при ПОМИ РАН][[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Примеры неразрешимых задач]]