Неразрешимость проблемы существования решения диофантова уравнения в целых числах — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 52 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
− | + | В 1900 году в Париже на втором Международном Конгрессе математиков выдающийся математик Давид Гильберт выступил с докладом, который назывался «Математические проблемы». Десятая из двадцати трех обозначенных в докладе проблем была сформулирована Гильбертом так: | |
− | |||
− | |||
− | |||
− | В 1900 году в Париже на втором Международном Конгрессе математиков выдающийся математик Давид Гильберт выступил с докладом, который назывался | ||
{{Задача | {{Задача | ||
|definition='''Решение проблемы разрешимости для произвольного диофантова уравнения.''' Пусть дано произвольное диофантово уравнение с произвольным числом неизвестных и целыми рациональными коэффициентами; требуется указать общий метод, следуя которому можно было бы в конечное число шагов узнать, имеет ли данное уравнение решение в целых рациональных числах или нет. | |definition='''Решение проблемы разрешимости для произвольного диофантова уравнения.''' Пусть дано произвольное диофантово уравнение с произвольным числом неизвестных и целыми рациональными коэффициентами; требуется указать общий метод, следуя которому можно было бы в конечное число шагов узнать, имеет ли данное уравнение решение в целых рациональных числах или нет. | ||
}} | }} | ||
− | == | + | ==Диофантовы уравнения== |
{{Определение | {{Определение | ||
− | |definition='''Диофантово уравнение''' имеет вид | + | |definition='''Диофантово уравнение''' (англ. ''diophantine equation'') имеет вид |
− | <tex>P(x_1 | + | <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=Неразрешимость десятой проблемы Гильберта | ||
Строка 22: | Строка 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> разрешимо. | ||
+ | |||
+ | :Для отрицательного решения десятой проблемы Гильберта достаточно доказать диофантовость каждого [[Перечислимые языки|перечислимого множества]], то есть по каждому перечислимому множеству <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> | ||
− | <tex> \left\{ \begin{array}{lcr}P(x_1 | + | <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>, | \end{array}\right. </tex>, | ||
Строка 40: | Строка 65: | ||
*любое решение системы <tex>(2)</tex> в произвольных целых числах содержит решение уравнения <tex>(1)</tex> в неотрицательных целых числах; | *любое решение системы <tex>(2)</tex> в произвольных целых числах содержит решение уравнения <tex>(1)</tex> в неотрицательных целых числах; | ||
− | *для любого решения уравнения <tex>(1)</tex> в неотрицательных целых числах <tex>x_1,x_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>(2)</tex> может быть свёрнута в одно уравнение : | Система уравнений <tex>(2)</tex> может быть свёрнута в одно уравнение : | ||
− | <tex>E(x_1, x_2, | + | <tex>E(x_1, x_2, \ldots , x_n, y_{1,\;1}, \ldots , y_{n,\;4})</tex>, |
разрешимое в целых числах тогда и только тогда, когда исходное уравнение <tex>(1)</tex> разрешимо в неотрицательных целых числах. | разрешимое в целых числах тогда и только тогда, когда исходное уравнение <tex>(1)</tex> разрешимо в неотрицательных целых числах. | ||
{{Утверждение | {{Утверждение | ||
Строка 50: | Строка 75: | ||
Наряду с отдельными диофантовыми уравнениями, Дэвис рассмотрел семейства диофантовых уравнений вида: | Наряду с отдельными диофантовыми уравнениями, Дэвис рассмотрел семейства диофантовых уравнений вида: | ||
− | <tex>P(a_1, a_2, | + | <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, | + | <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, | + | <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, | + | <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-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>; | ||
*множество всех нестепеней числа <tex>2</tex>, представлено уравнеием <tex>a-(2x_1+3)x_2=0</tex>. | *множество всех нестепеней числа <tex>2</tex>, представлено уравнеием <tex>a-(2x_1+3)x_2=0</tex>. | ||
Для доказательства неразрешимости десятой проблемы Гильберта нужно было лишь показать диофантовость любого перечислимого множества, | Для доказательства неразрешимости десятой проблемы Гильберта нужно было лишь показать диофантовость любого перечислимого множества, | ||
− | то есть нужно показать возможность построения уравнения, которое имело бы натуральные корни <tex>x_1,x_2, | + | то есть нужно показать возможность построения уравнения, которое имело бы натуральные корни <tex>x_1,x_2,\ldots , x_n</tex> только при всех <tex>\left \langle a_1, a_2, \ldots , a_m\right \rangle</tex>, принадлежащих этому перечислимому множеству. Исходя из этого, Дэвис сформулировал следующую гипотезу: |
{{Гипотеза | {{Гипотеза | ||
|author=Мартина Дэвиса | |author=Мартина Дэвиса | ||
|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, | + | <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, | + | <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, c= a^b\right \rangle</tex> | <tex>\left \langle a, b, c= a^b\right \rangle</tex> | ||
Строка 82: | Строка 107: | ||
Найти диофантово представление для операции возведения в степень ей не удалось, но она нашла достаточное условие для его существования: | Найти диофантово представление для операции возведения в степень ей не удалось, но она нашла достаточное условие для его существования: | ||
− | <tex>\left \langle a, b \right \rangle\in\mathbb{M}\Leftrightarrow \exists x_1, x_2, | + | <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, | + | <tex>\left \{ P(a, b, x_1, x_2, \ldots , x_n)=0 \right \}</tex> |
Его определяет отношение <tex>J(a,b)</tex> со следующими свойствами: | Его определяет отношение <tex>J(a,b)</tex> со следующими свойствами: | ||
Строка 93: | Строка 118: | ||
В 1958 году М. Дэвис и Х. Патнем опубликовали работу, в которой они рассмотрели класс так называемых экспоненциально-диофантовых уравнений.Такие уравнения имеют вид: | В 1958 году М. Дэвис и Х. Патнем опубликовали работу, в которой они рассмотрели класс так называемых экспоненциально-диофантовых уравнений.Такие уравнения имеют вид: | ||
− | <tex>E_1(x_1,x_2, | + | <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, | + | где <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, | + | <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, | + | <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>\left \langle a, b, c= a^b\right \rangle</tex>, является диофантовым. Тогда стало бы возможным ценой введения дополнительных неизвестных перевести экпоненциально-диофантово представление в диофантово представление: | ||
− | <tex>a, b, c= a^b\Leftrightarrow \exists x_1,x_2, | + | <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, | + | <tex>P(a, b, x_1, x_2, \ldots , x_n)=0 </tex>, |
*недопускающее решение с <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> будет всегда неверно; | ||
Строка 255: | Строка 281: | ||
|- | |- | ||
|} | |} | ||
− | Далее Матеясевич рассмотрел последовательность, состоящую из четных членов первоначальной последовательности. Оставалось построить уравнение, такое, что <tex>P(a,b,x_1, | + | Далее Матеясевич рассмотрел последовательность, состоящую из четных членов первоначальной последовательности. Оставалось построить уравнение, такое, что <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)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>6) \quad ld=r-2</tex> | ||
+ | |||
+ | <tex>7) \quad (2h+g)e=r-3</tex> | ||
− | <tex>2 | + | <tex>8) \quad x^2-rxy+y^2=1</tex> |
− | <tex> | + | <tex>9) \quad lp=x-b</tex> |
− | <tex> | + | <tex>10)\quad(2h+g)q=x-a</tex> |
− | |||
− | + | Если возвести обе части всех этих уравнений в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система. | |
− | + | В результате совместной работы Дэвиса, Робинсон, Патнема, Матиясевича было доказано, что по заданию перечислимого множества в любой стандартной | |
+ | форме можно построить его диофантово представление: | ||
+ | * построить арифметическую формулу со многими ограниченными кванторами общности; | ||
+ | * преобразовать эту формулу в нормальную форму Дейвиса с одним ограниченным квантором общности; | ||
− | + | * устранить этот ограниченный квантор общности ценой перехода к экспоненциально-диофантовым уравнениям; | |
+ | * устранить возведение в степень. | ||
− | + | Таким образом, была доказана правильность гипотезы Мартина Дэвиса, которая стала называться DPRM-теоремой. Из этой теоремы следует, что десятая проблема Гильберта является неразрешимой. | |
− | + | == См. также == | |
+ | * [[Неразрешимость исчисления предикатов первого порядка]] | ||
+ | * [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] | ||
+ | * [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]] | ||
+ | * [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]] | ||
+ | * [[Неразрешимость задачи об эквивалентности КС-грамматик]] | ||
+ | == Примечания == | ||
+ | <references /> | ||
==Источники информации== | ==Источники информации== | ||
− | *Матиясевич Ю.В. Десятая проблема Гильберта. — М. | + | *Матиясевич Ю.В. Десятая проблема Гильберта. — М., Физматлит, 1993 — Математическая логика и основания математики |
− | *Проблемы Гильберта | + | *Проблемы Гильберта. Сборник под редакцией П.С. Александрова, М., Наука, 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 П. Варпаховский, А. Н. Колмогоров О решении десятой проблемы Гильберта | + | *[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 клубе при ПОМИ РАН] | ||
+ | [[Категория: Теория формальных языков]] | ||
+ | [[Категория: Теория вычислимости]] | ||
+ | [[Категория: Примеры неразрешимых задач]] |
Текущая версия на 19:36, 4 сентября 2022
В 1900 году в Париже на втором Международном Конгрессе математиков выдающийся математик Давид Гильберт выступил с докладом, который назывался «Математические проблемы». Десятая из двадцати трех обозначенных в докладе проблем была сформулирована Гильбертом так:
Задача: |
Решение проблемы разрешимости для произвольного диофантова уравнения. Пусть дано произвольное диофантово уравнение с произвольным числом неизвестных и целыми рациональными коэффициентами; требуется указать общий метод, следуя которому можно было бы в конечное число шагов узнать, имеет ли данное уравнение решение в целых рациональных числах или нет. |
Диофантовы уравнения
Определение: |
Диофантово уравнение (англ. diophantine equation) имеет вид | , где — многочлен с целыми коэффициентами.
Примеры диофантовых уравнений
Ниже приведены примеры наиболее известных частных случаев диофантовых уравнений:
- ,
- при решениями этого уравнения (обобщенного уравнения Пифагора) являются пифагоровы тройки,
- согласно Великой теореме Ферма это уравнение не имеет ненулевых целых решений при .
- уравнение Пелля;
- , где параметр не является точным квадратом;
- уравнение Каталана:
- , где ;
- уравнение Туэ:
- при и .
Диофант искал решение этих уравнений в рациональных числах, Гильберт спрашивал про решение диофантовых уравнений в целых числах.
В современной терминологии десятая проблема Гильберта является примером массовой проблемы [1]. Массовая проблема состоит из счетного количества вопросов на каждый из которых нужно дать ответ — да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.
Теорема о неразрешимости десятой проблемы Гильберта
Теорема (Неразрешимость десятой проблемы Гильберта): |
Не существует алгоритма, который узнавал бы по произвольному диофантову уравнению, имеет ли оно решения в целых числах или нет. |
Таким образом, можно говорить об отрицательном решении десятой проблемы Гильберта. Доказательство неразрешимости этой проблемы вытекает из тезиса Черча и следующих двух теорем:
Теорема: |
Существует перечислимое, но неразрешимое множество натуральных чисел [2]. |
Теорема (DPRM-теорема): |
Понятия «диофантово множество» и «перечислимое множество» совпадают. |
Аббревиатура в названии последней теоремы образована из первых букв фамилий математиков Мартина Девиса (англ. Martin Davis), Хилари Патнэма (англ. Hilary Putnam), Джулии Робинсон (англ. Julia Robinson) и Юрия Матиясевича. Подробное доказательство неразрешимости десятой проблемы Гильберта можно прочитать здесь [3] [4].
Ниже приведены основные идеи доказательства неразрешимости проблемы существования решения диофантова уравнения в целых числах.
Пусть дано множество | натуральных чисел и нужно найти алгоритм, который по каждому натуральному определяет, принадлежит это множеству или нет.
- В соответствии с тезисом Черча, такой алгоритм существует тогда и только тогда, когда множество разрешимо.
- Для отрицательного решения десятой проблемы Гильберта достаточно доказать диофантовость каждого перечислимого множества, то есть по каждому перечислимому множеству уметь строить такое диофантово уравнение, , которое имело бы натуральные решения для всех , принадлежащих и только для таких .
- Тогда, взяв в качестве неразрешимое множество, можно было бы получить, что для соответствующего уравнения нет общего алгоритма, который по каждому натуральному давал бы ответ на вопрос о существовании у этого уравнения натуральных решений. Если бы этот алгоритм существовал, то можно было бы за конечное число шагов узнать, имеет ли уравнение решение, то есть принадлежит ли число множеству , имеет ли уравнение решение и так далее. Получилось бы, что существует алгоритм, который по каждому натуральному за конечное число шагов определяет, принадлежит множеству или нет. перечислимое, но
- Тогда, в соответствии с тезисом Черча, множество было бы разрешимым вопреки выбору этого множества.
Этапы доказательства DPRM-теоремы
Гипотеза и нормальная форма Мартина Дэвиса
М. Дэвис перешёл от формулировки десятой проблемы Гильберта в целых числах к естественной для теории алгоритмов формулировке в целых неотрицательных числах. Для конкретного диофантова уравнения задача о нахождении целочисленных решений и задача о нахождении решений в целых неотрицательных числах — разные задачи. Однако если мы интересуемся сразу всеми уравнениями (как, например, в 10-й проблеме Гильберта), то эти две задачи совпадают. Действительно, если рассмотреть систему уравнений
,
то станет понятно, что:
- любое решение системы в произвольных целых числах содержит решение уравнения в неотрицательных целых числах;
- для любого решения уравнения в неотрицательных целых числах найдутся целочисленные значения , дающие решение системы , так как, согласно известной теореме Лагранжа, каждое неотрицательное целое число представимо в виде суммы квадратов четырёх целых чисел.
Система уравнений
может быть свёрнута в одно уравнение : , разрешимое в целых числах тогда и только тогда, когда исходное уравнение разрешимо в неотрицательных целых числах.Утверждение: |
Таким образом, массовая проблема распознавания разрешимости диофантовых уравнений в целых числах сводится к массовой проблеме распознавания разрешимости диофантовых уравнений в целых неотрицательных числах. |
Наряду с отдельными диофантовыми уравнениями, Дэвис рассмотрел семейства диофантовых уравнений вида:
, где – многочлен с целыми коэффициентами, — параметры, — переменные. Каждое такое семейство определяет некоторое множество тех значений параметров, при которых уравнение разрешимо относительно переменных :
Такие множества называются диофантовыми.
Исследования Мартина Дэвиса, направленные на доказательство неразрешимости десятой проблемы Гильберта, привели его к постановке задачи, когда описано некоторое множество и требуется узнать, является ли оно диофантовым. В простейших случаях диофантовость множества очевидна — ясно, например, что диофантовым является множество всех положительных нечетных чисел. Однако совсем нелегко ответить на такие вопросы, как: «диофантово ли множество всех степеней числа
?», «диофантово ли множество всех простых чисел?», «диофантово ли множество всех совершенных чисел?» С первого взгляда кажется, что на эти вопросы следует дать отрицательный ответ. Тем не менее все эти множества являются диофантовыми. Приведем примеры диофантовых множеств:- множество всех полных квадратов, представлено уравнением ;
- множество всех составных чисел, представлено уравнением ;
- множество всех нестепеней числа , представлено уравнеием .
Для доказательства неразрешимости десятой проблемы Гильберта нужно было лишь показать диофантовость любого перечислимого множества, то есть нужно показать возможность построения уравнения, которое имело бы натуральные корни
только при всех , принадлежащих этому перечислимому множеству. Исходя из этого, Дэвис сформулировал следующую гипотезу:Гипотеза (Мартина Дэвиса): |
Понятия диофантового и перечислимого множества совпадают. Это значит, что множество диофантово тогда и только тогда, когда оно перечислимо. |
Доказать гипотезу Дэвису не удалось, но он получил близкий к доказательству результат, показав [5], что любое перечислимое множество можно представить в виде, названном нормальной формой Дэвиса:
Предикат Робинсон. Совместный результат М. Дэвиса и Х. Патнема и Д. Робинсон.
Джулия Робинсон исследовала вопрос о том, является ли диофантовым множество, состоящее из троек :
Найти диофантово представление для операции возведения в степень ей не удалось, но она нашла достаточное условие для его существования:
Его определяет отношение
со следующими свойствами:- для любых и из следует, что ;
- для любого существуют и , удовлетворяющие и такие, что .
Джулия Робинсон назвала отношения, обладающие этими двумя свойствами, отношениями экспоненциального роста; сейчас такие отношения носят также имя предикатов Джулии Робинсон.
В 1958 году М. Дэвис и Х. Патнем опубликовали работу, в которой они рассмотрели класс так называемых экспоненциально-диофантовых уравнений.Такие уравнения имеют вид:
,
где
и — выражения, построенные из и конкретных натуральных чисел с помощью сложения, умножения и возведения в степень.В 1961 году в совместной работе Робинсон, Дэвиса и Патмена [6] было получено экспоненциально - диофантово представление для любого перечислимого множества:
Одним из следствий работы стала возможность сведения любого показательно-диофантова уравнения к экспоненциально-диофантову уравнению с фиксированным числом переменных. Чтобы перенести результат Дэвиса, Патнема и Робинсон на обычные диофантовы уравнения, нужно было доказать, что множество, состоящее из троек
, является диофантовым. Тогда стало бы возможным ценой введения дополнительных неизвестных перевести экпоненциально-диофантово представление в диофантово представление:Джулия Робинсон показала, что для этого достаточно построить конкретное уравнение
,
- недопускающее решение с ;
- для каждого имеющее решение с .
Вклад Ю.В. Матиясевича
Такого рода уравнение удалось построить Ю.В. Матеясевичу в 1970 году. Обратившись к рассмотрению последовательности Фибоначчи, Матиясевич заметил, что если за
взять половину номера четного члена последовательности Фибоначчи, а за — сам член, то неравенство будет всегда неверно; для любого можно найти такой четный член последовательности, что неравенство будет верно. Это обстоятельство иллюстрируется приведенной ниже таблицей (в ней выделены те клетки, в которых числа оказываются меньше соответствующих чисел ).Номер члена последовательности Фибоначчи | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Член последовательности Фибоначчи | |||||||||||||||
Половина номера четного члена последовательности | |||||||||||||||
Далее Матеясевич рассмотрел последовательность, состоящую из четных членов первоначальной последовательности. Оставалось построить уравнение, такое, что
, которое имело бы натуральное решение тогда и только тогда, когда , далее сослаться на описанный выше результат Джулии Робинсон. Для этого достаточно было построить систему диофантовых уравнений в переменных , имеющую решение тогда и только тогда, когда . Такая система имеет в точнсти те же решения, что и единственное уравнение . Матиясевич получил требуемую систему в виде:
Если возвести обе части всех этих уравнений в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система.
В результате совместной работы Дэвиса, Робинсон, Патнема, Матиясевича было доказано, что по заданию перечислимого множества в любой стандартной форме можно построить его диофантово представление:
- построить арифметическую формулу со многими ограниченными кванторами общности;
- преобразовать эту формулу в нормальную форму Дейвиса с одним ограниченным квантором общности;
- устранить этот ограниченный квантор общности ценой перехода к экспоненциально-диофантовым уравнениям;
- устранить возведение в степень.
Таким образом, была доказана правильность гипотезы Мартина Дэвиса, которая стала называться DPRM-теоремой. Из этой теоремы следует, что десятая проблема Гильберта является неразрешимой.
См. также
Примечания
- ↑ Матиясевич Ю.В. Десятая проблема Гильберта. — М., Физматлит, 1993 — Математическая логика и основания математики — с.8
- ↑ Н. К. Верещагин, А. Шень, Вычислимые функции. — М. Издательство МЦНМО, 2008 — с.22
- ↑ Davis Martin Hilbert's tenth problem is unsolvable. — Amer. tex. Monthly., V.80, №3 1973 — p.233–269
- ↑ Манин Ю. И. Вычислимое и невычислимое. — М., Советское Радио, 1980 — c. 46-64
- ↑ M. Davis. Arithmetical problems and recursively enumerable predicates. — The Journal of Symbolic Logic 18 (1), 1953 — p. 33–41
- ↑ Martin Davis, Hilary Putnam, Julia Robinson The decision problem for exponential Diophantine equations. — Annals of Mathematics — 1961. — Vol. 74, № 3 — p. 425—436
Источники информации
- Матиясевич Ю.В. Десятая проблема Гильберта. — М., Физматлит, 1993 — Математическая логика и основания математики
- Проблемы Гильберта. Сборник под редакцией П.С. Александрова, М., Наука, 1969 г.
- Ю. В. Матиясевич. Диофантовы множества. — УМН, 1972, том 27, выпуск 5(167), — с. 185–222
- П. Варпаховский, А. Н. Колмогоров О решении десятой проблемы Гильберта, журнал Квант — 1970 — № 7. — С. 38—44
- Лекции Ю.В. Матиясевича в Computer Science клубе при ПОМИ РАН