Математическая энциклопедия - алгоритмическая проблема

проблема, в к-рой требуется найти единый метод ( алгоритм).для решения бесконечной серии однотипных единичных задач. Такие проблемы иногда наз. также массовыми проблемами. А. п. возникали и решались в различных областях математики на протяжении всей ее исторпи; однако нек-рые из них долгое время не поддавались решению. Причина этого выяснилась лишь после того, как в 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]).