Неразрешимость проблемы существования решения диофантова уравнения в целых числах

Материал из Викиконспекты
Версия от 14:16, 3 декабря 2016; 188.143.145.59 (обсуждение) (→‎Теорема о неразрешимости десятой проблемы Гильберта)
Перейти к: навигация, поиск

В 1900 году в Париже на втором Международном Конгрессе математиков выдающийся математик Давид Гильберт выступил с докладом, который назывался «Математические проблемы». Десятая из двадцати трех обозначенных в докладе проблем была сформулирована Гильбертом так:

Задача:
Решение проблемы разрешимости для произвольного диофантова уравнения. Пусть дано произвольное диофантово уравнение с произвольным числом неизвестных и целыми рациональными коэффициентами; требуется указать общий метод, следуя которому можно было бы в конечное число шагов узнать, имеет ли данное уравнение решение в целых рациональных числах или нет.


Диофантовы уравнения

Определение:
Диофантово уравнение (англ. diophantine equation) имеет вид [math]P(x_1\ldots x_n)=0[/math], где [math]P[/math] — многочлен с целыми коэффициентами. [math](1)[/math]

Примеры диофантовых уравнений

  • [math]x^n + y^n = z^n[/math]:
    • При [math]n=2[/math] решениями этого уравнения являются пифагоровы тройки.
    • согласно Великой теореме Ферма это уравнение не имеет ненулевых целых решений при [math]n\gt 2[/math].
  • [math]x^2 - n y^2 = 1[/math], где параметр [math]n[/math] не является точным квадратом — уравнение Пелля.
  • [math]x^z - y^t = 1[/math], где [math]z, t\gt 1[/math], — уравнение Каталана.
  • [math]\sum_{i=0}^n a_i x^i y^{n-i} = c[/math] при [math]n\ge 3[/math] и [math]c\ne 0[/math] — уравнение Туэ.

Диофант искал решение этих уравнений в рациональных числах, Гильберт спрашивал про решение диофантовых уравнений в целых числах.

В современной терминологии десятая проблема Гильберта является примером массовой проблемы [1]. Массовая проблема состоит из счетного количества вопросов на каждый из которых нужно дать ответ — да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.

Теорема о неразрешимости десятой проблемы Гильберта

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

Таким образом, можно говорить об отрицательном решении десятой проблемы Гильберта. Доказательство неразрешимости этой проблемы вытекает из тезиса Черча и следующих двух теорем:

Теорема:
Существует перечислимое, но неразрешимое множество натуральных чисел [2].
Теорема (DPRM-теорема):
Понятия «диофантово множество» и «перечислимое множество» совпадают.

Аббревиатура в названии последней теоремы образована из первых букв фамилий математиков Мартина Девиса (англ. Martin Davis), Хилари Патнэма (англ. Hilary Putnam), Джулии Робинсон (англ. Julia Robinson) и Юрия Матиясевича. Подробное доказательство неразрешимости десятой проблемы Гильберта можно прочитать здесь [3] [4]. Ниже приведены основные идеи доказательства.

Пусть дано множество [math]M[/math] натуральных чисел и нужно найти алгоритм, который по каждому натуральному [math]n[/math] определяет, принадлежит это [math]n[/math] множеству [math]M[/math] или нет.

В соответствии с тезисом Черча, такой алгоритм существует тогда и только тогда, когда множество [math]M[/math] разрешимо.

Для отрицательного решения десятой проблемы Гильберта достаточно доказать диофантовость каждого перечислимого множества, то есть по каждому перечислимому множеству [math]M[/math] уметь строить такое диофантово уравнение, [math]P(y,x_1\ldots x_k)=0[/math], которое имело бы натуральные решения [math]x_1\ldots x_k[/math] для всех [math]y[/math], принадлежащих [math]M[/math] и только для таких [math]y[/math].

Тогда, взяв в качестве [math]M[/math] перечислимое, но неразрешимое множество, можно было бы получить, что для соответствующего уравнения [math]P(y,x_1\ldots x_k)=0[/math] нет общего алгоритма, который по каждому натуральному [math]y[/math] давал бы ответ на вопрос о существовании у этого уравнения натуральных решений. Если бы этот алгоритм существовал, то можно было бы за конечное число шагов узнать, имеет ли уравнение [math]P(0,x_1\ldots x_k)=0[/math] решение, то есть принадлежит ли число [math]0[/math] множеству [math]M[/math], имеет ли уравнение [math]P(1,x_1\ldots x_k)=0[/math] решение и так далее. Получилось бы, что существует алгоритм, который по каждому натуральному [math]y[/math] за конечное число шагов определяет, принадлежит [math]y[/math] множеству [math]M[/math] или нет.

