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

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 40 промежуточных версий этого же участника)
Строка 4: Строка 4:
 
}}
 
}}
  
−
==Этапы доказательства неразрешимости десятой проблемы Гильберта==
+
==Диофантовы уравнения==
 
{{Определение
 
{{Определение
−
|definition='''Диофантово уравнение''' имеет вид
+
|definition='''Диофантово уравнение''' (англ. ''diophantine equation'') имеет вид
 
<tex>P(x_1\ldots x_n)=0</tex>, где <tex>P</tex> {{---}} многочлен с целыми коэффициентами. <tex>(1)</tex>
 
<tex>P(x_1\ldots x_n)=0</tex>, где <tex>P</tex> {{---}} многочлен с целыми коэффициентами. <tex>(1)</tex>
 
}}
 
}}
 +
=== Примеры диофантовых уравнений ===
 +
Ниже приведены примеры наиболее известных частных случаев диофантовых уравнений:
 +
*<tex>x^n + y^n = z^n</tex>,
 +
:*при <tex>n=2</tex> решениями этого уравнения (обобщенного уравнения Пифагора) являются пифагоровы тройки,
 +
:* согласно Великой теореме Ферма это уравнение не имеет ненулевых целых решений при <tex>n>2</tex>.
 +
*уравнение Пелля;
 +
: <tex>x^2 - n y^2 = 1</tex>, где параметр <tex>n</tex> не является точным квадратом;
 +
*уравнение Каталана:
 +
:<tex>x^z - y^t = 1</tex>, где <tex>z, t>1</tex>;
 +
*уравнение Туэ:
 +
: <tex>\sum_{i=0}^n a_i x^i y^{n-i} = c</tex> при <tex>n \geqslant  3</tex> и <tex>c\ne 0</tex>.
 
Диофант искал решение этих уравнений в рациональных числах, Гильберт спрашивал про решение диофантовых уравнений в целых числах.
 
Диофант искал решение этих уравнений в рациональных числах, Гильберт спрашивал про решение диофантовых уравнений в целых числах.
  
−
В современной терминологии десятая проблема Гильберта является примером массовой проблемы. Массовая проблема состоит из счетного количества вопросов  на каждый из которых нужно дать ответ {{---}} да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех  «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.
+
В современной терминологии десятая проблема Гильберта является примером ''массовой проблемы'' <ref>Матиясевич Ю.В. Десятая проблема Гильберта. — М., Физматлит, 1993 {{---}} Математическая логика и основания математики {{---}} с.8</ref>.  Массовая проблема состоит из счетного количества вопросов  на каждый из которых нужно дать ответ {{---}} да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех  «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.
  
 +
==Теорема о неразрешимости десятой проблемы Гильберта==
 
{{Теорема
 
{{Теорема
 
|author=Неразрешимость десятой проблемы Гильберта
 
|author=Неразрешимость десятой проблемы Гильберта
Строка 18: Строка 30:
 
}}
 
}}
 
Таким образом, можно говорить об отрицательном решении десятой проблемы Гильберта.
 
Таким образом, можно говорить об отрицательном решении десятой проблемы Гильберта.
 +
