Изменения

<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>P(x_1...\ldots x_n)=0</tex>, где <tex>P</tex> {{---}} многочлен с целыми коэффициентами. <tex>(1)</tex>

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

Во времена|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> перечислимое, но [[Разрешимые (рекурсивные) языки # Примеры неразрешимых множеств |definitionнеразрешимое множество]], можно было бы получить, что для соответствующего уравнения <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> или нет.}}{{Определение

|definition=Множество :Тогда, в соответствии с тезисом Черча, множество <tex>M</tex> называется было бы разрешимым, если оно перечислимо вместе со своим дополнением <tex>\mathbb N-M</tex>, где <tex>\mathbb N</tex> {{---}} множество всех натуральных чиселвопреки выбору этого множества.}}{{Теорема

|statement=Существует перечислимое, но неразрешимое множество натуральных чисел.}}Пусть дано множество <tex>M</tex> натуральных чисел и нужно найти алгоритм, который по каждому натуральному <tex>n</tex> определяет, принадлежит это <tex>n</tex> множеству <tex>M</tex> или нет.Такой алгоритм существует тогда и только тогда, когда множество <tex>M</tex> разрешимо. Для отрицательного решения десятой проблемы Гильберта достаточно было доказать диофантовость каждого перечислимого множества, то есть по каждому перечислимому множеству <tex>M</tex> уметь строить такое диофантово уравнение, <tex>P(y,x_1...x_k)=0</tex>, которое имело бы натуральные решения <tex>x_1...x_k</tex> для всех <tex>y</tex>, принадлежащих <tex>M</tex> и только для таких <tex>y</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

*для любого решения уравнения <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>E(x_1, x_2, ...\ldots , x_n, y_{1,\;1}, ...\ldots , y_{n,\;4})</tex>,

<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>x_1,x_2,...\ldots , x_n</tex> только при всех <tex>\left \langle a_1, a_2, ...\ldots , a_m\right \rangle</tex>, принадлежащих этому перечислимому множеству. Исходя из этого, Дэвис сформулировал следующую гипотезу:

Также Дэвис доказалДоказать гипотезу Дэвису не удалось, но он получил близкий к доказательству результат, показав <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>2</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>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>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>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>26)a+u\quad ld=lr-2</tex>

<tex>37) \quad (2h+g)l^2e=r-lk-k^2=13</tex>

<tex>48)g\quad x^2-gh-hrxy+y^2=1</tex>

<tex>59)l^2c \quad lp=gx-b</tex>

<tex>610)ld\quad(2h+g)q=rx-2a</tex>

<tex>10)(2h+g)q=x* устранить этот ограниченный квантор общности ценой перехода к экспоненциально-a</tex>диофантовым уравнениям;* устранить возведение в степень.

Если возвести обе части всех этих уравнений == См. также ==* [[Неразрешимость исчисления предикатов первого порядка]]* [[Примеры неразрешимых задач: задача о выводе в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система.полусистеме Туэ|Задача о выводе в полусистеме Туэ]]* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]* [[Неразрешимость задачи об эквивалентности КС-грамматик]]== Примечания ==

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