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

Рассмотрим еще программу Щ с 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