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

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

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

Птггп

\Ь \h

Т Л Т П1

циональной схемы для сложения происходят преобразования кон­ фигураций, показанные на рис. 34.

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

140

Последняя подстановка отражает факт перемещения единственной активной ячейки (см. рис. 37).

Этим и завершается перечень ориентированных подстановок, соответствующих в исчислении п м машинной команде вида (2).

П р и м е р . Построить для машины Тьюринга 2, реализующей сложение (см. п. 9.3), соответствующее исчисление

141

н 5 —два /(-слова в исчислении я д / . Если R переводимо в S ориенти­

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

ка. Поэтому обнаружение такой тройки в дедуктивной цепочке по­

чительной конфигурацией, то (см. утверждение 3) может быть лишь Rk-i -* Rk• Если в данной цепочке все стрелки являются правыми, то лемма уже установлена. Если же существуют левые стрелки, то пусть последняя встречается перед /'-м словом. Тогда имеется тройка

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

143

§17. КАЧЕСТВО АЛГОРИТМОВ

ИВЫЧИСЛЕНИЙ

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

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

короткими алгоритмами, однако фактическое их при­ менение требует очень больших вычислений, связанных с перебором сверхастрономического числа вариантов. Иначе говоря, может оказаться, что некоторое руководство к дей­ ствию само по себе просто и коротко формулируется, но само действие, предписываемое им, очень громоздко. Так обстоит, например, дело с алгоритмом поиска выигрышной стратегии для игры (см. § 2). С другой стороны,- встречают­

ся довольно громоздкие предписания, которые сравнитель­

но быстро приводят к цели.

17.1. Сигнализирующие функции. Определим теперь

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

Пусть Р — слово на ленте тыоринговой машины 93?,

изображающее исходную информацию. Число тактов, ко­

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

также наименьший кусок ленты, содержащий исходное слово Р, а также все те ячейки, которые хотя бы один раз

посещаются головкой в ходе этого процесса. Длина этого куска ленты есть не что иное, как объем внешней памяти, используемой машиной 3)? в процессе вычисления; обозна­ чим эту длину через (Р). Поскольку исходные данные

Р можно варьировать, то тем самым мы определили для

144

данной машины 50? две функции от аргумента Р, так назы­ ваемые временную и емкостную сигнализирующие машины SDf; они измеряют соответственно расход времени и памяти при вычислениях на машине Ж.

Наряду с этими функциями удобно пользоваться и функциями натурального аргумента п, которые по данной машине SO? и по фиксированному подалфавиту А ее внеш­ него алфавита определяются так:

В дальнейшем длина слова Р всюду обозначается | Р |. Эти функции также будем называть сигнализирующими; из контекста всегда будет ясно, о каких сигнализирующих

на самом деле идет речь. Разумеется, чем меньше эти функ­ ции (чем медленнее они растут с ростом л), тем проще вы­ числения на рассматриваемой машине. Часто нет возмож­

некоторые достаточно хорошие (в том или ином смысле)

при этом воспользуемся теми оценками, которые были ука­ заны в § 9 в связи с разбором проблем I — I I I и их реше­ ния на машинах 50?ь 50?а, Ш?3. Напомним, что Ш?х применяется к словам Р в десятичном цифровом алфавите. Как уже от­

145

возникающая при замене одной из этих величин другой, стремится к со. Однако полезно заметить, что отношение этих величин стремится к 1 при л.-»-со; иначе говоря, от­ носительная погрешность, которую мы допускаем при взаимной замене этих величин, стремится к нулю при /г-»- со. В соответствии с общепринятой терминологией о функциях f ("), g (»). таких, что

lim / («) = со, Mm g (л) = со, Mm f (n)lg (л.) = 1 при л - * со, говорят, что они асимптотически равны. Асимптотическое

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

Наконец, Э?3 применяется к словам Р вида

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

146

мерам I — I I I и попытаемся выяснить, можно ли для них предложить тыоринговы программы, которые быстрее при­ водят к результату, т. е. у которых временные сигнализи­ рующие медленнее растут. В случае I ясно, что убыстрение невозможно, ибо для слова 99...9 (п девяток) при любом

н чем ои отличается от процесса, протекающего в соответ­

цикле происходит стирание очередной палочки на левом конце массива палочек, а не на правом конце, как в случае программы 9Й2. Другое различие заключается в том, что десятичная запись числа, выработанная на очередном цикле, перемещается вправо на одну ячейку и тем самым продви­ гается вплотную к уцелевшему массиву палочек. На рис. 38 указаны записи на ленте после 369-, 370-, 371-го циклов и их взаимное расположение. Ясно, что длительность /-го

иначе говоря, Тс$ц по порядку меньше, чем.Гс^.

147

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

Можно ли еще улучшить этот результат? Точнее, воз­ можна ли тыорингова программа 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