Александров (ред.) - Проблемы Гильберта (сборник статей) - 2000 (947342), страница 31
Текст из файла (страница 31)
С другой стороны, всякое перечислимое множество М можно задать арифметической формулой ') Ф (х) с одной свободной переменной в том смысле, что х ~= М тогда и только тогда, когда Ф(х)— 1) То есть формулой, которая получается с помощью логических связок й (л), ~/ (~ши), Э (если...~ то...), ) (ке) к кээктороэ Чх (для любого х), Ях (существует л), применяемых к уралиеяяям ллдэ Р = О, где Р— мкогочлеи с целыми коэффкцэевтаюь Переменные, яа которые яе распространяется действие кэакторов, кавыэаются сэободкымк истинная формула. На языке математической логики это записывается в виде эквивалентности х ~ М Ф+ Ф (х).
Возникает вопрос, нельзя ли задать любое перечислимое множество, используя не все связки и кванторы, а только некоторые из них. Множество М натуральных чисел называется диофантовым, если можно построить много- член с целыми коэффициентами Р(», х„..., х„) такой, что » ~ М++ ях« ° ° Ьх„(~ (», х»,..., ха) = О) ° (1) Другими словами, М есть множество тех значений параметра», при которых уравкение Р(», х„..., х„) = О разрешимо в натуральных числах х„...,х„.
Если бы оказалось, что всякое перечислимое множество является диофантовьтм, то в силу существования неразрешимого перечислимого множества мы могли бы построить и неразрешимое диофантово множество, т. е. мы имели бы много- член Р(», х„„., х,) такой, что не существует алгорифма, распознающего по данному. », имеет ли решение уравнение Р(», х„..., х„) = О. Таким образом, проблема Гиль- берта была бы неразрешима уже для многочленов вида Р(0, хм..., х„), Р(1,х„..., х„), Р(2, х»..., х„),... и тем более для всех многочленов.
Итак, если бы всякое перечислимое множество было представимо в виде (1), то проблема Гильберта была бы нераэрешкма. Авторам работ [61 — [101 удалось получить. ряд представлений перечислимых множеств с помощью арифметических формул специального вида и извлечь из этих представлений следствии о невоэможкости некоторых алгорнфмов в теории чисел. Одним из наиболее интересных результатов является невозможность алгорифма для решения так называемых показательно-диофантовых уравнений.
Это — уравнения вида Р = ф, где Р, 9 — выражения, полученные из натуральных чисел и переменных с помощью сложения, умножения и возведения в степень. Девис, Путнам н Робинсон[71доказали, что всякое перечислимое множество представимо в виде (1), если допустить в правой части, помимо сложения и умножения, еще и действие возведения в степень, и отсюда вывели теорему о невозможности алгорифма, распознающего по данному показательно-диофантову уравнению, имеет оно решение в областинатуральных чисел или не имеет. 146 Используя несколько иное представление перечислимых множеств, Путнам [81 доказал, что не существует алгорифма, распознающего по данному многочлеиу с целыми коэффициентами, представляет этот многочлен все натуральные числа нли нет ').
Р. Р о б н н с о н [91 доказал, что всякое перечислимое множество М представимо в виде (х»:= М) ФФ 3ууз '~~ у лх ...цх (Р(х, у, г, х,..., х) = 0), где Р— многочлен с целыми коэффициентами. Отсюда следует, что невозможен злгорифм, распознающий по данному многочлену Р(у, з, х„х„х», х«) а шестью (!) неизвестными, существует ли такое у, что уравнение Р(у, х, х„..., х«) = 0 разрешимо относительно х„х„хю х прн всяком з, 0 ~( г ~~ у.
Д ев и с и П у т н а м «10] доказали также неразрешимость следующей проблемы. Обозначим через г«кольцо многочленов от одной переменной. Невозможен алгоркфм, распознающий по данному полнному Р(х„...,х„) с коэффициентами из Л, имеет уравнение Р = О решения в Л или не имеет, Недавно Д е в и с [1Ц получил следующий интересный результат. Рассмотрвм диофантово уравнение х' — гу«= 1. Если для любого х ~ 0 существует решение этого уравнения, такое, что х) з«, то десятая проблема Гильберта неразрешима. Любопытно, что еще в 1916 г. Д е л о и е [81 доказал, что при фиксированном з уравнение х« — з1»' = 1 имеет, кроме решения (1, 0), не более одного решения в целых числах.
Однако каких- либо количественных оценок, указываюпп«х зависимость х от з, мы не имеем. Остроумным рассуждением П у т н а и [81 доказал, что всякое диофантово множество совпадает с множеством натуральных значений некоторого многочлена (нлн с множеством целых значений некоторой рациональной дроби). Отсюда следует, что если все перечислвмые множества являются диофантовымн, то всякое перечислнмое множество есть множество натуральных значений некоторого многочлена.
В частности, танями будут множества всех простых чисел, всех чисел вида я(, 2" и т. п. Эти «маловероятные» результаты могут рассматриваться как «доводы» против гипотезы о том, что всякое перечислнмое множество является диофантовьп«. ») Многочлвк Р (««,..., х,,) вредстазля«т чвсзо а, есав уравзевке Р (т„,..., *„) = а зм«ет целочисленные резания. 147 Другой подход к отрицательному решению десятой проблемы Гильберта, не связанный с диофантовым представлением неречислимых множеств, был предложен А. А. Марковым. Этот подход основан на связи диофантовых уравнений с уравнениями в свободной группе или полугруппе. Уравнения в свободной полугруппе (илн, короче, уравнения в словах) определяются следующим образом. Пусть (а„..., а»), (хм..., х„) — непересекающиеся алфавиты. Равенство Ф=Ч', где Ф, Ч' — слова в алфавите (а„..., а», х„..., х„), называется уравнением в словах с и неизвестными х„..., х„.
Решением уравнения Ф = Ч' называется такой набор (Х„..., Х„) слов в алфавите (а„..., а»), что после подстановки слова Х,. вместо неизвестной х,. в слова Ф, Ч" получим графически равные слова. Известно 112], что совокупность матриц второго порядка с натуральными элементами и определителем 1 образует свободную полугруппу с двумя образующими А = ~, ), В = ~ ~. Исходя из этого, нетрудно всякой системе Е уравнений в словах сопоставить днофантово уравнение Р = О так, что система»' имеет решения тогда и только тогда, когда уравнение Р = О разрешимо в натуральных числах.
Отсюда следует, что если есть алгорифм для решения диофантовых уравнений, то он есть и для решения уравнений з словах. Если же алгорифма для решения уравнений в словах нет, то его нет и для диофантозых уравнений. Аналогичная связь существует между диофантовыми уравнениями и уравнениями в свободной группе в силу результата 113], согласно которому совокупность матриц второго порядка с целочисленными элементами и определителем 1 образует свободную группу с двумя образующими А = ( р, В = ~ „). Исследованием уравнений в свободной группе и полугруппе занимался ряд авторов.
Надо сказать, что полученные здесь результаты имеют пока положительный характер. Для уравнений в словах с двумя неизвестнымп разрешающий алгорифм построил А. А. Марков, позднее (1966 г.) 1О, И. Хмелевский нашел алгорифм для решения уравнений в словах с тремя неизвестными. Системы уравнений с одним неизвестным в свободной группе изучал Лоренц. Он нашел разрешающий алгорифм и изучил структуру решений таких систем. Однако уже для уравнений с двуми неиэ- 443 вестными в свободной группе не сделано, по существу, ничего.
По поводу исследований проблемы Гпльберта в положительном направлении предоставим слово Дэвенпорту. Он пишет 119]: «Вероятно, ни одна из областей теории чисел не сталкивается с такими трудностями, как теория диофантовых уравнений... Пря беглом взгляде на обширную литературу создается впечатление, что установлено с помощью различных искусственных приемов много результатов, связанных с отдельными уравнениями; кажется весьма затруднительным объединить эти результаты в общую теорию. Иногда, решив уравнение искусственным приемом, удается создать общую теорию, связанную с найденным решением, разумно объясняющую возникновение этого решения и показывающую, насколько найденное решение можно обобщить.
Но внутренние трудности предмета настольно велики, что область применения такой теории обычно очень ограничена. Если удается развить достаточно глубокую теорию диофантовых уравнений специального вида (например, теорию квадратичных форм), то такая теория получает право на самостоятельное существование». Все же математикам Х1Х вЂ” ХХ вв. удалось найти общие методы для решения диофантовых уравнений первой и второй степени. (См. по этому поводу (14].
Там же имеется обширная библиография.) Собственно уравнения первой степени умели решать н раньше (Ваше, ХУП в.), а вот решение уравнений второй степени — заслуга математиков Х1Х и ХХ вв. Известен также алгорифм для решения в целых числах систем уравнений первой степени (см. (14]). Однако уже для системы уравнений х' + ау' = и», х' — ау' = и» до сих пор неизвестен алгорифм, распознающий по данному целому а, имеет система целочисленные решения или нет.
В связи с положительным решением проблемы Гиль- берта для уравнений первой и второй степени интересно отметить, что решение произвольного дпофантова уравнения сводится к решению диофантовых уравнений четвертой степени. Для этого, вводя новые неизвестные, сводим произвольное диофантово уравнение к системе, состоящей из уравнений вида х + у = Л, ху = Л, О Л, а затем свертываем эту систему в одно уравнение, пользуясь тем, что система уравнений Р; = О (~ = 1,..., ш) $49 эквивалентна уравнению ,~~ ~Р;' = О. Мы получим урав- 4 1 пение четвертой степени, которое имеет целочисленные решения тогда и только тогда, когда их имеет первоначальное уравнение. При атом в новом уравнении каждая некзвестяая встречается не более чем во второй степени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
