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

согласно схеме рис. 18 появляется состояние q2 и процесс продолжается. В частности, если первая конфигурация взята как на рис. 17, то восьмая конфигурация получится уже такой, как на рис. 19. Как будет продолжаться процесс, видно из столбца состояния q2. начнется серия сдвигов вправо сквозь все цифры и все палочки, пока будет достиг­ нута первая пустая ячейка при входной паре Д q2 (см. кон­ фигурацию 14 рис. 19), тогда последует сдвиг влево с одно­ временным переходом в состояние q1 (конфигурация 15

рис. 19). Таким обра-

п+1 будет заменена записью числа п + 2. Если первоначаль­ но в наборе было k палочек, то после /е циклов работы все они будут стерты, а вместо первоначальной записи числа п появится запись числа п + к. По окончании &-го цикла машина опять окажется в состоянии qu но в ее поле зрения уже будет не палочка (палочки все уже стерты), а самая первая цифра (т. е. цифра единиц) в записи числа п + k (предпоследняя конфигурация на рис. 19). Как видно из схемы рис. 18, в этом случае произойдет остановка (послед­ няя конфигурация на рис. 19).

Из всего сказанного вытекает, что если к началу работы машины на ленте будут записаны цифра 0 и набор из k па­ лочек, то машина сотрет все эти палочки, а вместо нуля появится десятичная запись числа 0 + k, т. е. k. На самом же деле к началу работы можно обойтись и без нуля, так как если вместо нуля фигурирует знак Д, то при состоя­ ниях q0 и q1 машина ведет себя так же, как если бы это был нуль (см. схему рис. 18). Итак, предложенная схема рис. 18 действительно описывает алгоритм перевода набора k па­ лочек в десятичную запись их числа k.

Попытаемся оценить, сколько при этом тактов работы затрачивает машина. Поскольку осуществляемый ею про-

80

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

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

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

ным знаком, например звездочкой *. Этот знак тоже вхо­ дит во внешний альфавит машины.

9.3. Сложение. На ленту подается пара чисел, напри­ мер,

В результате должна получиться их сумма, в данном случае

81

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

Начальные условия: в поле зрения установлена самая

влево сквозь все палочки и звездочку до первой пустой ячей­ ки слева (конфигурация 24), тогда (входная пара [\qx) происходит сдвиг вправо, в поле зрения устанавливается первая из оставшихся палочек левее звездочки, и машина переходит в состояние q0 (конфигурация 25). В результате этого цикла одна палочка левого слагаемого оказалась пе­ ренесенной в правое слагаемое. Если левее звездочки было первоначально k палочек, то через k циклов все будут пере­

(предпоследняя конфигурация). Тогда (входная пара*^0) звездочка вычеркивается, и машина останавливается (по­ следняя конфигурация). Вместе с тем получена уже и нуж­ ная сумма.

Итак, если первое слагаемое равно k, а второе s (т. е. соответственно левее и правее звездочки первоначально

как нужно изменить схему рис. 20 для того, чтобы при пер-

82

воначальной подаче на ленту пары чисел т, п, например

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

новить после каждого сложения и снова прибавить к числу, изображенному правее звездочки. Этого можно добиться, например, тем, что палочки левого набора не стираются, а временно заменяются какими-то знаками или пометками. На рис. 22 изображена схема, в которой роль такой помет­ ки играет буква а. В соответствии с этим, вхождение пу­ стого знака Д в первой строке схемы 20 отвечает вхождению знака а в первой строке схемы 22 и, кроме того, в схеме рис. 22 имеется еще четвертая строка для буквы а; в этой

первого сложения, необходимо, чтобы в схеме рис. 22 вме­ сто знака «!», который в схеме рис. 20 появляется при вход­ ной паре *q0, входил знак другого состояния, обеспечп-

83