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

этом пути, состоит в том, что, воспроизведя работу програм­ мы 21 применительно к куску Р, машина Тьюринга может задавать запись куска Н, ибо ячейки, занятые этой запи­ сью, могут понадобиться для работы программы 31. Точно так же имитации работы программы 23 на куске Н может мешать кусок Р или те записи, которые возникли бы в ре­ зультате его обработки. Конечно, положение сильно упро­ стилось бы, если бы вместо одной одномерной ленты машины Тьюринга в качестве внешней памяти имелись бы две Ленты, причем правила функционирования машины допускали бы переписывание с одной ленты на другую. В таком случае можно было бы вычисление ЩР) осуществлять на одной ленте, вычисление ЩН) на другой, и потом можно было бы свести результаты вместе. Это замечание показывает, что для машин другого типа (с более «гибкой» и удобной памятью) алгоритм, программирующий параллельную композицию, был бы совсем тривиален. Для машин Тьюринга и для тыоринговых программ дело обстоит несколько хуже, но в ко­ нечном счете нужный программирующий алгоритм (и даже в разных вариантах) удается описать. Откладывая это опи­ сание до § 12, мы пока приведем в данном параграфе даль­ нейшие примеры и теоремы, опирающиеся на теорему о программировании параллельной композиции.

10.4. Разветвление алгоритмов. Уже в предыдущих па­ раграфах мы не раз встречались с предписаниями следую­ щего типа: «применить к исходным данным алгоритм 21 или алгоритм 33 в зависимости от того, обладают ли эти данные таким-то свойством (см., например, команды услов­ ного перехода для электронных вычислительных машин). При этом предполагалось, что мы располагаем соответстствующим распознающим алгоритмом Ф, т. е. алгоритмом, который применим к данным, о которых идет речь, и дает ответ «да» (они обладают этим свойством) или «нет» (если они не обладают этим свойством). Когда распознающий алго­ ритм Ф задан в виде тыоринговой программы, то обычно считают, что он применяется к исходному слову Р и пере­ рабатывает его в 1, если ответ утвердительный, и в 0 — если ответ отрицательный.

Такое предписание можно рассматривать как некоторый новый алгоритм, являющийся своеобразным сочетанием трех алгоритмов Ф, '21, 23, первый из которых является распознающим алгоритмом. Условимся называть его раз­ ветвлением 21 и S3 по признаку Ф и записывать так: «если Ф то 21 иначе 23».

94

мы, программирующие последовательную и параллельную композиции. Кроме того, будут использованы уже извест­ ные нам стандартные программы: Е (тождественный алго­ ритм), Konl (удваивающий алгоритм), а также еще одна стандартная программа, так называемая ветвящая про­ грамма (обозначаемая далее Ветв) Ветв имеет 3 внутренних состояния р, р0, Pi и внешние символы 0, 1, || . Среди команд для нас важны лишь следующие четыре команды:

{р-^Пр,:, Н Л; Ор^Пр0; ||р„-»-Л.

95

состоянием р из Ветв, а состояния р} ир0 из Ветв заменяются соответственно на начальные состояния программ 31 и 23. В качестве начального состояния программы & объявляется начальное состояние ty программы Ф. Проследим (рис. 27) теперь, как будет протекать работа в соответствии с пост­ роенной программой (£, исходя из стандартного изображения

возможных символов: 0 или 1.

Начиная с этого момента включится в работу подпро­ грамма Ветв, которая после двух тактов приведет к конфи­ гурации IV,- если а = 1 , или к конфигурации V, если о = = 0. Этим обеспечивается нужное разветвление: далее

96

Рис. 27.

начальным состоянием всей полученной таким образом программы; саму программу обозначим ©. Тогда в приме­ нении к слову Р работа программы SD будет протекать сле­ дующим образом: (I) проверяется условие Ф применительно к слову Р; (II) если оно выполнено, то Р перерабатывается по программе 31 в слово ЩР). Однако вместо того, чтобы на этом закончить работу, как это было в случае программы®, программа £> предписывает на этот раз: (III) проверить условие Ф применительно к слову Ч1(Р) (ибо в 91 заключи­ тельное состояние заменено начальным состоянием ({). Если условие выполнено, то будет вычислено ЩЩР)), потом условие Ф будет проверяться применительно к этому слову и т. д. Мы обнаружили здесь часто встречаемую ситуацию, когда исходя из распознающего алгоритма Ф и произволь­ ного алгоритма 91 предписывается: для любого слова Р, если выполнено условие Ф, вычислить Ш(Р); если для него выполнено условие Ф, вычислить ЩЩР)) и так далее до