Тогда, в соответствии с тезисом Черча, множество [math]M[/math] было бы разрешимым вопреки выбору этого множества.

Этапы доказательства DPRM-теоремы

Гипотеза и нормальная форма Мартина Дэвиса

М. Дэвис перешёл от формулировки десятой проблемы Гильберта в целых числах к естественной для теории алгоритмов формулировке в целых неотрицательных числах. Для конкретного диофантова уравнения задача о нахождении целочисленных решений и задача о нахождении решений в целых неотрицательных числах — разные задачи. Однако если мы интересуемся сразу всеми уравнениями (как, например, в 10-й проблеме Гильберта), то эти две задачи совпадают. Действительно, если рассмотреть систему уравнений [math](2)[/math]

[math] \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. [/math],

то станет понятно, что:

  • любое решение системы [math](2)[/math] в произвольных целых числах содержит решение уравнения [math](1)[/math] в неотрицательных целых числах;
  • для любого решения уравнения [math](1)[/math] в неотрицательных целых числах [math]x_1,x_2,\ldots , x_n[/math] найдутся целочисленные значения [math]y_{1,\;1},\ldots , y_{n,\;4}[/math], дающие решение системы [math](2)[/math] , так как, согласно известной теореме Лагранжа, каждое неотрицательное целое число представимо в виде суммы квадратов четырёх целых чисел.

Система уравнений [math](2)[/math] может быть свёрнута в одно уравнение : [math]E(x_1, x_2, \ldots , x_n, y_{1,\;1}, \ldots , y_{n,\;4})[/math], разрешимое в целых числах тогда и только тогда, когда исходное уравнение [math](1)[/math] разрешимо в неотрицательных целых числах.

Утверждение:
Таким образом, массовая проблема распознавания разрешимости диофантовых уравнений в целых числах сводится к массовой проблеме распознавания разрешимости диофантовых уравнений в целых неотрицательных числах.

Наряду с отдельными диофантовыми уравнениями, Дэвис рассмотрел семейства диофантовых уравнений вида: [math]P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0[/math], где [math]P[/math] – многочлен с целыми коэффициентами, [math]a_1, a_2, \ldots , a_m\in\mathbb{Z}[/math] — параметры, [math]x_1, x_2,\ldots , x_n\in\mathbb{Z}[/math] — переменные. Каждое такое семейство определяет некоторое множество [math]M[/math] тех значений параметров, при которых уравнение разрешимо относительно переменных [math]x_1, x_2,\ldots , x_n[/math] :

[math]\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow x_1, x_2,\ldots , x_n\[/math]

[math]\left \{ P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0 \right \}[/math]

Такие множества называются диофантовыми.

Исследования Мартина Дэвиса, направленные на доказательство неразрешимости десятой проблемы Гильберта, привели его к постановке задачи, когда описано некоторое множество и требуется узнать, является ли оно диофантовым. В простейших случаях диофантовость множества очевидна — ясно, например, что диофантовым является множество всех положительных нечетных чисел. Однако совсем нелегко ответить на такие вопросы, как: «диофантово ли множество всех степеней числа [math]2[/math]?», «диофантово ли множество всех простых чисел?», «диофантово ли множество всех совершенных чисел?» С первого взгляда кажется, что на эти вопросы следует дать отрицательный ответ. Тем не менее все эти множества являются диофантовыми. Приведем примеры диофантовых множеств:

  • множество всех полных квадратов, представлено уравнением [math]a-x^2=0[/math];
  • множество всех составных чисел, представлено уравнением [math]a-(x_1+2)(x_2+2)=0[/math];
  • множество всех нестепеней числа [math]2[/math], представлено уравнеием [math]a-(2x_1+3)x_2=0[/math].

Для доказательства неразрешимости десятой проблемы Гильберта нужно было лишь показать диофантовость любого перечислимого множества, то есть нужно показать возможность построения уравнения, которое имело бы натуральные корни [math]x_1,x_2,\ldots , x_n[/math] только при всех [math]\left \langle a_1, a_2, \ldots , a_m\right \rangle[/math], принадлежащих этому перечислимому множеству. Исходя из этого, Дэвис сформулировал следующую гипотезу:

Гипотеза (Мартина Дэвиса):
Понятия диофантового и перечислимого множества совпадают. Это значит, что множество диофантово тогда и только тогда, когда оно перечислимо.

Доказать гипотезу Дэвису не удалось, но он получил близкий к доказательству результат, показав [5], что любое перечислимое множество можно представить в виде, названном нормальной формой Дэвиса:

[math]\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow \exists z \quad \forall y \lt z \quad \exists x_1, x_2,\ldots , x_n\[/math]

[math]\left \{ P(a_1, a_2, \ldots , a_m, x_1, x_2, \ldots , x_n)=0 \right \}[/math]

Предикат Робинсон. Совместный результат М. Дэвиса и Х. Патнема и Д. Робинсон.

Джулия Робинсон исследовала вопрос о том, является ли диофантовым множество, состоящее из троек :

[math]\left \langle a, b, c= a^b\right \rangle[/math]

Найти диофантово представление для операции возведения в степень ей не удалось, но она нашла достаточное условие для его существования:

[math]\left \langle a, b \right \rangle\in\mathbb{M}\Leftrightarrow \exists x_1, x_2,\ldots , x_n\[/math]

[math]\left \{ P(a, b, x_1, x_2, \ldots , x_n)=0 \right \}[/math]

Его определяет отношение [math]J(a,b)[/math] со следующими свойствами:

  • для любых [math]a[/math] и [math]b[/math] из [math]J(a,b)[/math] следует, что [math]a \lt b^b[/math];
  • для любого [math]k[/math] существуют [math]a[/math] и [math]b[/math], удовлетворяющие [math]J(a,b)[/math] и такие, что [math]a \gt b^k[/math].

Джулия Робинсон назвала отношения, обладающие этими двумя свойствами, отношениями экспоненциального роста; сейчас такие отношения носят также имя предикатов Джулии Робинсон.

В 1958 году М. Дэвис и Х. Патнем опубликовали работу, в которой они рассмотрели класс так называемых экспоненциально-диофантовых уравнений.Такие уравнения имеют вид:

[math]E_1(x_1,x_2,\ldots ,x_n) = E_2(x_1,x_2,\ldots ,x_n)[/math],

где [math]E_1[/math] и [math]E_2[/math] — выражения, построенные из [math]x_1, x_2,\ldots , x_m[/math] и конкретных натуральных чисел с помощью сложения, умножения и возведения в степень.

В 1961 году в совместной работе Робинсон, Дэвиса и Патмена [6] было получено экспоненциально - диофантово представление для любого перечислимого множества:

[math]\left \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow \exists x_1, x_2,\ldots , x_n\[/math]

[math]\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 \}[/math]

Одним из следствий работы стала возможность сведения любого показательно-диофантова уравнения к экспоненциально-диофантову уравнению с фиксированным числом переменных. Чтобы перенести результат Дэвиса, Патнема и Робинсон на обычные диофантовы уравнения, нужно было доказать, что множество, состоящее из троек [math]\left \langle a, b, c= a^b\right \rangle[/math], является диофантовым. Тогда стало бы возможным ценой введения дополнительных неизвестных перевести экпоненциально-диофантово представление в диофантово представление: [math]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 \} [/math]

Джулия Робинсон показала, что для этого достаточно построить конкретное уравнение

[math]P(a, b, x_1, x_2, \ldots , x_n)=0 [/math],

  • недопускающее решение с [math]a\gt b^b[/math];
  • для каждого [math]k[/math] имеющее решение с [math]a\gt b^k[/math].

Вклад Ю.В. Матиясевича

Такого рода уравнение удалось построить Ю.В. Матеясевичу в 1970 году. Обратившись к рассмотрению последовательности Фибоначчи, Матиясевич заметил, что если за [math]b[/math] взять половину номера четного члена последовательности Фибоначчи, а за [math]a[/math] — сам член, то неравенство [math]a\gt b^b[/math] будет всегда неверно; для любого [math]k[/math] можно найти такой четный член последовательности, что неравенство [math]a\gt b^k[/math] будет верно. Это обстоятельство иллюстрируется приведенной ниже таблицей (в ней выделены те клетки, в которых числа [math]b^k[/math] оказываются меньше соответствующих чисел [math]a[/math]).

