Изменения

 Во времена, когда Гильберт формулировал свои проблемы, не было общего определения понятия алгоритма, однако Гильберт был оптимистом в математике, верил в разрешимость Доказательство неразрешимости этой проблемы, в этом смысле задача была сформулирована им вполне корректно. Задача о целых решениях произвольного уравнения сводится к задаче о целых неотрицательных решениях. Далее достаточно ограничиться диофантовыми уравнениями степени не выше четвертой. Для диофантовых уравнений степени не выше второй искомый общий метод был найден, однако уже для уравнений третьей степени эта задача казалась неразрешимой, возникло предположение,что тот общий метод, об отыскании которого говорится в формулировке Гильберта, попросту не существует. Чтобы доказать не существование некого общего метода для решения серии задач, требовалось дать точное определение тому, что такое этот общий метод и какими средствами он может быть реализован. Понятие алгоритма было сформулировано в тридцатые годы двадцатого века в работах матлогиков вытекает из тезиса Черча, Клини, Тьюринга, Геделя. Важную роль в решении десятой проблемы Гильберта сыграл Эмиль Пост. Постом было впервые предложено общее понятие вычислимости, которое имеет фундаментальное значение для доказательства неразрешимости ряда проблем математики. В одной из своих работ он написал, что десятая проблема Гильберта «молит о доказательстве неразрешимости». Эти слова Поста вдохновили его молодого ученика Мартина Дэвиса, который смог сформулировать гипотезу, из которой следовала неразрешимость десятой проблемы Гильберта. ===Некотрые определения и теорема==={{Определение |definition=Множество <tex>M</tex> натуральных чисел называется перечислимым, если оно совпадает со множеством значений некоторой примитивно-рекурсивной функции.}}{{Определение |definition=Множество <tex>M</tex> называется разрешимым, если оно перечислимо вместе со своим дополнением <tex>\mathbb N-M</tex>, где <tex>\mathbb N</tex> {{---}} множество всех натуральных чисел.}}следующих двух теорем:

{{Теорема|author=DPRM-теорема |statement=Понятия «диофантово множество» и «перечислимое множество» совпадают.}}Аббревиатура в названии последней теоремы образована из первых букв фамилий математиков Мартина Девиса (англ. Martin ''Davis''), Хилари Патнэма (англ. ''Hilary Putnam''), Джулии Робинсон (англ. ''Julia Robinson'') и Юрия Матиясевича. Подробное доказательство неразрешимости десятой проблемы Гильберта можно прочитать здесь <ref>Davis Martin Hilbert's tenth problem is unsolvable {{---}} Amer. Math. Monthly., V.80, №3 1973,p. 233–269.</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> было бы разрешимымвопреки выбору этого множества.