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

Для доказательства утверждения Б проследим за тем, как будет перерабатываться, например, конфигурация рис. 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-

пояснить на следующем примере. Рассмотрим функцию /, определяемую условием / (ООО) =000, / (Р) = 1, для всех двоичных слов Р, отличных от ООО; в частности, f (0000) = 1. Эта функция весьма проста и, конечно, было бы более чем странно, если бы в соответствии с принятым нами опреде­

(т. е. a (t +1) отлично от a (t)); иначе в начальной конфигу­ рации... ф0000ф... не была бы применила никакая актив­ ная команда, а следовательно, она была бы стабильной, т. е. автомат 32 не изменял бы ее; но это противоречит тому, что / (0000) = 1. Итак, имеется активная команда указан­ ного вида; но тогда конфигурация... ф000ф... не может быть стабильной, т. е. автомат начнет ее преобразовывать. Поскольку / (000) = 000, то через некоторое число тактов (обозначим его о) опять возникнет та же самая конфигура­ ция... 00000..., для которой начнется следующий цикл преобразований, и так периодически все будет повторяться через каждые о тактов. Иначе говоря, будучи запущенным

нительных разъяснений не понятно, на какой стадии этого процесса следует считать вычисление оконченным и при­ годным для считывания результата.

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

1. Рассматриваются автоматы Неймана с двухэтажным алфавитом состояний, среди которых выделяются: состоя­

л о