Изменения

<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>. Массовая проблема состоит из счетного количества вопросов на каждый из которых нужно дать ответ {{---}} да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех "Математических проблем" «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.

Во времена:В соответствии с тезисом Черча, такой алгоритм существует тогда и только тогда, когда Гильберт формулировал свои проблемы, не было общего определения понятия алгоритма, однако Гильберт был оптимистом в математике, верил в разрешимость этой проблемы, в этом смысле задача была сформулирована им вполне корректно. Задача о целых решениях произвольного уравнения сводится к задаче о целых неотрицательных решениях. Далее достаточно ограничиться диофантовыми уравнениями степени не выше четвертоймножество <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>6) \quad ld=r-2</tex> <tex>7) \quad (2h+g)e=r-3</tex>

<tex>8) \quad x^2)a-rxy+uy^2=l1</tex>

<tex>39)l^2 \quad lp=x-lk-k^2=1b</tex>

<tex>410)\quad(2h+g^2-gh)q=x-h^2=1a</tex>

<tex>8)x^2* устранить этот ограниченный квантор общности ценой перехода к экспоненциально-rxy+y^2=1</tex>диофантовым уравнениям;* устранить возведение в степень.

<tex>9)lp=xТаким образом, была доказана правильность гипотезы Мартина Дэвиса, которая стала называться DPRM-b</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.]