Изменения
Нет описания правки
В современной терминологии десятая проблема Гильберта является примером ''массовой проблемы''<ref>Матиясевич Ю.В. Десятая проблема Гильберта. — М.: Физматлит, 1993. - Математическая логика и основания математики {{---}} с.8</ref>. Массовая проблема состоит из счетного количества вопросов на каждый из которых нужно дать ответ {{---}} да или нет. В данном случае эти вопросы параметризуются диофантовыми уравнениями и нужно сказать: да, данное диофантово уравнение имеет решение или нет, данное уравнение не имеет решения. И суть массовой проблемы состоит в том, что нужно найти единый универсальный метод, который позволял бы ответить на любой из этих вопросов. Среди двадцати трех «Математических проблем» Гильберта десятая является единственной массовой проблемой и она может рассматриваться, как проблема информатики. Сегодня мы знаем, что десятая проблема Гильберта решения не имеет. Это означает, что она не разрешима, как массовая проблема.
==Теорема о неразрешимости десятой проблемы Гильберта==
{{Теорема
|author=Неразрешимость десятой проблемы Гильберта
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>.
Пусть дано множество <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-теоремы==
===Гипотеза и нормальная форма Мартина Дэвиса===
М. Дэвис перешёл от формулировки десятой проблемы Гильберта в целых числах к естественной для теории алгоритмов формулировке в целых неотрицательных числах.
Если возвести обе части всех этих уравнений в квадрат и сложить их почленно, то получиться одно уравнение, которое будет иметь те же решения на множестве натуральных чисел, что и вся система. Таким образом,
== См. также ==
