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

личием элементарных операций, в которых участвует сразу содержание трех ячеек памяти.

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

это означает, что содержание обозреваемой ячейки не из­ меняется; при / = 1 это означает, что если в обозреваемой ячейке хранился какой-либо знак, то он гасится. Даль­ нейшее упрощение заключается в том, что при переходе машины от одного такта к непосредственно следующуему такту адрес обозреваемой ячейки может изменяться не бо­ лее, чем на одну единицу, т. е. обозревается соседняя слева или соседняя справа ячейка, или же обозревается та же ячейка, что и в предыдущем такте.

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

П — обозревать соседнюю справа ячейку,

Л— обозревать соседнюю слева ячейку.

Н— продолжать обозревать ту же ячейку.

70

из конечного числа состоянии: складывающее, вычитаю­ щее и т. д.

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

<7;, поданных на вход. Команды, обу- - словливающие срабатывание машины на каждом отдель­

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

реализует функцию, сопоставляющую каждой паре знаков

71

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

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

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

Вэтой схеме отражено разделение памяти на внешнюю

ивнутреннюю. Внешняя память изображена ячейками бе­ сконечной ленты, предназначенными для хранения инфор­ мации, закодированной в символах внешнего алфавита; внутренняя память—двумя ячейками для хранения очеред­ ной команды: Q-ячейка хранит знак состояния и Р-ячейка — знак сдвига. В этих двух ячейках происходит задержка

знаков Р, qt, полученных на выходе логического блока в дан­ ном такте работы, до начала следующего такта. Из Q-ячейки по так называемой линии обратной связи в логический

блок £ поступает знак состояния qt, выработанный этим же блоком в предыдущем такте. Из Р-ячейки знак сдвига на­ правляется в механизм сдвига.

Логический блок общается с внешней памятью посред­ ством читающей и записывающей головки (называемой

72

впредь просто головкой), в которой вмонтированы один" входной канал (для считывания) и один выходной канал (для записи) логического блока; на рис. 13 головка изобра­ жена треугольником, установленным против «обозревае­ мой» ячейки. Функции управления теперь уже чрезвычай­ но упрощены и заключаются по существу лишь в обеспече­

(на рис. 13 последовательность из пяти палочек) и в «поле зрения» машины устанавливается определенная начальная ячейка (на чертеже — ячейка, содержащая четвертую спра­ ва палочку), а в ячейки Р и Q вводятся знаки начального состояния и начального сдвига (предположим, ql и Н). Дальнейший процесс протекает уже автоматически и одно­ значным образом определяется функциональной схемой машины. Посмотрим, например, что произойдет в том слу­ чае, когда задана функциональная схема рис. 12.

т. е. знак а оставляется без изменения с переходом к коман­

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

73

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

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

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

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

Впрочем, несколько позднее (см. § 13) станут ясными другие, причем очень важные причины, по которым такая двойственная интерпретация оправдана. Имея в виду выше­ сказанное, мы будем свободно пользоваться терминами «функциональная схема машины Тьюринга» и «тьюрин­ гова программа» как синонимами. Соответственно, сино­ нимами будем считать и термины «тыорингово программи­ рование», «построение тыоринговых машин», «построение функциональных схем тыоринговых машин».

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

74

Под k-u конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к на­ чалу k-vo такта, причем под обозреваемой ячейкой записан знак того состояния, которое подается в логический блоки к началу этого же такта. Таким образом, в k-i\ конфигурации явно указана входная пара знаков, следовательно, можно, обращаясь к функциональной схеме, определить соответ­ ствующую выходную тройку, а тем самым и (k - f 1)-ю конфигурацию.

В разобранном выше примере первая и вторая конфигу­ рации таковы:

от первой конфигурации ко второй обусловливается выход­ ной тройкой aHq2, соответствующей на рис. 12 входной

паре | qv

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

