Изменения
Нет описания правки
{{Определение
|definition='''Диофантово уравнение''' имеет вид
<tex>P(x_1...\ldots x_n)=0</tex>, где <tex>P</tex> {{---}} многочлен с целыми коэффициентами. <tex>(1)</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...\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> было бы разрешимым.
===Гипотеза Мартина Дэвиса===
Для конкретного диофантова уравнения задача о нахождении целочисленных решений и задача о нахождении решений в целых неотрицательных числах — это, вообще говоря, разные задачи. Однако если мы интересуемся сразу всеми уравнениями (как, например, в 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> разрешимо в неотрицательных целых числах.
{{Утверждение
Наряду с отдельными диофантовыми уравнениями, Дэвис рассмотрел семейства диофантовых уравнений вида:
<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-(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=Мартина Дэвиса
Также Дэвис доказал, что любое перечислимое множество можно представить в виде, названном ''нормальной формой Дэвиса'':
<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 \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> со следующими свойствами:
В 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 году в совместной работе Робинсон, Дэвиса и Патмена было получено экспоненциально - диофантово представление для любого перечислимого множества:
<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>.
|-
|}
Далее Матеясевич рассмотрел последовательность, состоящую из четных членов первоначальной последовательности. Оставалось построить уравнение, такое, что <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>.
Матиясевич получил требуемую систему в виде:
