ДИОФАНТОВЫХ УРАВНЕНИИ ПРОБЛЕМА РАЗРЕШИМОСТИ

Значение ДИОФАНТОВЫХ УРАВНЕНИИ ПРОБЛЕМА РАЗРЕШИМОСТИ в математической энциклопедии:

- проблема отыскания алгоритма для распознавания по любому диофантову уравнению, имеет ли оно решение.

Существенным в постановке проблемы является требование найти универсальный метод, к-рый должен быть пригоден для любого уравнения (все известные способы для распознавания наличия решений у диофантовых уравнений применимы лишь к уравнениям из отдельных более или менее широких классов). Такой метод позволял бы решать и системы диофантовых уравнений, ибо система Р ₁ = 0, . .., Р _k=0 эквивалентна уравнению

Задача нахождения такого универсального метода для распознавания наличия решений в целых числах была поставлена Д. Гильбертом (D. Hilbert, см. [1]).

В начале 50-х гг. 20 в. появились первые работы, нацеленные на доказательство невозможности алгоритма, требуемого в Д. у. п. р. В это время была высказана гипотеза (гипотеза Дейвиса, см. [2]) о том, что каждое перечислимое множество является диофантовым множеством. Поскольку известны примеры перечислимых, но алгоритмически неразрешимых множеств, то из справедливости этой гипотезы немедленно следует отрицательное решение Д. у. п. р.

В 1961 было доказано (см. [3]) более слабое утверждение: каждое перечислимое множество является показательно-диофантовым множеством, т. е. для каждого перечислимого множества M существуют такие выражения Ки L, построенные из натуральных чисел и переменных a,z_1; . . ., z_n с помощью сложения, умножения и возведения в степень, что тогда и только тогда, когда показательно- диофантово уравнение K=L разрешимо относительно z₁, ..., z_n. После этого для доказательства гипотезы Дейвиса осталось указать способ, позволяющий преобразовать произвольное показательно-диофантово уравнение в нек-рое диофантово уравнение, имеющее или не имеющее решения одновременно с ним. Было доказано [4], что такое преобразование возможно, если существует диофантово уравнение

обладающее следующими двумя свойствами: 1) в любом решении этого уравнения 2) для любого kсуществует решение, в к-ром v>u^k (про такое уравнение говорят, что оно имеет экспоненциальный рост). Пример диофантова уравнения, имеющего экспоненциальный рост, к-рый впервые был построен в [5], завершил доказательство гипотезы о диофантовости перечислимых множеств (полностью доказательство гипотезы Дейвиса изложено в [6], [7]). Обратное утверждение о перечислимости диофантовых множеств доказывается легко. Таким образом, класс перечислимых множеств совпадает с классом диофантовых множеств.

Из этого результата следует возможность указать конкретный многочлен W(a, z₁, .. ., z_n )с целыми коэффициентами такой, что не существует алгоритма, позволяющего по значению параметра аузнавать, разрешимо ли уравнение W(a,z₁, ..., z_n) = 0 относительно z₁, . , ., z_n, и, тем более, не существует требуемого в Д. у. п. р. алгоритма для распознавания наличия решений у произвольного диофантрва уравнения.

Вопрос о существовании алгоритма, позволяющего распознавать разрешимость диофантовых уравнений в рациональных числах, эквивалентен вопросу о существовании алгоритма, позволяющего распознавать разрешимость однородных диофантовых уравнений в целых числах. Эта важная проблема пока (1978) остается открытой и малоисследованной.

Лит.:[1] Гильберт Д., в кн.: Проблемы Гильберта, М., 1969, с. 11-64; [2] Дэвис М., "Математика", 1964, т. 8, № 5, с. 15-22; [3] Дэвиc М., Путнам Х., Робинсон Дж., там же, с. 69-79; [4] Робинсон Дж., там же, с. 3-14; [5] Матиясевич Ю. В., "Докл. АН СССР", 1970, т. .191, Л"" 2, с. 279-82; [6] его же, "Успехи матем. наук", 1972, т. 27, в. 5, с. 185-222; [7] Манин Ю. И., в сб.: Итоги науки и техники. Современные проблемы математики, 1973, т. 1, с. 5-37; [8] DavisM., Матиясевич Ю. В., Robinson J., "Proc. Symp. Pure Math.", 1976, v. 28, p 323 - 75

Ю. В. Матиясевич.