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

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

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

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

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

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

л о

ние покоя д , состояния ^ J — коды первой буквы (нуля или единицы) в исходном слове, состояния °\, \ — коды первой

буквы в результирующем слове, состояния д , д — коды нуля и единицы во всех других позициях исходного слова или результирующего слова. Например, начальная конфи­ гурация рис. 52, в и заключительная конфигурация рис. 52, г

конфигурации является как бы сигналом готовности авто­

для которых мы сохраним прежние обозначения. Например,

(^) — сигнализирующая времени указывает число так­ тов, затрачиваемых автоматом 3? на переработку начальной конфигурации, изображающей слово Р, в соответствующую заключительную конфигурацию.

Сделаем еще одно важное для дальнейшего замечание, касающееся оценки сигнализирующей функции (Р).

Допустим, что для определения значения R функции / (Р)

J81 -

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

•отличным от д0, д1, то согласно свойству 2л кодирования

меньшее число тактов автомат просто не успеет полностью прочесть исходное слово. Иначе говоря, принятый нами способ кодирования начальной конфигурации не дает явных преимуществ автомату Неймана по сравнению с машиной Тьюринга, обозревающей первую букву слова. Однако авто­ мат Неймана может проявлять свои преимущества уже в про­ цессе работы, действуя как неограниченно разрастающаяся система машин Тьюринга с общей памятью. Резюмируя сказанное, подчеркнем, что в нетривиальных ситуациях имеет место неравенство ^ ( P ) ^ | P | , которое и будет ис­ пользовано нами в подходящий момент.

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

В § 21 уже было показано, как строится для всякой машины Тьюринга 93? моделирующий ее автомат Неймана 93?. Допустим, что 93? вычисляет функцию /(Р). Тогда для произвольного слова Р из области определения функции f, если 9)? преобразует конфигурацию рис. 52, а, в конфигу­ рацию рис. 52, б за (Р) тактов, то 93? преобразует конфи­ гурацию рис. 52, в в конфигурацию рис. 52, г за столько же

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

182.

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

Отрицательный ответ, подсказываемый основной гипо­ тезой теории алгоритмов и, следовательно, не являющийся для нас неожиданным, действительно может быть доказан.

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

где Cj)7o — константа, не зависящая от Р.

Для сравнения вспомним (см. § 19), что если какаянибудь машина Тьюринга ffi распознает симметрию, то обя­ зательно

где Ccffi — константа, не зависящая от п. Итак, мы распола­ гаем конкретным автоматом Неймана 320, таким, что для всякой машины Тьюринга, способной делать то же самое, что и 5к0 (а именно — распознавать симметрию), справедливо неравенство

Естественно спросить, можно ли (а если да, то для каких' функций) при вычислении получить еще более значитель-

183

ную экономию времени за счет применения неймановых автоматов. Например, существует ли такая функция / и та­ кой вычисляющий ее нейманов автомат 3{, чтобы для любой тьюринговой машины 9ft, вычисляющей /, выполнялось неравенство

где Е<£1 — константа, не зависящая от п?

Следующая теорема выясняет реальное положение дел. Т е о р е м а 4. Каковы бы ни были функции / и вычис­ ляющий ее автомат Неймана 31, найдется такая машина Тьюринга ffl, вычисляющая f, для которой справедливо нера­

венство

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

Доказательство теоремы 3 излагается в следующем пунк­ те этого параграфа. Что же касается теорем 2 и 4, то они являются прямыми следствиями одного общего факта, кото­ рому посвящен п. 23.4 этого параграфа. В нем описывается алгоритм, который по любой неймановой программе 31 строит тьюрингову программу 3)?, в определенном смысле моделирующую нейманову программу 31. Если 31 вычис­ ляет некоторую функцию f, то и Ж вычисляет ту же функ­ цию. Однако (и в этом проявляется существенное отличие от рассмотренного ранее моделирования тьюринговой ма­ шины посредством нейманова автомата) один такт работы автомата 31 имитируется машиной 5Ш в течение большего числа тактов. Более того, это число не остается неизменным; оно, вообще говоря, возрастает вместе с порядковым номе­ ром моделируемого такта. Тем не менее, оказывается, что

18Р.

Взаключение этого пункта заметим, что алгоритмы,

184

теризовать, пользуясь терминологией § 10, как програм­ мирующие алгоритмы для нейманова программирования и тьюрингова программирования соответственно.

23.3. Распознавание симметрии на автомате Неймана. Можно сразу, так сказать «в лоб», построить нейманову про­ грамму автомата, существование которого утверждается теоремой 3. Однако мы здесь предпочитаем идти окольным, но, как нам кажется, более поучительным путем, опираясь на разбор и решение задачи о стрелках. Нам нужна про­ грамма, в соответствии с которой начальная конфигурация

рис. 52, д или 52, е, в зависимости от того, симметрично слово Р = Р (1)... Р (п) или нет; при этом требуется еще, чтобы эта переработка осуществлялась с линейной оценкой затрачиваемого времени (т. е. за время, не превосходящее const-л). Эту задачу разобьем на две.

Первая задача. Пусть начальная конфигурация взята так, как показано на рис. 53, а, где для простоты п счи­ тается четным числом: n = 2v. Здесь Л П — два специаль­ ных нижних символа в составе двухэтажных букв; их содержательный смысл заключается в различении букв ле­ вой половины слова Р от букв правой половины его. Тре­ буется построить программу %, перерабатывающую за

проста. В течение v тактов на каждом такте происходит од-

185'

повременное сползание на одну позицию правой конфигу­ рации влево и левой конфигурации вправо и сравнение пары подошедших к точке стыка полуконфпгурапий. Рис. 53,о изображает сравнение «Р (v) = Р (v + 1)?», рис. 53, б — сравнение «Р (v — 1) = Р (v + 2)?» и т. д. Если слово Р симметрично, то на (v — 1)-м такте появится конфигурация рис. 53, д, которая на следующем такте приведет к конфи-

гурации рис. 52, д. Допустим, что слово Р несимметрично и

на следующем такте (рис. 53, г) это зафиксируется появле­ нием нижнего символа Л' у точки стыка. Этот символ сохра­ няется при дальнейшем сползании. На предпоследнем так­ те появляется конфигурация рис. 53, е, которая еще через один такт переходит в конфигурацию рис. 52, е. Теперь ясно, что для доказательства теоремы 3 достаточно решить следующую задачу.

J86.

Вторая задача. Построить нейманову программу Э?п, которая обеспечивает переработку конфигурации рис. 52, а в конфигурацию рис. 53, а с соблюдением следующих условий:

Л(покоя), л, л, п, п\ в) по ходу этой переработки до появления конфигура­

