книги из ГПНТБ / Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы

Теперь уже нетрудно сообразить, как изменить форму­ лировки указаний 1—9 из первоначального описания алго­ ритма подражания для того, чтобы получить алгоритм, ко­ торый перерабатывает шифр схемы подражаемой машины и шифр начальной конфигурации в шифр результирующей конфигурации. Ограничимся только отдельными иллюст­ рациями:

У к а з а н и е 1. Обозревайте в шифре конфигурации кодовую группу (единственную), расположенную непосред­ ственно левее кодовой группы с нечетным числом нулей.

У к а з а н и е 2 и 3. Отыщите в шифре схемы пару соседних кодовых групп, одинаковую с парой кодовых групп в шифре конфигурации, в которой первая группа является обозреваемой.

У к а з а н и е 6. Если в обозреваемой тройке кодовых групп из шифра схемы второй является группа 1001, то в шифре конфигурации замените кодовую группу с нечетным числом нулей третьей' кодовой группой из этой обозревае­ мой тройки.

Дальнейшее рассмотрение этого алгоритма позволяет сводить каждую операцию над кодовыми группами к цепи стандартных операций, осуществимых в тыоринговой ма­ шине (замена одного знака другим, сдвиг на одни шаг п т. п.). При этом, кроме знаков 1 и 0, из которых построены шифры, будут участвовать и другие буквы, например буква, отделя­ ющая один шифр от другого, буквы, играющие роль времен­ ных пометок при просмотре единиц и нулей (сравнить с ал­ горитмом Евклида) и другие.

В конечном счете в результате такой детализации алгоритм подражания описывается функциональной схе­

ринга.

В связи с этим фактом всевозможные функциональные схемы (или их шифры) можно толковать двояко:

1) схема описывает логический блок с п е ц и а л ь н о й машины Тьюринга, реализующей соответствующий алго­ ритм (это и есть точка зрения, которая проводилась перво­ начально);

130

2) схема описывает программу, подаваемую на ленту универсальной машины для реализации соответствующего алгоритма.

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

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

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

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

15.1. Теорема Чёрча. Переход от расплывчатого понятия алгоритма к точному понятию машины Тьюринга, которая может быть задана своим шифром, позволяет уточнить и во­ прос об алгоритмической (или машинной) разрешимости того или иного круга задач. Именно теперь этот вопрос следует понимать так: существует ли машина Тьюринга, решающая данный класс задач, или же такой машины не существует? (Что значит «машина Тьюринга решает некоторый класс задач» см. в § 8.)

На этот вопрос теория алгоритмов в ряде случаев дает отрицательный ответ. Один из первых результатов такого типа, установленный американским математиком Чёрчем

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

15.2. Распознавание самоприменимости и переводимости. Доказательствам невозможности, приводимым в тео­ рии алгоритмов, присуща та же математическая строгость, что и доказательствам невозможности, приводимым в других областях математики (например, невозможность трисекции угла с помощью циркуля и линейки, или невозможность определения общей меры для стороны квадрата и его диа­ гонали). Эскиз такого доказательства мы приведем ниже для проблемы распознавания самоприменимости.

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

взаключительной конфигурации, подавая сигнал об оста­ новке; 2) машина не применима к этой конфигурации, т. е. сигнал об остановке никогда не наступает и машина впадает

вбесконечный процесс. Возникает следующая массовая проблема.

машины и конфигурация в ней; узнать, применима машина к этой конфигурации или нет. Это—типичная задача на построение алгоритма, ибо для ее решения надо найти об­

изображен ее же собственный шифр (т. е. шифр функцио­ нальной схемы), записанный в алфавите машины*). Если машина применима к такой конфигурации, то будем назы­ вать ее самоприменимой, в противном случае — несамоприменимой. Тогда можно сформулировать следующую мас­ совую проблему.

*' Предполагается, что по внешнем алфавите машины имеются символы Л , 0, 1, а может быть, и другие.

132

мости, алгоритмически неразрешима.

Очевидно, из этой георемы немедленно вытекает и алго­ ритмическая неразрешимость более общей проблемы при­ менимости.

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

Итак, В применима ко всякому несамоприменимому шифру (вырабатывая при этом символ т) и не применима к самоприменимым шифрам. Однако это приводит к проти­ воречию. Действительно,

1) пусть эта машина В самоприменима, тогда она при­ менима к своему шифру В' и перерабатывает его в символ т;

Полученное противоречие доказывает теорему.

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

133

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

серии {£>;}. Такая ситуация как раз и используется часто для установления алгоритмической неразрешимости; имен­ но для исследуемой проблемы 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

Совокупность всех активных ячеек образует сплошную часть лен­

139