Изменения

Ниже приведены примеры наиболее известных частных случаев диофантовых уравнений:* <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\ge geqslant 3</tex> и <tex>c\ne 0</tex> — уравнение Туэ.

В современной терминологии десятая проблема Гильберта является примером ''массовой проблемы'' <ref>Матиясевич Ю.В. Десятая проблема Гильберта. — М.: , Физматлит, 1993 {{---}} Математическая логика и основания математики {{---}} с.8</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>. Ниже приведены основные идеи доказательства. Пусть дано множество <tex>M</tex> натуральных чисел и нужно найти алгоритм, который по каждому натуральному <tex>n</tex> определяет, принадлежит это <tex>n</tex> множеству <tex>M</tex> или нет.

Ниже приведены основные идеи доказательства неразрешимости проблемы существования решения диофантова уравнения в целых числах. {| | 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> было бы разрешимым вопреки выбору этого множества.

*Матиясевич Ю.В. Десятая проблема Гильберта. — М.: , Физматлит, 1993 — Математическая логика и основания математики