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

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

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

это означает, что содержание обозреваемой ячейки не из­ меняется; при / = 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