Алгоритмическая Проблема

Проблема, в к-рой требуется найти единый метод ( алгоритм).для решения бесконечной серии однотипных единичных задач. Такие проблемы иногда наз. также массовыми проблемами. А. п. возникали и решались в различных областях математики на протяжении всей ее исторпи; однако нек-рые из них долгое время не поддавались решению. Причина этого выяснилась лишь после того, как в 30-х гг. 20 в. в математнч. логике было выработано точное определение понятия алгоритма. Оказалось, что А. п. могут быть неразрешимыми, т. е. искомые в них алгоритмы могут не существовать. Таким образом, представление математиков об А. п. значительно изменилось: теперь уже новые А. п. стали формулировать как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач п нахождения такого алгоритма в случае, если он существует. В алгоритмов теории почти одновременно появилось несколько различных по форме уточнений понятия алгоритма, к-рые по существу оказались эквивалентными. Каждое из этих уточнений заключается в том, что выделяется тот или иной достаточно широкий класс конкретных алгоритмов, замкнутый относительно естественных операций соединения алгоритмов. Каждое утверждение о неразрешимости той или иной А. п. представляет собой математически строго доказанную теорему о невозможности решения рассматриваемой А. п. с помощью алгоритмов данного класса. В такой форме эти теоремы можно было бы рассматривать как спецп-фич. теоремы, связанные с данным классом алгоритмов. Однако все результаты такого рода можно перенести на общепонятный для математиков язык алгоритмов, понимаемых в интуитивном смысле. Этот перенос основан на так наз. тезисе Чёрча(в зависимости от формы уточнения понятия алгоритма его наз. еще тезисом Тьюринга, или принципом нормализации), к-рый утверждает, что рассматриваемый класс алгоритмов универсален, т. е. с помощью алгоритмов этого класса по существу мо?кно выполнить работу любого алгоритма, понимаемого в интуитивном смысле. Этот тезис есть естественнонаучный факт, подкрепленный историей математики: все известные в математике алгоритмы удовлетворяют ему; все попытки построить примеры алгоритмов, выходящих за указанные рамки, не увенчались успехом. Наконец, эквивалентность различных по форме уточнений понятия алгоритма также служит подкреплением этого тезиса. Тезис Чёрча не может быть доказан, поскольку относится к математически расплывчатому понятию алгоритма в интуитивном смысле; однако он очень важен для математики, так как позволяет говорить о неразрешимости тех или иных А. и. в широком и общепонятном для математиков смысле. Первые примеры неразрешимых А. п. были обнаружены в самой теории алгоритмов. К ним относятся проблема распознавания принадлежности данному нерекурсивному множеству натуральных чисел, проблема остановки универсальной машины Тьюринга, проблема распознавания самопрцменимостн нормальных алгорифмов и др. Из А. п., выходящих за рамки самой теории алгоритмов, прежде всего следует отметить проблему распознавания тождественной истинности формул исчисления предикатов 1-й ступени, неразрешимость к-рой впервые была доказана А. Чёрчем (A. Church) в 1936. К этому результату по существу примыкают многочисленные исследования А. п. в моделей теории. Теория моделей, изучающая непустые множества с определенными на них отношениями с помощью исчисления предикатов, возникла в 30-х гг. в работах А. И. Мальцева и А. Тар-ского (A. Tarski). Им же принадлежат точные постановки многих А. п. в теории моделей и ряд фундаментальных результатов в этом направлении. Элементарной теорией данного класса Кмоделей наз. совокупность всех замкнутых формул исчисления предикатов 1-й ступени, к-рые истинны во всех моделях класса K. Класс K может состоять из одной модели. Элементарная теория Тназ. разрешимой или неразрешимой в зависимости от того, существует или нет алгоритм для распознавания но любой формуле, принадлежит она теории Тили нет. Ыек-рый обзор методов исследования А. п. в теории моделей и результатов, полученных в этом направлении, имеется в [3]. Из указанных в [3] н оставшихся пока (1977) нерешенными проблем наиболее интересен вопрос о разрешимости элементарной теории свободных групп. Многочисленные и разнообразные А. п. возникают также при конструктивном истолковании различных разделов математики. Ниже приведены основные результаты, относящиеся к А. п. в традиционных разделах математики. Долгое время оставался открытым естественный вопрос: являются ли неразрешимые А. п. специфическими для теории алгоритмов и математич. логики? Иначе говоря, существуют ли неразрешимые А. п. в традиционных разделах математики, далеких от математич. логики? Первый результат такого рода был получен в 1947 независимо друг от друга А. А. Марковым и Э. Л. Постом (Е. L. Post). Они доказали неразрешимость проблемы равенства слов (тождества) для полугрупп, к-рая была поставлена А. Туэ (А. Тhue) еще в 1914. В этой проблеме рассматриваются полугруппы, заданные с помощью конечного числа образующих (алфавита) и определяющих соотношений Элементарным преобразованием рассматриваемой полугруппы П наз. переход от слова вида к слову или обратно, где Ри Q — произвольные слова в алфавите (1). Два слова Xи У в алфавите (1) наз. эквивалентными в П, если они либо совпадают графически, либо одно из них получается из другого с помощью конечной последовательности элементарных преобразований. Множество всех классов эквивалентности с операцией умножения, к-рая определяется естественным образом через операцию приписывания слов, и есть полугруппа П, заданная образующими (1) и определяющими соотношениями (2). Проблема равенства слов (тождества) полугруппы П заключается в отыскании алгоритма для распознавания по любой паре слов X и Y полугруппы П, эквивалентны они в П или нет, т. е. тождественны определенные ими элементы полугруппы П или нет. А. А. Марков и Э. Л. Пост построили конкретные полугруппы, для к-рых уже невозможен алгоритм, решающий проблему равенства (см. [1]). Наиболее замечательный результат в этом направлении был получен П. С. Новиковым [4], [5]. Он доказал неразрешимость классич. проблемы тождества теории групп, к-рая была поставлена М. Деном (М. Dehn) в 1912 и привлекала внимание многих алгебраистов мира. Эта проблема формулируется аналогично проблеме тождества для полугрупп с тем отличием, что рассматриваются только такие системы соотношений (2), к-рые гарантируют существование в рассматриваемой полугруппе обратных элементов для всех образующих (1). П. С. Новиков доказал также неразрешимость очень важной для теории групп проблемы изоморфизма, к-рая заключалась в отыскании алгоритма для распознавания по любым двум группам, изоморфны они или нет. Позже было показано [6], что для всякой фиксированной группы Gневозможен алгоритм, к-рый проверял бы по произвольной группе, изоморфна она группе G или нет. А. А. Марков исследовал проблемы распознавания инвариантных свойств полугрупп, т. е. таких свойств, к-рые сохраняются при переходе к изоморфным полугруппам [2]. Он доказал, что если для инвариантного полугруппового свойства существует полугруппа со свойством ц другая полугруппа, не вложимая ни в какую полугруппу с этим свойством, то невозможен алгоритм для распознавания по любой полугруппе, обладает она свойством пли нет. Это по существу означает, что почти все инвариантные полугрупповые свойства алгоритмически не распознаваемы в классе полугрупп. В теории групп также был получен аналог этой фундаментальной теоремы (см. [7], [8], [9]). Из нее, в частности, вытекает следствие: пусть есть класс всех групп, обладающих инвариантным свойством ; с каждым таким классом связаны две А. п.- проблема тождества для групп из класса и проблема распознавания по любой группе, принадлежит она классу или нет. Оказывается, что для любого непустого класса по крайней мере одна из этих двух А. п. неразрешима. Аналогичная ситуация имеет место и для полугрупп. Исследовался вопрос о возможно простых заданиях групп и полугрулп с неразрешимой проблемой равенства слов. Из многочисленных исследований в этом направлении следует отметить доказательство неразрешимости проблемы равенства слов для полугруппы, заданной 7 простыми определяющими соотношениями: (см. [10]). Позже был построен пример полугруппы с 3 определяющими соотношениями и неразрешимой проблемой равенства [11]. Даже для полугрупп с одним определяющим соотношением до сих пор (1977) не найден алгоритм, решающий проблему тождества в общем случае. Такой алгоритм построен только для несократимого определяющего соотношения [12]. Для групп с одним определяющим соотношением алгоритм, решающий проблему равенства, был построен давно [13]; но уже для двух соотношений вопрос остается открытым. Минимальное число определяющих соотношений, при к-ром известны примеры групп с неразрешимой проблемой тождества, равно 12. Доказана разрешимость проблемы равенства слов для коммутативных полугрупп. Для коммутативных групп разрешима также и проблема изоморфизма. Проблема равенства слов разрешима для конечных групп, для конечно определенных простых групп, для нильпотентных групп, а также для разрешимых групп ступени 2. Но уже в классе разрешимых групп ступени 5 можно указать группу с неразрешимой проблемой равенства, заданную с помощью соответствующего тождества ступени 5 и конечного числа определяющих соотношений (см. [15]). Исследование проблемы тождества для групп с ограниченной мерой налегания определяющих слов, т. е. левых частей определяющих соотношений, было начато еще до того, как была доказана неразрешимость общей проблемы тождества. Самым сильным результатом в этом направлении в настоящее время (1977) является доказательство разрешимости проблемы тождества в классе групп, задаваемых системами определяющих соотношений, в к-рых определяющие слова могут налегать друг на друга лпшь менее чем на своей длины [14]. Если допустить налегание на длины определяющих слов, то пример группы с неразрешимой проблемой тождества строится довольно просто. Для промежутка между и вопрос остается открытым. Аналогичные исследования проводились и для полугрупп. Оказалось, что для полугрупп с максимальной мерой налегания определяющих слов, меньшей , проблема тождества разрешима, в то время как известны примеры полугрупп с неразрешимой проблемой тождества и с максимальной мерой налегания определяющих слов, равной . Из топологич. А. п. прежде всего выделяется классич. проблема распознавания гомеоморфизма для n-мерных многообразий. А. А. Марков построил пример 4-мерного многообразия , для к-рого невозможен алгоритм, распознающий по любому 4-мерному многообразию, гомеоморфно оно пли нет [17]. Известно, что при п=2 эта проблема имеет положительное решение; при n=3 вопрос остается открытым; для n-мерных многообразий при неразрешимы также проблемы распознавания комбинаторной и гомотопич. эквива-лентностей многообразий. Заметим также, что если взять полиэдр Р, фундаментальная группа к-рого имеет неразрешимую проблему тождества, то для Рневозможен алгоритм, распознающий связанную гомотопность (или свободную гомотопность) двух произвольных путей на Р, проходящих через данную точку. Получено положительное решение проблемы сопряженности в группах кос, к-рая эквивалентна топологич. проблеме распознавания эквивалентности кос [16]. Одной из наиболее знаменитых А. п. математики являлась 10-я проблема Гильберта, в к-рой требовалось найти алгоритм для распознавания по любой системе днсфантовых уравнений с целочисленными коэффициентами, имеет она целочисленное решение или нет. После появления многочисленных результатов о неразрешимых А. п. возникла гипотеза о том, что и эта проблема неразрешима. Более того, группе американских математиков удалось установить, что неразрешимость 10-й проблемы Гильберта следует из существования двуместного диофантова предиката экспоненциального роста (см. [18], [19]). Однако построить такой предикат им не удалось. Они доказали лишь неразрешимость проблемы распознавания существования целочисленных решений показательных уравнений. Искомый диофантов предикат экспоненциального роста впервые был построен в 1970 (см. [20], [21] ). Тем самым впервые была доказана неразрешимость 10-й проблемы Гильберта. В теории алгоритмов доказано существование неразрешимых А. п. различных неразрешимости степеней. Многочисленные исследования возникающих в математике А. п. показали, что каждая из этих А. п. в общем случае имеет максимальную степень неразрешимости, а в своих частных вариантах (например, проблема тождества в конкретных полугруппах или группах) может иметь любую наперед заданную степень неразрешимости. Лит.:[1] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [2] Марков А. А., "Тр. Матем. ин-та АН СССР", 1954, т. 42, с. 1-376; [3] Ершов Ю. Л. и др., "Успехи матем. наук", 1965, т. 20, № 4, с. 37-108; [4] Новиков П. С., "Докл. АН СССР", 1952, т. 85, № 4, с. 709 — 12; [5] Новиков П. С., "Тр. Матем. нн-та АН СССР", 1955, т. 44, с. 1-444; [6] Адян С. И., "Тр. Моск. матем. об-ва", 1957, т. 6, с. 231-98; [7] Адян С. И., "Докл. АН СССР", 1957. т. 117, Л5 1, с. 9 — 12; [8] А д я н С. И., "Докл. АН СССР", 1958. т. 123, Л" 1, с. 13-16; [9] Rabin M. О., "Ann. math.", 1958, v. 67, № 1, p. 172-94; [10] Цейтин Г. С., "Тр. Матем. ин-та АН СССР", 1958, т. 52, с. 172-89; [11] Матиясевич Ю. В., "Докл. АН СССР", 1967, т. 173, № 6, с. 1264-6; [12] Адян С. И., "Тр. Матем. ин-та АН СССР", 1966, т. 85, с. 1 — 123; [13] Магнус В., "Успехи матем. наук", 1941, Bd 8, с. 365-76; [14] Lуndоn R. С., "Math. Ann.", 1966, Bd. 166, № 3, S. 208-28; [15] Ремесленников В. Н., "Алгебра и логика", 1973, т. 12, № 5, с. 577-602; [16] Гарсаид Ф. А., "Математика", 1970, т. 14, № 4, с. 113-32; [17] Марков А. А., "Докл. АН СССР", 1958, т. 123, № 6, с. 978-80; [18] Дэвис М., Путнам X., РобинсонД ж., "Математика", 1964, т. 8, № 5, с. 69-79; [19] Робинсон Д ж., "Математика", 1964, т. 8, М!> 5, с. 3-14; [20] Матиясевич Ю. В., "Докл. АН СССР", 1970, т. 191, М 2, с. 279 — 82; [21] Матиясевич Ю. В., "Изв. АН СССР. Сер. матем.", 1971, т. 35, Mb 1, с. 3-30. С.