дет переход от рис. 52, а и 53, а согласно SRn, а затем далее от 53, а к 52, д или к 52, в согласно fSls- При этом общее затра­ чиваемое время не превышает дозволенной оценки.

Роль программы 9?п заключается, очевидно, в том, чтобы довести одновременно до каждой буквы слова Р информа­ цию-о том, какой половине слова она принадлежит: левой или правой. Аналогия с задачей о стрелках достаточно проз­ рачна. Специфика новой ситуации сводится лишь к следую­ щим двум пунктам: 1) теперь мы имеем дело со стрелками двух категорий (нули и единицы), вместо прежних стрелков одной категории (сплошь палочки); 2) вместо общего для всех приказа «пли» (нижний символ*) теперь стрелкам из левой полушеренги, нужно выполнять приказ «пли на­ лево!» (нижний символ Л), а стрелкам из правой полушерен­ ги— приказ «пли. направо!» (нижний символ П). Однако обе эти особенности несущественны; и рассмотренное нами решение (§ 22) легко может быть приспособлено и к'новым

5 п тактов. Модификации, которые нужно ввести, потребуют лишь увеличения числа внутренних состояний нейманова элемента (стрелка). Например, вместо двух верхних сим­ волов I, р потребуются четыре: /°, I 1 , р°, р 1 — для запоми­ нания того, какие буквы (0 или 1) стояли в тех местах, где заканчивались очередные циклы дихотомии. В заключи­ тельном такте это позволяет восстанавливать в верхнем этаже первоначальное слово Р; кроме того, увеличение числа состояний необходимо для того, чтобы после первой дихотомии и впредь до выстрела в левой и правой полузовах длиной п/2 употреблялись различные состояния.

167

Это позволяет на заключительном такте установить всюду в левой полузоне нижний символ Л, а всюду в правой полузоне — другой нижний символ П. Опуская эти детали, можем считать теорему 3 доказанной.

состояния покоя ф. Тогда за один такт эта конфигурация перерабатывается в конфигурацию рис. 55, б, активная зона которой, очевидно, во всяком случае не длинее s -f- 2

188

изображены конфигурации «трехэтажной» машины Тью­ ринга 50?, которая на своем втором этаже стремится ими­

машины 2)?совершает колебания, изображенные посредством зигзагообразной линии под лентой на рис. 55, в. При пер­ вом пробеге — слева направо — машина записывает на верхнем этаже каждой посещаемой ячейки содержимое вто­ рого этажа соседней с нею левой ячейки. В результате воз­ никает конфигурация рис. 55, г. При возвращении налево в нижний этаж каждой ячейки заносится содержимое вто­ рого этажа соседней справа ячейки. Итак, после одного полного колебания в каждой ячейке зоны длины s + 2 уже накоплена информация о состоянии соответствующей ней­ мановой ячейки и о состояниях ее соседей слева и справа. Начиная свой очередной пробег слева направо, машина 50? осуществляет в каждой ячейке замену тройки неймановых состояний тем состоянием, которое предписывается суще­ ствующей командой программы 31; это состояние заносится на второй этаж, а другие два этажа очищаются. К концу третьего пробега запись на тьюринговой ленте уже имеет вид, указанный на рис. 55, е. Наконец, головка возвра­ щается влево, не производя никаких записей и, достигнув ячейки с записью и (0), переходит в состояние (обозначен­ ное на рис. 55, в через г0). Теперь она уже готова к сле­ дующему циклу, в котором будет моделироваться следующий нейманов такт. Ясно, что можно построить машину Тьюрин­ га 50?, выполняющую описанный нами алгоритм (подтверж­ дение основной гипотезы теории алгоритмов).

При составлении программы 50? на самом деле нужно учитывать еще некоторые другие, впрочем, довольно оче­ видные детали. Например, машине 50? необходимо как-то помечать на каждом цикле ячейку, из которой она начи­ нает свои колебания, дабы при обратном движении она могла бы обнаружить ее и продолжать свой путь ровно на

189