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

ние покоя д , состояния ^ 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'