Номер члена последовательности Фибоначчи 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Член последовательности Фибоначчи [math]a[/math] [math]0[/math] [math]1[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]5[/math] [math]8[/math] [math]13[/math] [math]21[/math] [math]34[/math] [math]55[/math] [math]89[/math] [math]144[/math] [math]233[/math] [math]377[/math]
Половина номера четного члена последовательности [math]b[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] [math]5[/math] [math]6[/math] [math]7[/math]
[math]b^b[/math] [math]1[/math] [math]1[/math] [math]4[/math] [math]27[/math] [math]64[/math] [math]3125[/math] [math]47256[/math] [math]823649[/math]
[math]b^0[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math]
[math]b^1[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] [math]5[/math] [math]6[/math] [math]7[/math]
[math]b^2[/math] [math]0[/math] [math]1[/math] [math]4[/math] [math]9[/math] [math]16[/math] [math]25[/math] [math]36[/math] [math]49[/math]
[math]b^3[/math] [math]0[/math] [math]1[/math] [math]8[/math] [math]27[/math] [math]64[/math] [math]125[/math] [math]216[/math] [math]343[/math]

Далее Матеясевич рассмотрел последовательность, состоящую из четных членов первоначальной последовательности. Оставалось построить уравнение, такое, что [math]P(a,b,x_1,\ldots ,x_k)=0[/math], которое имело бы натуральное решение тогда и только тогда, когда [math]b=\varphi_a[/math], далее сослаться на описанный выше результат Джулии Робинсон. Для этого достаточно было построить систему диофантовых уравнений [math]P_1=0,\ldots,P_n=0[/math] в переменных [math]a,b,x_1,\ldots ,x_k[/math], имеющую решение тогда и только тогда, когда [math]b=\varphi_a[/math]. Такая система имеет в точнсти те же решения, что и единственное уравнение [math]P_1^2+\ldots +P_n^2=0[/math]. Матиясевич получил требуемую систему в виде:

[math]1)\quad b+(z-1)=a[/math]

[math]2)\quad a+u=l[/math]

[math]3) \quad l^2-lk-k^2=1[/math]

[math]4)\quad g^2-gh-h^2=1[/math]

[math]5) \quad l^2c=g[/math]

[math]6) \quad ld=r-2[/math]

[math]7) \quad (2h+g)e=r-3[/math]

[math]8) \quad x^2-rxy+y^2=1[/math]

[math]9) \quad lp=x-b[/math]

[math]10)\quad(2h+g)q=x-a[/math]


Если возвести обе части всех этих уравнений в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система.

В результате совместной работы Дэвиса, Робинсон, Патнема, Матиясевича было доказано, что по заданию перечислимого множества в любой стандартной форме можно построить его диофантово представление:

  • построить арифметическую формулу со многими ограниченными кванторами общности;
  • преобразовать эту формулу в нормальную форму Дейвиса с одним ограниченным квантором общности;
  • устранить этот ограниченный квантор общности ценой перехода к экспоненциально-диофантовым уравнениям;
  • устранить возведение в степень.

Таким образом, была доказана правильность гипотезы Мартина Дэвиса, которая стала называться DPRM-теоремой. Из этой теоремы следует, что десятая проблема Гиль­берта является неразрешимой.

См. также

Примечания

  1. ↑ Матиясевич Ю.В. Десятая проблема Гильберта. — М., Физматлит, 1993 — Математическая логика и основания математики — с.8
  2. ↑ Н. К. Верещагин, А. Шень, Вычислимые функции. — М. Издательство МЦНМО, 2008 — с.22
  3. ↑ Davis Martin Hilbert's tenth problem is unsolvable. — Amer. tex. Monthly., V.80, №3 1973 — p.233–269
  4. ↑ Манин Ю. И. Вычислимое и невычислимое. — М., Советское Радио, 1980 — c. 46-64
  5. ↑ M. Davis. Arithmetical problems and recursively enumerable predicates. — The Journal of Symbolic Logic 18 (1), 1953 — p. 33–41
  6. ↑ Martin Davis, Hilary Putnam, Julia Robinson The decision problem for exponential Diophantine equations. — Annals of Mathematics — 1961. — Vol. 74, № 3 — p. 425—436

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Неразрешимость_проблемы_существования_решения_диофантова_уравнения_в_целых_числах&oldid=56720»