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

(1) может послужить для установления нижней оценки сигнализи­ рующей 1$)\{Р)- Именно таким методом мы намерены в дальнейшем получить нижние оценки сложности вычислений в ряде интересую­ щих нас случаев.

18.2. Эксперимент с разрезанной лентой. Значение понятия сле­ да состоит в том, что след отражает способ, которым машина посред­ ством своих внутренних состояний передает информацию с одной стороны границы на другую. Следующий мысленный эксперимент иллюстрирует наглядно это обстоятельство. Допустим, что нам из­ вестен след в точке / для процесса 9Л [Р]. Допустим далее, что правая полулента, начинающаяся в точке /, изъята (вместе с куском слова, расположенным на ней). Эксперимент заключается в следующем. Запускаем машину на уцелевшей левой полуленте так, что головка обозревает символ Р (1) в начальном состоянии. Тогда машина бу­

ность машине продолжать работу на левой полулепте до тех пор,

q (s) она больше уже не покинет левую полуленту и наконец остано­ вится на ней в заключительном состоянии. Тем самым эксперимент

мент она покинет левую полуленту в состоянии q (s); на этом экспери­ мент заканчивается. Совершенно очевидно, что в условиях описан­ ного нами эксперимента поведение машины на левой полуленте бу­

18.3. Замещения. Допустим, что в процессе 5ЭД [И], который вы­ полняет машина $Ш, запущенная с исходным словом Н в некоторой точке i, возникает в точности такой же след, как прежде, при исход­ ном слове Р в точке / (см. рис. 40, а и б)\

след(Р, ]) = след(#, i).

Пусть Р[ обозначает начальный кусок длины / с л о в а Р, а Р" — его конечный кусок длины п — /; аналогичный смысл имеют обозна­ чения Н'а и Н'Р для слова # = Н(\)Н{2) ... Н(т). Рассмотрим на­ чальную конфигурацию со словом Р[Н'" (рис. 40, в) и соответствую­ щий процесс 50} \P\Hf\. Анализ эксперимента, описанного выше, по­ казывает, что в этой ситуации произойдет в точности следующее;

152

I

этим свойством. Если же след (Я, /') имеет нечетную длину, то оста­

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

Л е м м а о з а м е щ е н и я х Пусть слова Р = PJP" и И =t •= Н'аН"' эквивалентны относительно распознающей машины 93}, причем следы, возникающие на границе между Р[ и Я1 ], а также между #,5 и Н"', равны. Тогда четыре слова!

метричные слова одинаковой длины я, причем / < я/2. Тогда, если

симметричным. Но если бы в симметричном слове Н = н1н" мы заменили начальный кусок //(, длиной меньше половины всего слова Н куском той же длины, но отличным от Н\'в, то полученное слово наверняка было бы несимметричным.

§19. НИЖНИЕ ОЦЕНКИ СЛОЖНОСТИ

19.1.Сложность распознавания симметрии. Теперь мы в состоя­ нии доказать теорему Барздния (см. конец п. 17.4). Несправедли­ вость вытекает непосредственно из леммы 1, которая будет доказана ниже. Во избежание излишней громоздкости совершенно месушеет-

153

венном для наших оценок, мы будем считать далее, что употребляе­ мые натуральные числа л кратны четырем, т. е, что /г/2, л/4 — на­ туральные числа (в общем случае приходится заниматься с нижай­ шими по избытку или по недостатку числами, но все оценки сохра­

распознающая симметрию. Тогда можно подобрать константу Оэд (зависящую только от машины 9Л) так, что будет иметь место следую­ щее.

Для всех достаточно больших я (т. е. для всех л, начиная

Из этой леммы интересующая нас оценка получается тривиаль­ ным образом. Для всякого слова Р, удовлетворяющего условию (1), имеет место в соответствии с неравенством 1 из 18.1 также н такое неравенство:

Итак, гипотеза справедлива, если в качестве константы Сэд взято число Diyjj/4.

Мы докажем, что утверждение леммы 1 имеет место, если в ка­ честве Diffi взято число l/8log2 k, где k обозначает число внутренних состояний машины Ш- При таком подборе Эщ мы не только обнару­ жим, что среди симметричных слов длиной л найдется слово Р, удов­ летворяющее условию (1), но и что таких слов Р — «подавляющее большинство». Точнее, пусть Л'(л) — число симметричных слов Р длиной л, для которых условие (1) нарушено, и S(n) — число всех симметричных слов длиной л. Будет показано, что

т. е. условие (1) нарушается лишь для ничтожной доли всех слов длиной я. Для того же, чтобы показать (2), достаточно установить

15*

т. е. числу всех двоичных слов половинной длины; в самом деле, ле­ вую половину симметричного слова, имеющую длину л/2, можно задавать любым из 2" / 2 возможных способов, а правая половина уже однозначно определяется как зеркальное отображение левой.

Таким образом,

но, поскольку в левой половине симметричного слова Р уже зафик­

порядку!) способа распознавания симметрии, чем последовательное сравнение кусков слова, одинаково удаленных от середины.

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

155

ленты. Эти же обстоятельства могут быть использованы для уста­

алгоритм [Шо, приводящий к результату с оценкой времени 2nlog1 0 /i, Предлагается следующее.

У п р а ж н е и и е. Показать, что для любой машины Тьюринга 9Л, переводящей унарную запись числа п в его десятичную запись, существует константа Сэд такая, что Т%\ (п) > CgiJ / г ' ° й ю « ' Иначе говоря, с точностью до порядка (до постоянного множителя) тыорин-

на рис. 41. Показать, что машина Ш, запущенная в этой конфигура­ ции, порождает попарно различные следы в точках 1, 2, ... Далее, проверить, что сумма длин п попарно различных следов удовлет­ воряет неравенству, которое нужно установить для Тщ.

§ 20. СУЩЕСТВОВАНИЕ СКОЛЬ УГОДНО СЛОЖНЫХ ПРОБЛЕМ

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

работы. В этом параграфе нам хочется обсудить следующий

156