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

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

Например, вместо схемы рис. 12 возникает одномерная строка символов

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

II I I Ы-

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

2. Для характеристики функциональной схемы и кон­ фигураций вовсе не существенны специфические начертания букв внешнего алфавита и алфавита состояний, которые в ней фигурируют. Например, если всюду в таблице рис. 12 или в соответствующей ей строке заменить букву (3 бук­ вой Ь, то от этого ничего в наших рассмотрениях не изме­ нится. Важно лишь то, чтобы различные объекты были за­ даны различными символами и чтобы можно было различить буквы состояний от букв внешнего алфавита.

Конечно, можно было выбрать другие буквы, отличные от Л, П, Н, и для обозначения сдвигов (влево, вправо, от­ сутствие сдвига), однако при этом должно быть четко ого­ ворено, какой именно буквой такой сдвиг обозначается. Здесь сказывается тот факт, что каждая из трех букв обо­ значает вполне определенное действие, которое не заменимо другим.

Учитывая эти обстоятельства, заменим в строке Q каж­ дую отдельную букву некоторой последовательностью из единиц и нулей (кодовой группой) так, чтобы различные буквы заменялись различными кодовыми группами, но одна и та же буква заменялась бы всюду, где бы она ни встре­ чалась, одной и той же кодовой группой. В результате такой замены, например, строка Q перейдет в некоторую строку Q'. Для того чтобы по й ' можно было восстановить Q, способ

128

Теперь уже нетрудно сообразить, как изменить форму­ лировки указаний 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