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

раз н содержат все активные команды из 59?п; пассивные команды здесь опущены, так же, как п в программе рис. 45.

Легко понять, что процедура, проиллюстрированная только что на конкретном примере, всегда приводит к цели, т. е. перерабатывает любую заданную тыорингову про­ грамму 59? в «моделирующую» ее нейманову программу 50?. Возвращаясь к неймановой программе 50?0, заметим, что, исходя из начальной конфигурации рис. 48, а или рис. 48, б, она будет моделировать соответственно тьюринговы про­ цессы, происходящие в машине 59?0, при начальных конфи­ гурациях рис. 42, а, б. Это значит, что, начиная с рис. 48, а, в нижнем этаже неймановой ленты будет происходить «быстрое» перемещение символа л вправо, а, начиная с рис. 48, б, — «медленное» перемещение символа р вправо. Однако построенная указанным способом программа 50? (и, в частности, наша программа 50?о) однозначно определяет поведение нейманова автомата и для таких конфигураций

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

левая часть — тройка р д д или тройка A p„ , то в первых двух ячейках (активной зоны!) никаких изменений не произойдет. Зато на следующем такте в третьей ячейке появится сос­ тояние ^, потом такое же состояние появится в четвертой ячейке и т. д. Наконец, на (п — 1)ям такте возникнет кон­ фигурация рис. 48, д, которая более уже не будет изме­ няться.

170

Рассмотрим еще программу Щ с 18 активными коман­ дами, которая получается из Ш?0 путем включения допол­ нительных активных команд с номерами 15, 16, 17, 18 (см. рис. 49). Убедимся, что для нее справедливо следующее утверждение, которым мы воспользуемся в § 22.

Команды 15, 16 за один такт перерабатывают конфигу­ рацию рис. 48, е в конфигурацию рис. 48, г. Можно сказать, что на этом такте происходит размножение: вместо одной машины Тьюринга, обозревающей первую ячейку, возни­ кают две машины Тьюринга, обозревающие первые две ячейки. На следующем такте благодаря командам 17, 18 вырабатывается конфигурация рис. 48, з. Команды 17, 18 как бы разрешают двум возникшим машинам Тьюринга «нормально» функционировать и снимают «скованность», обнаруженную несколько выше при попытке применить программу 50?о к конфигурации рис. 48, г. Далее будет уже в точности моделироваться совместная работа двух экземп­

восходящее п. Это обстоятельство существенно использо­ вано в следующем параграфе.

§ 22. ЗАДАЧА О СТРЕЛКАХ

Сформулируем одну задачу, опубликованную извест­ ным американским специалистом по теории автоматов Э. Ф. Муром, и обсудим некоторые возможные ее решения*'. Это поможет лучше понять определенные трудности, кото­ рые возникают при организации процесса переработки ин­ формации на автомате Неймана (и вообще процесс вычис­ ления при распараллеливании). Кроме того, решение зада­ чи будет использовано в § 23.

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

1. Каждый стрелок может общаться непосредственно только со своими ближайшими соседями слева и справа. Естественно, левофланговый (правофланговый) может об­ щаться только с правым соседом (с левым соседом).

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

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

В некоторый момент левофланговый (или правофланго­ вый) получает пакет с приказом «пли!», который адресован всем стрелкам и должен быть выполнен ими одновременно. Возникают вопросы:

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

б) каково минимальное время (наименьшее число се­ кунд), за которое выполнение приказа может быть обес­ печено?

Здесь важно подчеркнуть, что число стрелков (длина шеренги) никому из стрелков неизвестно и вообще это число (обозначим его п) может быть произвольным. Кроме того, в момент вручения пакета левофланговому (право-

*> См. «Задачи о синхронизации цепи стрелкбв». Кибернетика. Сборник № 1 (новая серия). Э. Ф. Мур ссылается на Дж . Майхила как на автора задачи.

172

фланговому) об этом никому из стрелков кроме получателя еще не известно.

Рассмотрим следующую возможную инструкцию стрел­ кам, которая, на первый взгляд, представляется весьма естественной. Сначала опишем ту часть инструкции, кото­ рая рассчитана на случай, если пакет будет вручен лево­ фланговому. Она состоит из указаний. Первые два указа­ ния обеспечивают выполнение обычной команды: «слева

сосед сообщил тебе номер v, запомни свой номер v + 1 • и

вследующую секунду сообщи его правому соседу.

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

