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

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

Можно ли еще улучшить этот результат? Точнее, воз­ можна ли тыорингова программа 50?2 такая, что Год?» по порядку меньше даже, чем Тещ,;? К этому вопросу мы еще вернемся позднее (см. п. 19.2).

Наконец, для задачи I I I можно предложить программу 50?з, в соответствии с которой происходит замена звездочки

на единицу и стирание крайней слева палочки. Очевидно, Тщ:. («) = п + I , что по порядку меньше, чем (п.), которая асимптотически равна п2. Более того, достаточно ясно, что дальнейшее существенное убыстрение процесса уже невозможно.

17.4. Распознавание симметрии. Рассмотрим еще сле­ дующий класс однотипных задач: для произвольного слова р = Р (]) р (2)... Р (п) в алфавите (0,1| следует узнать, симметрично ли оно, т. е. совпадает ли слово Р со своим зеркальным отображением Р (п) Р (п — 1)... Р (1). Как обычно, будем считать, что соответствующий распознаю­ щий алгоритм выдает 1 в случае утвердительного ответа и О — в противном случае. Легко составить тьюринговы про­ граммы, решающие эту проблему, но мы ограничимся*опи­ санием того, как протекает соответствующий вычислитель­ ный процесс. Начав работу в конфигурации рис. 39, головка запоминает символ Р (1), уходит на правый конец слова и, найдя символ Р (п), сравнивает его с Р (1). Если эти символы различны, то слово Р не симметрично, и тогда стирается первоначальная запись и на ленте записывается результат 0. В противном случае головка возвращается влево, отыс­ кивает Р (2) и начинает второй цикл, в котором сравни ваются Р (2) и Р (п — 1) и т. д. Дольше всего машина будет

148

работать, когда слово Р на самом деле симметрично. Тогда

а — 2 ячейки и обратный на п — 3 ячейки и т. д. На рис. 39

но было бы сэкономить время примерно вдвое за счет сле­ дующего усовершенствования алгоритма: машина 3? осу­ ществляет по одному сравнению после каждого хода в одну сторону. Например, после сравнения Р (/) с Р (п) при возвращении влево по пути считывается и запоминается зна­ чение Р (п — 1), которое после завершения обратного хода (влево) уже сравнивается с Р (2). При таком способе вы­ числения на машине уже будет Tg-j (п) — /г2/4. Легко понять, что возможны и дальнейшие усовершенствования. Пусть, например, при каждом перемещении в одном направлении

и т. д. Это, конечно, потребует увеличения числа внутрен­

i-ки символов. Соответственно для временной сигнализи­ рующей имеет место асимптотическое равенство Tg^ (/г) ~

~ /г2 /4/. Хотя мы таким образом и добиваемся ускорения процесса вычисления, тем не менее для всех рассмотренных нами до сих пор машин SR, распознающих симметрию, временная сигнализирующая Тс^ по порядку не меньше /г2; точнее, для них справедливо следующее утверждение.

Существует константа Сстд, зависящая от Ш, но не зави­

Возможно ли распознавание симметрии за время по порядку меньшее, чем /г2, т. е. существует ли машина Тьюринга Ж0 , распознающая симметрию, и такая что

lim 7Vj-)jo(n)lif — 0 при /г-» оо ?

149

(например, машина 5Я?0, для которой (п) < п У п или

7Yffi0(/!)<HVlOg/7).

В связи с этим вспомним, что для перевода в десятич­

меньше, чем первоначальная опенка Тсдо„ (я) ~ я ' г . На первый взгляд, однако, создается впечатление, что всякая процедура распознавания симметрии так или иначе должна основы­ ваться на циклах сравнения рассмотренного выше типа; и не видно, за счет чего можно было бы добиться более су­

в начальной конфигурации с исходным словом Р. Пронумеруем гра­ ницы между соседними ячейками так, как это указано на рис. 40, а, С каждой фиксированной границей / можно ассоциировать последо­

Пусть головка пересекает границу / ровно s раз: первый раз в состоя­ нии q (1), второй раз в состоянии q (2) и т.д. Тогда последовательность

из контекста ясно, какая имеется в виду машина или слово, будем применять упрощенные обозначения типа след (Р, / ) , след (/). Если первое прохождение головки было слева направо, то второе будет

Если процесс Ш [Р] бесконечен, то может случиться, что в некоторых границах / след тоже будет бесконечным. Однако, поскольку мы да-

150

Рис. 40.

ратон одного такта работы машины. Поэтому справедливо неравен­ ство

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

151