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

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

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

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

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

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

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

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

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

150

Рис. 40.

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

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

151

(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

Допустим, что проблема, решаемая на машине Тьюринга 3J?, состоит в вычислении значений некоторой числовой функ­ ции ф (п) при /1=1, 2, 3,... Мы уже знаем (см. п. 11.3), что такая функция может оказаться очень быстро растущей. Вспомним, например, функцию ср, принимающую для аргу­ мента п значение З 2 ' (п этажей!), хотя, конечно, и такой внушительный рост может быть превзойден. Если значения аргумента и самой функции записываются унарно, то для любой машины Ш, вычисляющей ф, Тэд (п) будет не меньше, чем ф (/г); ведь машине потребуется такое коли­ чество тактов уже только для того, чтобы записать резуль­ тат— ф (п) палочек. В этом смысле, вычисляя быстро рас­ тущие функции, мы уже столкнулись со сколь угодно слож­ ными проблемами. Это положение сохранилось бы и в том случае, когда числа записываются в какой-нибудь позицион­

добных ситуациях много времени тратится машиной на за­

не громоздок (результирующее слово короткое), а значит почти все время тратится машиной на вычисление резуль­ тата. В связи с этим ограничимся рассмотрением лишь проб­ лем, заключающихся в распознавании свойства исходных данных; в этой ситуации решение может быть дано в виде однобуквенного слова «1» (да) или «0» (нет). (Пользуясь терминологией, употребляемой в логике, можно сказать, что это есть проблема вычисления предиката.) Среди таких проблем, как мы уже знаем, имеются и алгоритмически неразрешимые (например, распознавание самоприменимо­ сти, распознавание эквивалентности слов и др.). Если же проблема распознавания алгоритмически разрешима, то

157

время, затрачиваемое на решение тех или иных индивидуаль­ ных ее задач при использовании конкретного алгоритма (например, тыорпнговой программы Ж), уходит почти це­

Тьюринга 31, которая распознает то же самое свойство, и при этом

/fSR(P)<f(P) для всех слов Р.

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

20.2. Распознавание /-самоприменимости. На самом же деле оказывается, что такой вычислимой функции не суще­

(ЩР) > f (Р) для бесчисленного множества слов Р.

Доказательство этой теоремы получается путем подходя­ щей (и поучительной!) модификации теоремы п. 15.2 об алго­ ритмической неразрешимости проблемы распознавания самопрнменимости. Пусть / (Р) — вычисляемая функция из условий теоремы. Тогда, если на ленте произвольной ма­ шины 93? записан ее собственный шифр €0?' и машина запущена в работу, то возможен один и только один из следующих трех случаев: 1) машина 3)? не остановится в течение пер-

158

вых / (93?") тактов; 2) машина 93? остановится не позже чем через [ (50?') тактов и выдаст результат 1; 3) машина 2)? остановится не позже чем через / (S3?') тактов и выдаст ре­ зультат, отличный от 1.

Условимся говорить о машине Ж, что она /-самопримени­ ма, если имеет место ситуация 3) и что она /-несамопримени­ ма в противном случае, т. е. в ситуациях 1) и 2). Естествен­ но, возникает проблема распознавания/-самоприменимости: для любого двоичного слова Р узнать, является ли оно шиф­ ром /-самопримеиимой машины (короче, является ли Р /-самоприменимым шифром). При всем внешнем сходстве с проблемой самоприменимости имеет место, однако, сле­ дующий факт; проблема распознавания /-самопримени­ мости алгоритмически разрешима. Разрешающий алгоритм 2( заключается в следующем. 1. Для данного слова Р про­

в п. 14.2. Если Р не является шифром, то тем более оно не является /-самоприменимым шифром и ответ (отрицатель­ ный) уже найден. 2. Если Р является шифром, то сначала вычисляем число / (Р). Это можно сделать эффективно, ибо по предположению функция / (Р) вычислима, т. е. суще­ ствует алгоритм (машина Тьюринга), который по каждому слову Р позволяет находить значение / (Р). 3. Далее, по шифру Р восстанавливаем схему машины и, запуская ее в начальной конфигурации с записью слова Р, следим за ее работой в течение не более чем / (Р) тактов. Это позволяет нам фактически установить, какая из ситуаций (1, 2, 3) имеет место и, следовательно, позволяет получить правиль­ ный ответ на вопрос: /-самоприменим ли шифр Р?

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

тактов ее работы. Пусть $ — какая-нибудь машина Тьюрин­

если 93?' /-самоприменима; (**) $ перерабатывает 93?' в 0, если 93?' / несамоприменима. По аналогии с доказательством из § 15 посмотрим, как будет перерабатывать машина $ свой собственный шифр

159