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

АЛГОРИТМИЧЕСКАЯ ПРОБЛЕМА, проблема, в которой требуется найти единый чётко описанный метод (алгоритм) для решения бесконечной серии однотипных единичных задач. Такие проблемы называют также массовыми проблемами. Предписание для работы алгоритма должно быть настолько чётким, чтобы эту работу можно было поручить машине. Алгоритмические проблемы возникли и решались в различных областях математики на протяжении всей её истории. После того как в 1930-х годах в математической логике было выработано определение понятия алгоритма, появилась возможность доказывать, что некоторые алгоритмические проблемы неразрешимы, то есть искомые в них алгоритмы не существуют, поэтому алгоритмические проблемы стали формулировать как задачи существования соответствующего алгоритма и его нахождения в случае, если он существует.

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

Первые примеры неразрешимых алгоритмических проблем были обнаружены в самой теории алгоритмов. К ним относится проблема распознавания самоприменимости машин Тьюринга, проблема остановки алгоритма, проблема распознавания принадлежности числа данному нерекурсивному множеству натуральных чисел. Из неразрешимых алгоритмических проблем в области математической логики следует отметить проблему распознавания тождественной истинности формул исчисления предикатов 1-й ступени (А. Чёрч, 1936) и проблему распознавания истинности замкнутых формул в арифметике.

В середине 20 века была доказана неразрешимость ряда классических алгоритмических проблем в традиционных разделах математики. Среди них — результат А. А. Маркова и американского математика и логика Э. Л. Поста о неразрешимости поставленной А. Туэ (1914) проблемы распознавания равенства слов в полугруппах, заданных определяющими соотношениями (1947), аналогичный результат для групп (П. С. Новиков, 1955), результат С. И. Адяна (1957) об алгоритмической нераспознаваемости почти всех инвариантных групповых свойств, в том числе свойств единичности, конечности, периодичности, результат Маркова о неразрешимости проблемы распознавания гомеоморфизма для 4-мерных многообразий (1958) и результат Ю. В. Матиясевича (1971) о несуществовании алгоритма для распознавания разрешимости диофантовых уравнений в целых числах (10-я проблема Гильберта).

Лит.: Адян С. И., Дурнев В. Г. Алгоритмические проблемы для групп и полугрупп // Успехи математических наук. 2000. Т. 55. Вып. 2.