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

вающего продолжение процесса; в нашем случае таким бу­ дет дополнительно введенное состояние 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