Ук а з а н и е 3. Если ты правофланговый и левый сосед сообщил тебе номер п — 1, то в следующую секунду отве­

правый сосед доложил тебе «готов!», то со следующей се­ кунды приступай к. обратному счету v, v — 1, при этом, если v > 1, т. е. если ты не левофланговый, то в следующую же секунду доложи левому соседу «готов1».

У к а з а н и е 5. Досчитав до нуля, стреляй1 Аналогичные указания даются, когда приказ получен

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

ше этого времени.

22.2. Стрелки и автоматы. Уточним теперь вопрос а), потребовав, чтобы инструкция для стрелков была фор­ мализована в виде неймановой программы. Иначе говоря,

173

нас интересует, может ли некоторый фиксированный ней­ манов элемент § выступать в роли стрелка из нашей задачи. Соответственно, к моменту получения приказа шеренга длиной п мыслится в виде подходящей неймановой конфи­ гурации с активной зоной длиной п. Разумеется, в ее ак­ тивной зоне все элементы кроме крайнего левого или край­ него правого должны иметь одно и то же состояние. Это требование отражает тот факт, что ни один стрелок, за ис­ ключением левофлангового или правофлангового, не рас­ полагает никаким преимуществом по сравнению с другим. Что же касается шеренги в момент выстрела, то она должна изображаться посредством активной зоны длиной п, в ко­ торой все элементы пребывают в одном и том же состоянии. Более того, это общее для них состояние (состояние выстре­ ла) в предыдущих конфигурациях ни разу не встречается (не допускается беспорядочная преждевременная стрельба!).

При ближайшем рассмотрении нашей инструкции ока­ зывается, однако, что она не формализуется в виде неймано­ вой программы. Дело в том, что по смыслу задачи п может быть любым натуральным числом. Но поскольку стрелку приходится запоминать свой номер, то тем самым предпо­ лагается, что он способен воспринять в одну секунду (за один такт) любое число из натурального ряда чисел. Иначе говоря, предполагается, что различных состояний, в ко­ торых может пребывать стрелок, — бесконечное множество; нейманов же элемент может пребывать лишь в конечном множестве состояний. Кстати, и реальный стрелок не спо­ собен воспринимать в одну секунду (или в любую другую заранее фиксированную единицу времени) слишком боль­ шие числа. Поэтому требование о том, чтобы шеренга стрел­ ков (при любом п) вела себя как нейманов автомат, доста­ точно естественно. Переходим к точной формулировке зада­ чи для автоматов Неймана. Нам удобно будет считать, что состояния интересующих нас неймановых элементов яв­ ляются «двухэтажными» буквами, подобно тому, как это было при моделировании машины Тьюринга и в других примерах предыдущего параграфа. Итак, будем считать,

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

174

Задача ставится теперь следующим образом. Нужно построить нейманову программу так, чтобы при любом /г каждая начальная конфигурация рис. 50, а и б преобразо­ вывалась в конфигурацию рис. 50, в; при этом требуется еще,.чтобы ни разу до появления конфигурации рис. 50, в нигде не возникал нижний символ *. Заметим, что рис. 50, а и б отличаются лишь тем, что первая и последняя ячейки

q на левом краю активной зоны — это левофланговый «при

175

22.3. Решение задачи*). Чтобы разгрузить решение от несущественных деталей, будем предполагать, что среди верхних символов имеются специальные символы /, р (со­ держательно, левофланговый и правофланговый) и что в ка­ честве начальных конфигураций вместо 50, а или б взяты' конфигурации рис. 50, г и д. Такое предположение оправ­ дано тем, что переход от рис. 50, а к г можно осуществить куском неймановой программы, моделирующей обычную машину Тьюринга, которая работает так: головка в сосстоянии q о отправляется вправо, находит крайнюю правую палочку, заменяет ее символом р, возвращается влево, отыскивает крайнюю левую палочку, заменяет ее симво­ лом I и переходит в состояние п. Для дальнейшего важно отметить, что на описанную переработку конфигурации рис. 50, а в конфигурацию рис. 50, г затрачивается 2 п так­ тов. Аналогичное замечание справедливо и относительно переработки конфигурации рис. 50, д.

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

На рис. 51 изображена программа 5Я, насчитывающая 44 команды, из которых первые 18 — это активные команды программы Щ, а последующие 18 — активные команды программы $ip. Напомним, что программы 5Лг и Шр были рас­ смотрены в конце §21. Наша ближайшая цель — убедиться

