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

Эти команды не изменяют записи на ленте, а лишь управ­ ляют перемещением головки. В соответствии с командами группы I , начиная с конфигурации рис. 42, а, головка приступает к перемещению вправо, сохраняя состояние я; дойдя до символа р, «отражается» и, переходя в состоя­ ние я ' , начинает перемещение влево. В соответствии с ко-

Сплошь палочки

головка совершает замедленное движение вправо, «разгляды­ вая» символ / и каждую палочку в течение трех тактов.

Предположим теперь, что головки двух экземпляров машины 9Яо запущены одновременно на одной ленте, содер­ жащей так же, как и выше, запись слова I \ \... | ] р. В кон­ фигурации рис. 42, в указаны начальные положения головок и соответствующие внутренние состояния. Тогда согласно командам групп I — I I каждая из головок начнет переме­ щаться вправо. Нетрудно проверить, что если длина п слова / | | р является четным числом, то за 3 (/г/2—1) тактов «быстрая» головка (запущенная в состоянии я) успеет добе­

За это же время «медленная» головка (запущенная в состоя­ нии р) успеет дойти в состоянии р" до ячейки с (п/2)-й бук­ вой. Итак, на такте 3(д/2 — 1) получится конфигурация рис. 42, г, т. е. головки «столкнутся» как раз в середине

162

слова. На следующем такте головки «перепрыгнут» друг через друга и появится конфигурация рис. 42, д\ после этого медленная головка продолжает путь вправо, а быстрая — влево.

Заметим, однако, что не всегда можно рассчитывать на столь благополучное сосуществование двух или более тьюрииговых машин. В самом деле, могло случиться, что обе головки «стремятся» попасть в одну и ту же ячейку. В таком случае нужны дополнительные команды, не предусмотрен­ ные первоначальными тыоринговыми машинами. Например, дополнительная команда может предписывать, что если символ х обозревается одновременно двумя головками, в состояниях qu q2, соответственно, то в ячейку записывает­ ся символ, указанный исходной командой с левой частью

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

команду, которая устраняет эту опасность. С помощью команд такого типа можно уточнить для любого v = 2, 3, ...

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

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

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

Нейманов элемент — это устройство, которое на каждом такте t — 1, 2, 3, .... пребывает в одном из конечного числа состояний гъ г2, rv , образующих его алфавит R. Эле­ мент имеет два входных канала — левый и правый, по каждому из которых на такте t также поступает по одному

бужденным (или возбуждающим). Это означает, что эле­ мент, пребывающий в состоянии покоя, может быть выведен из него только при условии, что хотя бы по одному из его каналов поступает возбуждающее состояние. Впредь пред­ полагается, что среди состояний множества R имеется одно специально выделенное состояние покоя 15b. Итак:

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

164

но на рис. 44, а. Фиксируя в момент t каким-то образом состояния элементов, мы тем самым задаем некоторую

правому каналам соответственно; это позволяет ему выра­ ботать свое состояние a (t + 1) в следующий момент, согласно его программе. Поскольку это справедливо для всех элементов ленты, то за один такт в результате одно-

CL(t*t)=rm

ОС" ОС ос+

Рис. 44.

временного действия всех элементов возникает непосред­ ственно следующая конфигурация K(t + 1). Точно так же далее вырабатываются конфигурации K(t + 2), K(t + 3), ...

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

В дальнейшем мы будем рассматривать лишь конечные неймановы конфигурации, т. е. такие конфигурации, в ко­ торых все элементы за исключением конечного (но не фикси­

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

165

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

в виду связи между элементами неймановой ленты, явно указанные на рис. 44, а, мы для простоты будем пользо­ ваться в дальнейшем более удобным изображением автомата Неймана в виде обычной, как в случае машины Тьюринга, ленты (см. рис. 44. б).

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

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

го автомата, когда начальная конфигурация имеет активную зону длины V, в которой записаны сплошь нули. На рис. 47 показаны

166