Доказательство неразрешимости этой проблемы вытекает из тезиса Черча и следующих двух теорем:
 +
{{Теорема
 +
 +
|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> разрешимо.  
−
 
−
===Некотрые определения и теорема===
 
−
{{Определение
 
  
−
|definition=Множество <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>.  
−
}}
 
−
{{Определение
 
  
−
|definition=Множество <tex>M</tex> называется разрешимым, если оно перечислимо вместе со своим дополнением <tex>\mathbb N-M</tex>, где <tex>\mathbb N</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> или нет.
−
}}
 
−
{{Теорема
 
  
−
|statement=Существует перечислимое, но неразрешимое множество натуральных чисел.}}
+
:Тогда, в соответствии с тезисом Черча, множество <tex>M</tex> было бы разрешимым вопреки выбору этого множества.
−
Пусть дано множество <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>
+
===Гипотеза и нормальная форма Мартина Дэвиса===
 +
М. Дэвис перешёл от формулировки десятой проблемы Гильберта в целых числах к естественной для теории алгоритмов формулировке в целых неотрицательных числах.
 +
Для конкретного диофантова уравнения задача о нахождении целочисленных решений и задача о нахождении решений в целых неотрицательных числах {{---}}  разные задачи. Однако если мы интересуемся сразу всеми уравнениями (как, например, в 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> \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
Строка 63: Строка 84:
 
Такие множества называются ''диофантовыми''.
 
Такие множества называются ''диофантовыми''.
  
−
Исследования Мартина Дэвиса, направленные на доказательство неразрешимости десятой проблемы Гильберта, привели его к постановке задачи, когда описано некоторое множество и требуется узнать, является ли оно диофантовым. В простейших случаях диофантовость множества очевидна {{---}} ясно, например, что диофантовым является множество всех положительных нечетных чисел. Однако совсем нелегко ответить на такие естественные вопросы, как «диофантово ли множество всех степеней числа <tex>2</tex>?», «диофантово ли множество всех простых чисел?», «диофантово ли множество всех совершенных чисел?» С первого взгляда кажется, что на эти вопросы следует дать отрицательный ответ. Тем не менее все эти множества являются диофантовыми. Приведем примеры диофантовых множеств:
+
Исследования Мартина Дэвиса, направленные на доказательство неразрешимости десятой проблемы Гильберта, привели его к постановке задачи, когда описано некоторое множество и требуется узнать, является ли оно диофантовым. В простейших случаях диофантовость множества очевидна {{---}} ясно, например, что диофантовым является множество всех положительных нечетных чисел. Однако совсем нелегко ответить на такие вопросы, как: «диофантово ли множество всех степеней числа <tex>2</tex>?», «диофантово ли множество всех простых чисел?», «диофантово ли множество всех совершенных чисел?» С первого взгляда кажется, что на эти вопросы следует дать отрицательный ответ. Тем не менее все эти множества являются диофантовыми. Приведем примеры диофантовых множеств:
 
*множество всех полных квадратов, представлено уравнением <tex>a-x^2=0</tex>;
 
*множество всех полных квадратов, представлено уравнением <tex>a-x^2=0</tex>;
 
*множество всех составных чисел, представлено уравнением <tex>a-(x_1+2)(x_2+2)=0</tex>;
 
*множество всех составных чисел, представлено уравнением <tex>a-(x_1+2)(x_2+2)=0</tex>;
Строка 73: Строка 94:
 
|statement=Понятия диофантового и перечислимого множества совпадают. Это значит, что множество диофантово тогда и только тогда, когда оно перечислимо.
 
|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 \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>
Строка 80: Строка 101:
  
 
===Предикат Робинсон. Совместный результат М. Дэвиса и Х. Патнема и Д. Робинсон.===
 
===Предикат Робинсон. Совместный результат М. Дэвиса и Х. Патнема и Д. Робинсон.===
−
Основополагающий вклад в решение десятой проблемы Гильберта внесла американский математик Джулия Робинсон.  Ее учитель, Альфред Тарский, предположил, что даже множество всех степеней числа <tex>2</tex> не является диофантовым. Джулия Робинсон исследовала вопрос о том, является ли диофантовым множество, состоящее из троек :  
+
Джулия Робинсон исследовала вопрос о том, является ли диофантовым множество, состоящее из троек :  
  
 
<tex>\left \langle a, b, c= a^b\right \rangle</tex>
 
<tex>\left \langle a, b, c= a^b\right \rangle</tex>
Строка 101: Строка 122:
 
где <tex>E_1</tex> и <tex>E_2</tex> — выражения, построенные из <tex>x_1, x_2,\ldots , x_m</tex> и конкретных натуральных чисел с помощью сложения, умножения и возведения в степень.
 
где <tex>E_1</tex> и <tex>E_2</tex> — выражения, построенные из <tex>x_1, x_2,\ldots , x_m</tex> и конкретных натуральных чисел с помощью сложения, умножения и возведения в степень.
  
−
В 1961 году в совместной работе  Робинсон, Дэвиса и Патмена было получено экспоненциально - диофантово представление для любого перечислимого множества:
+
В 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 \langle a_1, a_2, \ldots , a_m\right \rangle\in\mathbb{M}\Leftrightarrow  \exists  x_1, x_2,\ldots , x_n\</tex>
Строка 116: Строка 137:
 
*недопускающее решение с <tex>a>b^b</tex>;  
 
*недопускающее решение с <tex>a>b^b</tex>;  
 
*для каждого <tex>k</tex> имеющее решение с <tex>a>b^k</tex>.
 
*для каждого <tex>k</tex> имеющее решение с <tex>a>b^k</tex>.
 +
 
=== Вклад Ю.В. Матиясевича===
 
=== Вклад Ю.В. Матиясевича===
 
Такого рода уравнение удалось построить Ю.В. Матеясевичу в 1970 году. Обратившись к рассмотрению последовательности Фибоначчи, Матиясевич заметил, что если за <tex>b</tex> взять половину номера четного члена последовательности Фибоначчи, а за <tex>a</tex> — сам член, то неравенство <tex>a>b^b</tex> будет всегда неверно;  
 
Такого рода уравнение удалось построить Ю.В. Матеясевичу в 1970 году. Обратившись к рассмотрению последовательности Фибоначчи, Матиясевич заметил, что если за <tex>b</tex> взять половину номера четного члена последовательности Фибоначчи, а за <tex>a</tex> — сам член, то неравенство <tex>a>b^b</tex> будет всегда неверно;  
Строка 262: Строка 284:
 
Матиясевич получил требуемую систему в виде:
 
Матиясевич получил требуемую систему в виде:
  
−
<tex>1)b+(z-1)=a</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>2)a+u=l</tex>
+
<tex>6) \quad ld=r-2</tex>
  