В дальнейшем будем пользоваться следующей упрощен­ ной записью функциональных схем, что сделает схему более обозримой и удобной при выписывании конфигураций. Именно, мы откажемся от полной записи выходной тройки SjPqv опуская знаки s;- и qh если они не отличаются от соответствующих входных знаков, а также знак N, указы­ вающий на отсутствие сдвига. В частности, это позволяет

75

полностью опустить столбец, соответствующий стоп-со­ стоянию. Аналогично будем поступать и при записи тыоринговых команд; например, aq2 -н» Л вместо aq2 ->- а/7<72. Упрощенная запись для схемы рис. 12 приведена на рис. 14,

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

ния стоп-состояния.

§9. РЕАЛИЗАЦИЯ АЛГОРИТМА

ВМАШИНЕ ТЬЮРИНГА (ТЬЮРИНГОВО ВЫЧИСЛЕНИЕ)

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

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

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

9.1.Переход от п к га - f 1 в десятичной системе счисле­ ния. Решается задача следующего типа.

Дана десятичная запись числа п (т. е. представление натурального числа я в десятичной системе счисления);

требуется указать десятичную запись числа п - f 1.

76

Для этого берется внешний алфавит, состоящий из де­

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

чится, если не учитывать в ней последнюю строку и послед-

89 !

9О Л

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

Итак, дольше всего машина работает, когда десятичная запись числа я состоит сплошь из девяток; очевидно, в этом случае число тактов равно ] log1 0 n [ -4- 1; (обозначение ]х[ имеет смысл: ближайшее от х с избытком целое число). Вообще говоря, для других натуральных п число тактов меньше, чем ] log1 0 п [ + I .

77

На рис. 16 выписаны соответствующие конфигурации при п = 389.

Поясним теперь смысл расширенной таблицы, помещен­ ной на рис. 15. Она задает функциональную схему машины, в которой имеется еще одно состояние — ^ ; кроме того, во внешнем алфавите имеется еще один знак, а именно «па­ лочка». Если к началу работы машина настроена в состоянии q0, а на ленте нет ни одной палочки, то работа будет про­ текать в точности так же, как если бы мы имели дело с машиной из предыдущего примера. Это непосредственно очевидно из того, что при указанных условиях последняя

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

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

к числу п + 1. Условимся этот процесс называть контроли­ руемым переходом от десятичной записи п к десятичной за­ писи п + 1-

На рис. 17 выписаны конфигурации для набора из пяти палочек и для п = 389.

Допустим, что в начальной конфигурации правее деся­ тичной записи числа п имеется v палочек. Оценим число t

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

78

ной записи; далее, она затрачивает еще 1г < log1Qn + 1 тактов на переход к десятичной записи числа п + 1. Итак,

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

Дана конечная совокупность палочек, вписанных в ячейки, взятые подряд без пропусков (такие совокупности будем на­ зывать наборами палочек); требуется записать в десятич­

Короче: пересчитать набор палочек.

Такая схема задана на рис. 18. Для того чтобы убедить­ ся в том, что эта схема действительно описывает нужную машину (алгоритм), полезно сравнить ее со схемой расширен­ ной табл. рис. 15. Столбец q0 в схеме рис. 18 отличается от столбца q0 в схеме рис. 15 лишь тем, что вместо состояния«!» в нем всюду фигурирует новое состояние <72; различие столбцов qx не имеет существенного значения в работе схе­ мы рис. 15. Поэтому, если на ленте задана десятичная за­ пись числа п, а правее ее — набор палочек, если, далее, в по­ ле зрения машины, как и прежде, установлена самая правая палочка, а сама машина настроена в состоянии qu то в ма­ шине будет вначале протекать такой же процесс, как и при схеме рис. 15; именно палочка набора будет стерта, а за­ пись числа п будет-заменена записью числа п + 1. Однако в то время как согласно схеме рис. 15 на этой стадии про­ цесса появится состояние I, т. е. процесс прекращается,

79