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

н 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