−
<tex>3)l^2-lk-k^2=1</tex>
+
<tex>7) \quad (2h+g)e=r-3</tex>
  
−
<tex>4)g^2-gh-h^2=1</tex>
+
<tex>8) \quad x^2-rxy+y^2=1</tex>
  
−
<tex>5)l^2c=g</tex>
+
<tex>9) \quad lp=x-b</tex>
  
−
<tex>6)ld=r-2</tex>
+
<tex>10)\quad(2h+g)q=x-a</tex>
  
−
<tex>7)(2h+g)e=r-3</tex>
 
  
−
<tex>8)x^2-rxy+y^2=1</tex>
+
Если возвести обе части всех этих уравнений в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система.
  
−
<tex>9)lp=x-b</tex>
+
В результате совместной работы Дэвиса, Робинсон, Патнема, Матиясевича было доказано, что по заданию перечислимого множества в любой стандартной
 +
форме можно построить его диофантово представление:
 +
*  построить арифметическую формулу со многими ограниченными кванторами общности;
 +
*  преобразовать эту формулу в нормальную форму Дейвиса с одним ограниченным квантором общности;
  
−
<tex>10)(2h+g)q=x-a</tex>
+
*  устранить этот ограниченный квантор общности ценой перехода к экспоненциально-диофантовым уравнениям;
 +
*  устранить возведение в степень.
  
 +
Таким образом, была доказана правильность гипотезы Мартина Дэвиса, которая стала называться DPRM-теоремой. Из этой теоремы следует, что десятая проблема Гиль­берта является неразрешимой.
  
−
Если возвести обе части всех этих уравнений в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система. Таким образом,
 
−
теорема о неразрешимости десятой проблемы Гильберта была доказана.
 
 
== См. также ==
 
== См. также ==
 
* [[Неразрешимость исчисления предикатов первого порядка]]
 
* [[Неразрешимость исчисления предикатов первого порядка]]
Строка 291: Строка 323:
 
* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]
 
* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]
 
* [[Неразрешимость задачи об эквивалентности КС-грамматик]]
 
* [[Неразрешимость задачи об эквивалентности КС-грамматик]]
 +
== Примечания ==
  
 +
<references />
 
==Источники информации==
 
==Источники информации==
−
*Матиясевич Ю.В. Десятая проблема Гильберта. — М.: Физматлит, 1993. - Математическая логика и основания математики.
+
*Матиясевич Ю.В. Десятая проблема Гильберта. — М., Физматлит, 1993 — Математическая логика и основания математики
−
*Проблемы Гильберта, Сборник под редакцией П. С. Александрова, М., Наука, 1969 г.
+
*Проблемы Гильберта. Сборник под редакцией П.С. Александрова, М., Наука, 1969 г.
−
*Ю. В. Матиясевич. Диофантовы множества. —  УМН, 1972, том 27, выпуск 5(167), с. 185–222
+
*Ю. В. Матиясевич. Диофантовы множества. —  УМН, 1972, том 27, выпуск 5(167), —  с. 185–222
−
*[http://kvant.ras.ru/1970/07/o_reshenii_desyatoj_problemy_g.htm П. Варпаховский, А. Н. Колмогоров О решении десятой проблемы Гильберта // Квант. — 1970. — № 7. — С. 38—44.]
+
*[http://kvant.ras.ru/1970/07/o_reshenii_desyatoj_problemy_g.htm П. Варпаховский, А. Н. Колмогоров О решении десятой проблемы Гильберта, журнал Квант — 1970 — № 7. — С. 38—44]
 
*[https://www.lektorium.tv/lecture/12974 Лекции Ю.В. Матиясевича в Computer Science клубе при ПОМИ РАН]
 
*[https://www.lektorium.tv/lecture/12974 Лекции Ю.В. Матиясевича в Computer Science клубе при ПОМИ РАН]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория вычислимости]]
 
[[Категория: Теория вычислимости]]
 
[[Категория: Примеры неразрешимых задач]]
 
[[Категория: Примеры неразрешимых задач]]

Версия 13:34, 5 декабря 2016

В 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 \geqslant 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=56982»