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

10.2. Последовательная композиция. Часто встречается ситуация, когда два алгоритма — в частности, две тыоринговы программы SI, 23, — приходится сочетать следу­ ющим образом. Предписывается исходя из начальных дан­ ных, т. е. из слова Р, сначала применить алгоритм 21, а за­ тем к его результату, т. е. к слову ЩР), применить алго­ ритм 23 и, следовательно, получить слово 33(^1 (Р)). Это предписание составляет новый алгоритм — последователь­ ную композицию алгоритмов "21, 23, обозначаемую 3}. Естественно спросить, можно ли (а если да, то как) постро­ ить функциональную схему для последовательной компо­ зиции, коль скоро мы располагаем функциональными схе­ мами "21, 25. Утвердительный ответ содержится в следующей почти очевидной теореме.

Т е о р е м а (о программировании последовательной композиции). Каковы бы ни были тыорйнговы программы "21 и 23, может быть эффективно построена тыорингова про­

Программирующий алгоритм, который строит (эффек­ тивно) программу е, заключается в следующем. Предва­ рительно препарированные программы *2l, 93 объединяются в одну программу, а в подпрограмме «а всюду заменяется символ «!» символом начального состояния программы 93

не в заключительном состоянии «!», а в начальном состоя­ нии гх подпрограммы 93. Благодаря этому далее продол-

91

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

дартное изображение слов, лишь бы гарантировалась со­ гласованность перехода от 31 к ЙЗ. В качестве примера по­ строим функциональную схему алгоритма, перерабатываю­ щего пару чисел а, Ь, заданных соответствующими наборами палочек в их общий наибольший делитель, записанный в десятичной системе счисления. Поскольку этот алгоритм является последовательной композицией двух ранее рас­ смотренных алгоритмов (в п. 9.5 и 9.2), его функциональная схема (рис. 25, б) может быть получена из схем рис. 14 и 18, так, как этого требует описанный программирующий алго­ ритм. Состояния схемы рис. 18 здесь переименованы в р,.,

ръ р 2 . Хотя схемы рис. 14 и 18 не были составлены нами

применительно к стандартному изображению начальных и результирующих слов, тем не менее построенная схема рис. 25, б годится, ибо схема рис. 14 заканчивает работу на крайнем правом символе слова, а схема рис. 18 начинает там же работу (т. е. обеспечена согласованность перехода от первой программы ко второй).

92

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

10.3. Параллельная композиция алгоритмов 21, 23 заклю-. чается по существу в совместном рассмотрении их работы применительно к соответствующим исходным данным; пусть это будут слова Р и Н, соответственно. Более точно эту разновидность сочетания алгоритмов можно описать сле­ дующим образом. Допустим, что || — некоторый символ, не встречающийся в алфавитах, посредством которых изо­ бражаются исходные данные и результаты алгоритмов $1, 23; тогда слова Р \\ Н и ЩР) || ЩН) могут применяться как изображения пар исходных слов и пар результирующих

писание и составляет новый алгоритм — параллельную ком­

увеличит на единицу десятичное число 389, приведет сло­ жение слагаемых 6 + 4 и выдаст результат:

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

93

этом пути, состоит в том, что, воспроизведя работу програм­ мы 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 предписывается: для любого слова Р, если выполнено условие Ф, вычислить Ш(Р); если для него выполнено условие Ф, вычислить ЩЩР)) и так далее до

алгоритмов для композиции, разветвления и повторения мы можем получить исходя из формулы (фр) тыорингову программу для алгоритма Евклида. Конечно, эта программа будет более громоздкой, чем функциональная схема рис. 14, но зато ее получение не требует никакой особой изобрета­ тельности.

Коль скоро мы намерены пользоваться входным языком, то вместо четырех частных типов программирующих алго­ ритмов удобнее говорить о едином, объединяющем их, про­ граммирующем алгоритме, который по любой формуле входного языка строит соответствующую ей тыорингову программу. Естественно, предполагается, что наряду с фор­ мулой входного языка заданы и тьюрииговы программы для «элементарных» алгоритмов, встречающихся в формуле.

§11. РЕКУРСИВНЫЕ ФУНКЦИИ

ИФУНКЦИИ, ВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ

11.1Вычисление функций и алгоритмические пробле­ мы. В этом параграфе речь идет о числовых функциях одно­ местных, т. е. от одной переменной, или, многоместных, т. е. от многих переменных; предполагается, что значениями са­ мой функции, а также ее аргументов являются натуральные числа. Числовую функцию / будем называть вычислимой по Тьюрингу, если существует машина Тьюринга, вычисля­ ющая ее. Конечно, аккуратное определение функции, вы­ числимой по Тьюрингу, должно содержать указание на то,

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