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

1) пусть S f-самоприменима; тогда по определению f-самоприменимости (вариант 3) она выдает результат, от­ личный от 1. Но согласно (**) это означает, что на самом деле й выдает результат 0, а следовательно, ®/-несамо- применима. Полученное противоречие заставляет нас (так же, как и в п. 15.2) отвергнуть предположение о /-самопри­ менимости машины ®;

2) пусть й /-несамоприменима; тогда по определению возможен один из вариантов (1 или 2). Вариант 2 приводит к противоречию в точности так же, как это было обнару­ жено для варианта 1. Тем самым выясняется, что имеется лишь одна возможность, а именно, что реализуется вариант 1, т. е. справедливо утверждение: если машина Й распознает

Р в стандартной конфигурации, то они будут работать со­

они также распознают /-самоприменимость, а следовательно,

можно при условиях теоремы обнаружить существование такого свойства Г двоичных слов, для которого утвержде­ ние б) теоремы справедливо в следующей более сильной форме (теорема Рабииа): б) Какова бы ни была машина £, распознающая это свойство Г, ее временная сигнализирую­ щая (й удовлетворяет неравенству t% (Р) > / (Р) для всех двоичных слов Р за исключением конечного их числа.

160

Эти команды не изменяют записи на ленте, а лишь управ­ ляют перемещением головки. В соответствии с командами группы 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

все ячейки ленты, за исключением конечного их числа, будут охарактеризованы именно «двухэтажной» буквой д. Те­ перь, если мы буквы из R будем интерпретировать как сос­ тояния некоторого нейманова элемента, то ясно, как всякая тьюрингова конфигурация К естественным образом коди­ руется некоторой неймановой конфигурацией К- Напри­ мер, на рис. 48, а, б изображены неймановы конфигурации, кодирующие тыоринговы конфигурации рис. 42, а, б.Более

167

того, по заданной тыоринговой программе 9J? можно по­ строить нейманову программу 9Й так, что если 9R переводит за один такт К и К!, то автомат Неймана с программой Ж пе­ реводит за один такт К в конфигурацию, кодирующую

К'. В этом смысле автомат Неймана 9Й моделирует машину Тьюринга ЗЙ, причем, как легко понять, роль состояния

Процедуру перехода от 9Й и 3)? поясним на примере тьюринговой программы 50?0 из 21.1. В этой программе имеет­ ся команда рп-*-Лп'. Поэтому для любой тройки вида

д^Л., где х, у — любые внешние символы машины Э3?0,

168

в программе $?0 фигурирует команда: * дд->-л>. Она в точ­ ности отражает факт смещения головки из ячейки а+ в ячей­ ку а и появления состояния я' . По тем же соображениям

автомата, моделирующего 5Ш0. Верхние 14 строк рис. 49 как