Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

решения задач то его можно перестроить в алгоритм, решающий серию задач {а,}. Если же ранее было установ­

серии {£>;}. Такая ситуация как раз и используется часто для установления алгоритмической неразрешимости; имен­ но для исследуемой проблемы 25 отыскивают проблему U, которая заведомо алгоритмически неразрешима, но вместе с тем сводится к проблеме 93.

Приведем пример сводимости проблем из теории машин Тьюринга.

Для произвольной машины Тьюринга М можно пост­ роить другую машину Л'/*, которая связана с ней следую­ щим образом*). Пусть /< — какая-нибудь конфигурация в /И; тогда и в /И* ей сопоставлена конфигурация К* с со­ блюдением двух условий:

1) если М не применима к /<, то и М* не применима

к/<*;

2)если М применима к /<, то М* тоже применима к /(*, причем перерабатывает ее в некоторую фиксированную заключительную конфигурацию (например, в обозреваемой ячейке вписана буква т, а все остальные ячейки пусты).

если в качестве начальной конфигурации взята /(,, то перей­ дет ли машина (после конечного числа тактов) в конфигу­ рацию Кг или нет?

Пользуясь введенными выше терминами, можно сказать, что проблема применимости сводится к проблеме переводимости. Действительно, для распознавания применимости ма­ шины М к конфигурации /< достаточно выяснить, переводима ли в машине /И* конфигурация К* к стандартной конфигу­ рации т. Отсюда вытекает, что проблема переводимое™ тоже алгоритмически неразрешима.

Более того, проблема переводимое™ остается алгорит­ мически неразрешимой, если в качестве /<2 брать только такие конфигурации, которые заведомо являются заклю­ чительными.

15.3. Краткий исторический обзор. Впервые алгорит­ мическая неразрешимость была установлена для проблем,

*> Доказательство этого утверждения можно рекомендовать в ка­ честве упражнения.

134

возникающих в самой математической логике (проблема выводимости) и в теории алгоритмов (например, проблемы применимости, переводимое™ и т. п.). Однако позднее вы­ яснилось, что подобные явления имеют место и для неко­ торых, казалось бы, более узких проблем, возникающих в самых разнообразных разделах математики. В первую очередь здесь следует указать на ряд алгебраических про­ блем, приводящих к различным вариантам проблемы слов, которые исследовались советскими математиками.

Проблема эквивалентности слов для ассоциативных исчислений (см. § 4,) была сформулирована еще в 1914 г. норвежским математиком Туэ. Им же был предложен ал­ горитм для распознавания эквивалентности слов в некото­ рых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для л ю б о г о ассоциативного исчисления и для любой пары слов в нем позволили бы уста; новить, эквивалентны эти слова или нет.

В 1946 и 1947 гг. советский математик Андрей Андреевич

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

В следующем параграфе приводится одни пз вариантов доказательства теоремы о невозможности алгоритма для распознавания эквивалентности слов в любом ассоциатив­ ном исчислении.

Большое впечатление произвел в математическом мире опубликованный в 1955 г. результат Петра Сергеевича Но­ викова, доказавшего алгоритмическую неразрешимость про­ блемы тождества теории групп*'. Эта проблема заключается в распознавании эквивалентности слов для ассоциативных исчислений специального вида: рассматриваются лишь такие ассоциативные исчисления, в которых для каждой буквы а алфавита в списке допустимых подстановок исчисления имеется подстановка вида

ааД,

*> За эту работу П. С. Новикову в 1957 г. присуждена Ленинская премия-

где а — какая-либо буква того же алфавита (возможно, совпадающая с а). Содержательный смысл этого требования

как некоторые сложные преобразования, получаемые путем у м н о ж е н и я элементарных преобразований, задава­ емых соответствующими буквами, образующими это слово. В таком случае пустое слово Д задает тождественное преоб­ разование, ничего не изменяющее (сравни с § 4), а наличие допустимых подстановок вида аа — Д означает, что для каждого элементарного преобразования (задаваемого бук­ вой а) существует элементарное преобразование (задаваемое буквой а) такое, что последовательное их осуществление дает тождественное преобразование. Не вдаваясь в даль­ нейшие подробности, отметим лишь, что рассмотрение та­ ких множеств преобразований, называемых группами пре­ образований, представляет исключительно большой теоре­ тический и практический интерес, а само понятие группы является одним из самых основных понятий современной математики.

Теперь нам нужно уяснить себе, что весьма важный результат Маркова — Поста, отмеченный выше, сам по себе не позволяет делать никаких выводов по существу про­ блемы тождества теории групп. Дело в том, что те индиви­ дуальные ассоциативные исчисления, для которых А. А. Мар­ ков иЭ. Пост установили алгоритмическую неразрешимость проблемы эквивалентности, как раз не удовлетворяют тре­ бованию, отмеченному выше, которое является существен­ ным при постановке проблемы тождества теории групп. Поэтому возможность алгоритма для этой последней про­ блемы не исключается результатами Маркова— Поста. На­ дежда на создание этого алгоритма еще не была полностью утрачена, и поиски его еще продолжались, когда стал из­ вестен результат П. С. Новикова, согласно которому такого алгоритма не существует. П. С. Новиков построил индиви­ дуальный пример ассоциативного исчисления, удовлетво­ ряющего указанному требованию, для которого невозмо­ жен алгоритм, распознающий эквивалентность; тем более невозможен единый алгоритм для всех рассматриваемых групп.

Первые примеры, построенные А. А. Марковым и П. С. Новиковым для опровержения алгоритмической раз­ решимости исследуемых проблем, оказались весьма гро­ моздкими и насчитывали сотни допустимых подстановок.

136

Была поставлена задача построения по возможности более простых примеров. В этом направлении блестящий успех был достигнут ленинградским математиком Г. С. Цейтиным; для приведенного в п. 4.2 исчисления, построенного Цей­ тиным и насчитывающего всего лишь семь допустимых под­ становок, проблема эквивалентности слов также алгорит­ мически неразрешима. В течение последних тридцати лет были выявлены и многие другие алгоритмические пробле­ мы, для которых невозможен разрешающий алгоритм. Для некоторых из них это очень долго не удавалось установить, хотя они уже давно числились в списке кандидатов на ал­ горитмически неразрешимые проблемы. До настоящего вре­ мени в этом отношении рекордной остается проблема Гиль­ берта о диофантовых уравнениях (см. § 1). Лишь в конце 1969 г. молодому ленинградскому математику Ю. В. Матиясевичу удалось доказать, что эта знаменитая проблема ал-, горитмнчески неразрешима.

с поиском разрешающего алгоритма. Может даже оказаться, что в результате такой модификации проблема из алгорит­ мически неразрешимой становится алгоритмически разре­ шимой*'.

Обнаружение алгоритмически неразрешимых проблем создало в науке такую ситуацию, когда математик, стремя­

в книге «Алгоритмы и машинное решение задач» (М., Физматгиз, 1960).

Читатель Г. Н.Спиридович из Ленинграда, не поверив на слово автору (и поделом!), что для исчисления, приписанного им Г. С. Дентину, проблема эквивалентности слов алгоритмически не­ разрешима, сумел найти разрешающий алгоритм.

Автор признателен Г. Н. Спиридовичу и Г. С. Цейтину за то, что они обратили его внимание на допущенную неточность.

137

таться с тем, что такой алгоритм может и не существовать. Поэтому параллельно с усилиями, направленными на по­ иски желаемого алгоритма, приходится прилагать усилия для доказательства невозможности такого алгоритма. В за­ висимости от того, на каком из этих направлений будет до­ стигнут успех, н выяснится окончательно картина: либо будет найден разрешающий алгоритм, либо установлена алгоритмическая неразрешимость проблемы.

§ 16. НЕВОЗМОЖНОСТЬ АЛГОРИТМА ДЛЯ ПРОБЛЕМЫ ЭКВИВАЛЕНТНОСТИ СЛОВ

На первом этапе (п. 16.1) рассматриваются ассоциативные исчис­

означает, что предыдущее слово переходит в последующее в резуль­ тате разового применения ориентированной подстановки. Устанав­ ливается, что не существует алгоритма распознавания переводимос­ тн слов в произвольном одностороннем исчислении. Наряду с исчис­ лениями л будем рассматривать исчисления л' . Исчисление л ' по­ лучается из соответствующего л путем замены каждой из односто­

Поэтому получаемый результат для односторонних исчислений не распространяется автоматически на любые исчисления.

На втором этапе (п. 16.2) доказательства как раз и преодолевает­ ся эта трудность и устанавливается теорема неразрешимости для

переводимостн для односторонних исчислений. Поскольку первая является алгоритмически неразрешимой, то таковой является и вто­ рая. Приводимые ниже понятия и конструкции предназначены как раз для сведения первой проблемы ко второй.

138