всправедливости следующего факта.

Ут в е р ж д е н и е Б, При любом п, являющемся сте­ пенью двойки, программа fft перерабывает любую из конфи­ гураций рис. 50, г, д в конфигурацию рис. 50, в, затрачивая на это не более чем Зп тактов.

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

*> Сначала пусть читатель сам поразмыслит над задачей. В ука­ занной на стр. 172 статье Э. Ф. Мур пишет: «Я настоятельно прошу знающих решение этой задачи избегать разглашения его тем людям, которые сами ищут решение, чтобы не испортить удовольствия от решения этой интригующей проблемы».

176

Для доказательства утверждения Б проследим за тем, как будет перерабатываться, например, конфигурация рис. 50, г в соответствии с программой 31. На этом рисунке взято п = 2s — 32. Сначала будут применяться команды

ht Ссм.рис. <+9)

Рбое *I

ЛЖ лю­ боелю­

появится конфигурация рис. 48, ж (см. утверждение А в кон­ це § 21). На следующем такте с помощью команд 37, 38 программы 31, будет выработана конфигурация рис. 50, е.

171

Итак, за 3 (л/2— 1) + 2<3/г/2 тактов происходит разбиение активной зоны длиной п на две подзоны длиной /?/2 каждая; правая подзона в точности такого же вида, как исходная зона на рис. 50, г, но вдвое короче; левая же — это умень­ шенная вдвое зона рис. 50, д. Описанную часть процесса будем называть левой дихотомией, ..отражая в этом назва­ нии то обстоятельство, что к разбиению зоны на две под­

аналогично проверяется, что за такое же самое чнсло'тактов происходит правая дихотомия, т. е. переработка конфигура­ ции рис. 50, д с обозревающим состоянием ~ на правом краю

это разбиение длинной шеренги стрелков на две более ко­ роткие шеренги, каждая со своим левофланговым и право­ фланговым.

Теперь мы уже можем завершить доказательство утверж­ дения Б. Пусть п = 2s . Тогда интересующий нас процесс распадается на s циклов. На первом цикле, который длится не более З/г/2 тактов,- происходит правая дихотомия. На

чем З/г/4 тактов. В результате (см. рис. 50, ж) появляется уже четыре зоны длиной /г/4 каждая, в которых одновремен­ но будут происходить дихотомии на следующем цикле с за­ тратой не более чем З/г/8 тактов и т. д. После (s — l)-ro цикла появится конфигурация такого вида, как на рис. 50, з. Тогда, наконец, применение команд 41—44 программы 9i

Утверждение Б доказано.

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

.178

приспособить процедуру дихотомии к случаю, когда зона имеет нечетную длину. Этого можно достичь, например, так: элемент, находящийся в середине зоны, попадает в со­ стояние, «равносильное» в естественном смысле паре состоя-

„ pi

нии ~ , и получает возможность распространять свое влия­ ние на обе подзоны в качестве общего для них погранич­ ного элемента. Реализация этой идеи потребует увеличения числа состояний по сравнению с программой 31, но оценка для времени остается прежней: число тактов не превосхо­

дит 3/1*).

§23. СРАВНЕНИЕ НЕЙМАНОВЫХ

ИТЬЮРИНГОВЫХ ВЫЧИСЛЕНИЙ

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

23.1. Кодирование. Как и прежде при изучении машин Тьюринга и по тем же мотивам, мы будем рассматривать автоматы Неймана как инструмент для вычисления функции. Не ограничивая общности рассмотрений, можно сосредо­ точить внимание на случае, когда речь идет о словарных функциях, аргументы и значения которых являются слова­ ми в алфавите (0, 1). Определение вычислимости по Ней­ ману формулируется, как это и следовало ожидать, так:

тывает конфигурацию, изображающую или, как говорят еще, кодирующую слово Р, в конфигурацию, кодирующую

Р(п) само это слово, точнее, конфигурацию ... ф ф Р (1) Р(2)...

*) Можно показать, что ни при каком решении задачи о стрел­ ках время от получения приказа левофланговым до выстрела не мо­ жет быть меньше 2/г — 2. Впервые решение с минимальным возмож­ ным временем получил японский математик Э. Гото; однако в реше­ нии Гото каждый стрелок — нейманов элемент — имел много тысяч состояний. Советский математик В. И. Левенштейн нашел решение с минимальным временем 2п — 2 и с 9 состояниями.

179-