НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ

— массовые проблемы, для которых не Существует эффективных методов разрешения. В интуитивном смысле массовая (алгоритмическая) проблема — это бесконечный класс родственных единичных конкретных проблем, каждая из которых требует ответа «да» или «нет», а метод разрешения массовой проблемы — это единый общий метод, дающий правильный ответ для каждой единичной проблемы. Фактически произвольную массовую проблему можно сформулировать как проблему распознавания некоторого свойства Е элементов данного бесконечного мн-ва А; при этом единичные проблемы, составляющие эту массовую проблему, связываются с элементами мн-ва А, и каждая из них состоит в том, что требуется узнать, обладает или нет свойством Е соответствующий элемент мн-ва А.

Рассматривая массовую проблему, исследователь обычно интересуется эффективными (конструктивными) методами ее разрешения, методами, которые дают решение любой единичной проблемы за конечное число шагов. Мн-во А, для элементов которого формулируется массовая проблема, предполагается конструктивным (допускающим возможность применения алгоритмов). Поэтому задача ставится так: найти алгоритм, который применим к любому элементу мн-ва А и для каждого данного дает «1» или «0» в зависимости от того, обладает или нет элемент а свойством Е. Массовая проблема наз. неразрешимой, если такого алгоритма не существует.

Почти все разделы математики изобилуют массовыми проблемами. В алгебре, напр., возникает следующая массовая проблема: для произвольного целочисленного многочлена от одного неизвестного узнать, имеет ли он целый корень (здесь, очевидно, А — мн-во всех многочленов от одного переменного, коэффициенты которых — целые числа, а Е - свойство многочлена иметь целый корень). Существует тривиальный алгоритм решения этой массовой проблемы, основанный на том, что любой целый корень целочисленного многочлена от одного неизвестного является делителем его свободного члена. Известная 10-я проблема Гильберта состояла в отыскании алгоритма разрешения для более широкой массовой проблемы, в которой мн-во целочисленных многочленов от одного неизвестного заменено мн-вом всех целочисленных многочленов от произвольного числа неизвестных. Эта проблема уже оказалась неразрешимой.

В 30-х гг. 20 ст., благодаря работам австр. матем. К. Гёделя (р. 1906) и амер. матем. А. Черча (р. 1903), понятие алгоритм, неразрешимости было уточнено с привлечением понятий нумераций (см. Нумераций теория) и

частичной рекурсивности. Впоследствии англ. матем. А. Тьюринг (1912—54) предложил другое уточнение понятия неразрешимости, использовав понятие Тьюринга машины. Эти уточнения, как оказалось, приводят к равнообъемным понятиям неразрешимости. Известны и др. уточнения, дающие тот же результат: нормальные алгорифмы сов. матем. Л. А. Маркова (р. 1903), формальные исчисления амер. матем. Э. Поста (1897—1954) и др.

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

В 1947 независимо друг от друга А. А. Марков и Э. Пост доказали алгоритм, неразрешимость проблемы тождества в полугруппах. Это был первый пример Н. а. п., возникшей вне области матем. логики и оснований математики. Известно, что всякая полугруппа может быть задана с помощью систем образующих и определяющих соотношений. Если полугруппа не является свободной (т. е. существует хотя бы одно соотношение между ее образующими), то представление любого ее элемента через образующие неоднозначно. Поэтому возникает задача: для данных двух выражений, представляющих собой произведения образующих, узнать, равны ли эти произведения между собой. В том случае, когда полугруппа задается конечными системами образующих и определяющих соотношений, нужно найти алгоритм, решающий любую такую задачу. А. А. Марков и Э. Пост построили полугруппы с неразрешимой проблемой тождества. Аналогичная проблема для групп — проблема тождества в группе — занимает важное место в теории групп. Сов. матем. П. С. Новиков (р. 1901) в 1952 доказал ее алгоритм, неразрешимость. За последнее время была доказана алгоритм, неразрешимость ряда проблем в теориях полугрупп, групп, структур, колец, полей и др. алгебр, систем (см. Элементарные теории).

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

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

Известны два способа доказательства алгоритм. неразрешимости: прямой, основанный на т. н. «диагональном» методе, и косвенный, использующий сводимость к данной проблеме другой массовой проблемы, неразрешимость которой была доказана раньше. Идею прямого метода доказательства алгоритм, неразрешимости объясним на примере т. н. проблемы остановки машины Тьюринга. Эта проблема заключается в нахождении алгоритма, который позволял бы по любой машине Тьюринга и любой конфигурации ленты узнать, остановится или нет машина, начав работу с этой конфигурации. Выберем к.-л. эффективную нумерацию всех машин Тьюринга и обозначим через ту машину, которая получает номер х. Пронумеруем все конфигурации ленты, причем так, чтобы каждое натуральное число являлось номером некоторой конфигурации. Обозначим через конфигурацию с номером х.

Перейдем теперь к неформальному доказательству того, что не существует алгоритма распознавания остановки произвольной машины Тьюринга для произвольной начальной конфигурации ленты. Предположим, что такой алгоритм есть. Тогда, очевидно, частично рекурсивной будет функция определенная следующим образом: не определено, если х не является номером никакой машины; равно 1 или 0 в зависимости от того, остановится или нет машина начав работу с конфигурации Значит, существует машина Тьюринга, вычисляющая ф-цию Эту машину легко переделать в другую машину, отличающуюся от первой только тем, что когда первая машина в качестве результата вычисления дает 1, вторая попадает в цикл. Пусть у — номер второй машины. Запустим машину с конфигурации Если машина остановится, то, по самому определению машины должно быть и, следовательно, по определению ф-ции машина не остановится. Если машина не остановится, то, поскольку определена в и, следовательно, по определению функции машина остановится. Полученное противоречие является доказательством Н. а. п. остановки машины Тьюринга.

Косвенный метод доказательства алгоритм, неразрешимости разъясним на примере т. н. -сводимости. Пусть имеются две массовые проблемы. Первая заключается в распознавании свойства Е элементов мн-ва А, вторая — в распознавании свойства F элементов мн-ва В. Говорят, что первая массовая проблема m - сводима ко второй, если существует эффективное отображение мн-ва А в мн-во В такое, что для любого утверждения: обладает свойством обладает свойством одновременно истинны или ложны. Легко видеть, что, если одна массовая проблема - сводима к другой и первая проблема алгоритмически неразрешима, то вторая проблема также будет алгоритмически неразрешимой. См. также Алгоритмов теория.

Лит.: