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

согласно схеме рис. 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

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

В схеме рис. 22 нет знака «!» (остановки), поэтому про­ цесс, описываемый ею, не имеет конца. Читатель теперь без особого труда проверит, что соответствующая машина реализует как раз неограниченное прибавление числа, изображенного левее звездочки, к числу, изображенному правее ее. Если правее звездочки к началу работы нет па­ лочек (т. е. второе число нуль), то правее звездочки появят­ ся т палочек, потом 2 т, потом Зт и т. д. без конца.

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

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

9.5. Нахождение общего наибольшего делителя. Рас­ смотрим теперь, как выглядит в машине Тьюринга алго­ ритм Евклида для нахождения общего наибольшего дели­ теля чисел а, Ь. Этот алгоритм был уже ранее описан нами дважды: первый раз в виде словесного предписания, а вто­ рой раз в виде программы для электронной машины с авто­ матическим управлением. На этот раз алгоритм мы зададим в виде функциональной схемы тьюринговой машины и про­ следим процесс вычисления в машине. Этот процесс скла­

84

рис. 14; ее внешний алфавит состоит из четырех знаков:

Л. I. «. I5-

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

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

Машина же заменяет палочку первого числа символом а, потом заменяет палочку второго числа символом |3, потом

85

опять возвращается к палочкам первого числа и заменяет еще одну из них символом а, потом заменяет еще одну палочку второго числа символом р и т. д.

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

ществлен при участии одних лишь состояний <?j и <?2- Сле­ дующий такт дает уже конфигурацию I I I .

Как видно из столбца состояния <?4 в схеме, представ­ ленной на рис. 14, теперь начинается сдвиг вправо с заме­ ной всех а пустыми знаками Д (т. е. с вычеркиванием всех а) и заменой всех |3 палочками. После того как последняя спра­ ва Р уже заменена палочкой, на ленте возникает конфигу­ рация IV рис. 24, а вслед за тем конфигурация V. Таким образом, после цикла сравнения произошел цикл вычи­ тания первого числа из второго, в результате которого мень­

86

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

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

В заключение параграфа условимся еще в определенном стандартном задании исходной и результирующей инфор­ мации при вычислениях на машинах Тьюринга. Как уже неоднократно указывалось, эта информация изображается в виде исходного слова Р и результирующего слова R, где Р и R — слова в заранее указанных подалфавитах внеш­ него алфавита машины ЭД. Однако до сих пор у нас не было единого соглашения по поводу того, какие ячейки должны обозреваться в начале и в конце вычисления. Например, при решении задач I и 3 считалось, что в начальной кон­ фигурации обозревается самый первый символ слова Р, а при решении задачи 2 — самый левый символ, при состав­ лении же функциональной схемы рис. 14 алгоритма Евк­ лида эта роль отводилась одному из символов, располо­ женных где-то внутри слова. Что же касается заключитель­ ных конфигураций, то там тоже допускались различные варианты. Теперь мы условимся о том, что впредь (если противное не оговорено) в начальной и заключительной кон­ фигурациях должен обозреваться первый символ слова Р или соответственно слова R. В этом случае будем говорить о стандартном изображении слов Р и R посредством началь­ ной и заключительной конфигурации. Если машина Тью­ ринга перерабатывает слово Р, изображенное стандарт­ но, в слово R, также изображенное стандартно, то это будем записывать так: R = 9Л(Р).

87

У п р а ж н е н и я . Для рассмотренных выше задач составить функциональные схемы, пригодные для стандарт­ ного изображения исходных данных и результатов. Со­ ставить функциональную схему для операции - над нату­ ральными числами, определяемой условиями: х - у — = х — у при х <; у, х - у — 0 при х < у.

Рассмотрим алгоритм, который по паре натуральных чисел х, у составляет пару натуральных чисел и, v, где и — частное, v — остаток при делении х на у. Построить соответствующую функциональную схему.

§ 10. ПРОГРАММИРУЮЩИЕ АЛГОРИТМЫ

В предыдущем параграфе для нескольких сравнительно простых алгоритмов было показано, каким образом их мож­ но реализовать в машинах Тьюринга; точнее, были построе­ ны соответствующие тыоринговы программы. Вообще со­ ставление алгоритма отнюдь не легкое дело; оно может потребовать глубокого анализа содержания рассматривае­ мых задач и большой изобретательности. Если же мы хотим представить в виде тыоринговой программы алгоритм, пер­ воначально описанный в иных привычных терминах, то у нас появляются дополнительные трудности; они связаны с чрезвычайной простотой тыоринговых операций и с край­ не ограниченным доступом машины к ее внешней памяти: на каждом такте происходит преобразование лишь в одной ячейке и возможен сдвиг лишь в соседнюю ячейку. Эти трудности уже заметны при сравнении с программирова­ нием для обычной электронной вычислительной машины (см. § 6). Их можно, однако, значительно смягчить, если учесть следующее соображение, которое, впрочем, касается не только тыорингова программирования, но и программи­ рования для реальных вычислительных машин: при пост­ роении новых программ (в частности, новых тыоринговых программ) удобно использовать в качестве отдельных ку­ сков ранее построенные программы. Это возможно в тех случаях, когда рассматриваемый алгоритм является в оп­ ределенном смысле сочетанием алгоритмов, ранее уже изу­ ченных и построенных.

10.1. Стандартные программы и формальные операции над программами. Как же осуществлять на деле сформу­ лированное выше общее соображение?

88

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

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

1. Тождественный алгоритм (обозначение — Е) перера­ батывает каждое слово Р в некотором заданном алфавите

вэто же самое слово Р : Е (Р) = Р.

2.Копирующие алгоритмы. Удваивающий алгоритм (обозначение Konl) снимает одну копию заданного слова Р.

Пусть || — специальный символ — разделительный знак, не принадлежащий тому алфавиту, в котором рассматрива­ ются слова Р. Тогда Konl (Р) = Р || Р. Аналогично, для ут­

которые копируют не все слово, но лишь некоторую его часть, однозначно указываемую с помощью специальных разделительных символов. Например, алгоритм, копиру­ ющий часть слова, расположенную после единственного вхождения разделительного символа *, перерабатывает слово Р « R в слово Р • R \\ R. Там, где из контекста ясно, какой именно копирующий алгоритм имеется в виду, будем обозначать его просто Коп.

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

89