Введение
Решение некоторых диофантовых уравнений
In mathematics, a Diophantine equation is an equation of the form P(x1, , xj, y1, , yk) = 0 (usually abbreviated P(, ) = 0) where P(, ) is a polynomial with integer coefficients, where x1, , xj indicate parameters and y1, , yk indicate unknowns. A Diophantine set is a subset S of , the set of all j tuples of natural numbers, so that for some Diophantine equation P(, ) = 0,
That is, a parameter value is in the Diophantine set S if and only if the associated Diophantine equation is satisfiable under that parameter value. The use of natural numbers both in S and the existential quantification merely reflects the usual applications in computability theory and model theory. It does not matter whether natural numbers refer to the set of nonnegative integers or positive integers since the two definitions for Diophantine sets are equivalent. We can also equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers. Also it is sufficient to assume P is a polynomial over and multiply P by the appropriate denominators to yield integer coefficients. However, whether quantification over rationals can also be substituted for quantification over the integers is a notoriously hard open problem. The MRDP theorem (so named for the initials of the four principal contributors to its solution) states that a set of integers is Diophantine if and only if it is computably enumerable. A set of integers S is computably enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of S and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging to number theory, can be taken rather in logical or computability theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work. Matiyasevich's completion of the MRDP theorem settled Hilbert's tenth problem. Hilbert's tenth problem was to find a general algorithm that can decide whether a given Diophantine equation has a solution among the integers. While Hilbert's tenth problem is not a formal mathematical statement as such, the nearly universal acceptance of the (philosophical) identification of a decision algorithm with a total computable predicate allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.
В математике диофантово уравнение — это уравнение вида P(x₁, …, xj, y₁, …, yk) = 0 (обычно сокращается как P( , ) = 0), где P( , ) — многочлен с целочисленными коэффициентами, причём x₁, …, xj обозначают параметры, а y₁, …, yk — неизвестные. Диофантово множество — это подмножество S множества всех j-кортежей натуральных чисел, такое что для некоторого диофантова уравнения P( , ) = 0, значение параметра принадлежит диофантовому множеству S тогда и только тогда, когда соответствующее диофантово уравнение имеет решение при этом значении параметра. Использование натуральных чисел как в S, так и в экзистенциальной квантификации отражает обычные применения в теории вычислимости и теории моделей. Не имеет значения, относятся ли натуральные числа к множеству неотрицательных или положительных целых чисел, поскольку два определения диофантовых множеств эквивалентны. Мы также можем говорить о диофантовых множествах целых чисел и свободно заменять квантификацию над натуральными числами квантификацией над целыми числами. Кроме того, достаточно предположить, что P — многочлен, и умножить P на соответствующие знаменатели, чтобы получить целочисленные коэффициенты. Однако, можно ли заменить квантификацию над рациональными числами квантификацией над целыми числами, остаётся известной сложной открытой проблемой. Теорема MRDP (названная по инициалам четырёх основных участников её решения) утверждает, что множество целых чисел является диофантовым тогда и только тогда, когда оно вычислимо перечислимо. Множество целых чисел S является вычислимо перечислимым, если и только если существует алгоритм, который, получив на вход целое число, останавливается, если это число принадлежит S, и работает бесконечно в противном случае. Это означает, что понятие общего диофантова множества, очевидно относящееся к теории чисел, можно рассматривать скорее в логических или теоретико-вычислительных терминах. Однако это далеко не очевидно и стало кульминацией многолетней работы. Завершение Матиясевичем теоремы MRDP решило десятую проблему Гильберта. Десятая проблема Гильберта заключалась в поиске общего алгоритма, который может определить, имеет ли данное диофантово уравнение решение в целых числах. Хотя десятая проблема Гильберта не является формальным математическим утверждением как таковым, почти всеобщее принятие (философской) идентификации алгоритма решения с полным вычислимым предикатом позволяет нам использовать теорему MRDP, чтобы заключить, что десятая проблема неразрешима.
In mathematics, a Diophantine equation is an equation of the form P(x1, , xj, y1, , yk) = 0 (usually abbreviated P(, ) = 0) where P(, ) is a polynomial with integer coefficients, where x1, , xj indicate parameters and y1, , yk indicate unknowns. A Diophantine set is a subset S of , the set of all j tuples of natural numbers, so that for some Diophantine equation P(, ) = 0,
That is, a parameter value is in the Diophantine set S if and only if the associated Diophantine equation is satisfiable under that parameter value. The use of natural numbers both in S and the existential quantification merely reflects the usual applications in computability theory and model theory. It does not matter whether natural numbers refer to the set of nonnegative integers or positive integers since the two definitions for Diophantine sets are equivalent. We can also equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers. Also it is sufficient to assume P is a polynomial over and multiply P by the appropriate denominators to yield integer coefficients. However, whether quantification over rationals can also be substituted for quantification over the integers is a notoriously hard open problem. The MRDP theorem (so named for the initials of the four principal contributors to its solution) states that a set of integers is Diophantine if and only if it is computably enumerable. A set of integers S is computably enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of S and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging to number theory, can be taken rather in logical or computability theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work. Matiyasevich's completion of the MRDP theorem settled Hilbert's tenth problem. Hilbert's tenth problem was to find a general algorithm that can decide whether a given Diophantine equation has a solution among the integers. While Hilbert's tenth problem is not a formal mathematical statement as such, the nearly universal acceptance of the (philosophical) identification of a decision algorithm with a total computable predicate allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.
Методика испытаний
Юрий Матиясевич использовал метод, основанный на числах Фибоначчи, растущих экспоненциально, чтобы продемонстрировать, что решения диофантовых уравнений могут расти экспоненциально. Более ранние работы Джулии Робинсон, Мартина Дэвиса и Хилари Путнэма – известные как MRDP – показали, что этого достаточно для доказательства того, что любое вычислимо перечислимое множество является диофантовым.
Применение к десятой проблеме Гильберта
Десятая проблема Гильберта ставит вопрос о существовании общего алгоритма, определяющего разрешимость диофантовых уравнений. Сочетание результата Матиясевича с тем фактом, что большинство рекурсивно перечислимых языков не являются разрешимыми, влечет за собой невозможность решения десятой проблемы Гильберта.
Усовершенствования
Позднее работы показали, что вопрос о разрешимости диофантова уравнения неразрешим, даже если уравнение содержит только 9 натуральных переменных (Матиясевич, 1977) или 11 целых переменных (Цзи Вэй Сунь, 1992).