Главная Промышленная автоматика.

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

Однако сколь ни сильны косвенные доводы, еще никому не удалось найти в ЛЭ-ТШЕ или -SPACE задачу, о которой можно было бы доказать, что она не принадлежит -TIME. Более того, похоже, что техники гл. 10 хватает лишь для доказательства того, что данная задача по меньшей мере столь же трудна, как и любая другая задача из некоторого класса. Чтобы действительно доказать, что данная задача не принадлежит -TIME, нужна техника, которая позволила бы показать, что существует хотя бы один язык, не допускаемый никакой детерминированной машиной Тьюринга за полиномиальное время. Чаще всего для подобной цели применяется диагонализация. Хотя этот способ, по-видимому, не достаточно силен, чтобы доказать, что -ТШЕФЛ-ТШЕ, с его помощью удалось получить результаты о иерархии как по емкостной, так и по временной сложностям для обоих типов машин Тьюринга - детерминированных и недетерминированных. Каждая теорема о иерархии имеет следующий вид: для данных "хороших" функций f{n) и g{n), таких, что f(n) растет "быстрее" gin), существует язык со сложностью fin), но не gin).

11.2. ИЕРАРХИЯ ПО ЕМКОСТНОЙ СЛОЖНОСТИ ДЛЯ ДЕТЕРМИНИРОВАННЫХ МАШИН ТЬЮРИНГА

Здесь мы докажем теорему о иерархии по емкостной сложности (иерархии по памяти) для детерминированных машин Тьюринга. Можно доказать аналогичные результаты для времени и для недетерминированных машин Тьюринга, но поскольку для наших целей они не нужны, мы оставляем их в качестве упражнений. Вспомним, что в силу следствия 3 леммы 10.1, если язык L допускается fe-ленточной ДМТ с емкостной сложностью S (п), он допускается и одноленточной ДМТ с емкостной сложностью Sin). Таким образом, можно ограничиться рассмотрением одноленточных ДМТ.

Чтобы получить результат о иерархии по емкостной сложности, надо перечислить ДМТ, т. е. каждому неотрицательному целому числу i поставить в соответствие единственную ДМТ. Кроме того, каждая ДМТ должна появляться в этом перечислении бесконечно много раз. Мы будем перечислять только одноленточные ДМТ с входным алфавитом {О, "1}, ибо это все, что нам нужно. Для перечисления всех машин Тьюринга достаточно просто обобщить этот метод.

Не умаляя общности, можно принять следующие соглашения о способе представления одноленточных ДМТ.

1. Состояния имеют имена q, q,. . ., qa Для некоторогоs, причем qi - начальное н qg - допускающее состояния.



11.2. ИЕРАРХИЯ ПО ЕМКОСТНОЙ СЛОЖНОСТИ ДЛЯ ДМТ

2. Входным алфавитом служит {О, 1}.

3. Ленточным алфавитом служит {Хи Х,. . ., Xf) для некоторого t, где Xi=b, 2=0 и Хз=1.

4. Функция переходов б представляет собой список пятерок вида {qu Xj, q, X,. DJ, означающих, что 8{qi, Xj)= ={qh, Xi,D„), где qiHq - состояния, Xj и X - ленточные символы и D„ - направление сдвига головки: L (влево), R (вправо) и5 (остается на месте) при т=0, 1 и 2 соответственно. Считаем, что такая пятерка кодируется цепочкой 101(V10*1010»1.

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

Любое целое число, которое нельзя декодировать, считается представлением тривиальной машины Тьюринга с пустой функцией переходов. Каждая одноленточная ДМТ будет появляться в этом перечислении бесконечно много раз, поскольку, имея какую-то ДМТ, можно к началу ее кода приписывать единицы и получать все большие и большие целые числа, представляющие одно и то же множество пятерок.

Построим четырехленточную ДДТ Мо, рассматривающую свою входную цепочку х одновременно как код одноленточной ДМТ М и как вход для М. Мы построим Мо так, чтобы для каждой ДМТ М с данной сложностью нашлась хотя бы одна входная цепочка, которую допускает Мо, но отвергает М, или наоборот. Одна из способностей, которыми наделена машина Мо, состоит в возможности моделировать произвольную машину Тьюринга по ее описанию. Машина Мо будет распознавать, допускает ли машина Тьюринга М входную цепочку так, что при этом используется не более Si(x) клеток, где Si - некоторая функция. Если М допускает х, укладываясь в Si(x) клеток, то Мо не допускает х. В противном случае Мо допускает х. Таким образом, либо поведение машины Мо отличается от поведения t-й ДМТ на входе х, являющемся двоичным представлением числа t, либо 1-я ДМТ на входе х использует более Si(x) клеток.

Говорят, что Afo представляет диагонализацию по всем ДМТ с емкостной сложностью Si(n), ибо если вообразить двумерную таблицу, (i, /)-й элемент которой показывает, допустила ли t-я машина Тьюринга вход /, то поведение машины Мо будет отличаться от поведения некоторых машин Тьюринга на диагонали этой таблицы. В частности, Л1 о будет отличаться от машин Тьюринга, допускающих свой вход с емкостной сложностью, не большей Si(n). В силу след-is* А. Ахо, Дж. Хопкрофт, Дж. Ульнаа 4S3



Si in) •

Тогда существует язык L, допускаемый некоторой ДМТ с емкостной сложностью S 2 (п), но не допускаемый никакой ПМТ с емкостной сложностью Si{ny).

Доказательство. Пусть Мо - четырехленточная ДМТ, которая работает на входной цепочке х длины п следующим образом.

1. Мо отмечает S,(n) клеток на каждой ленте. После этого всякий раз, когда любая ее головка пытается выйти за отмеченные клетки, Мо останавливается, не допуская вход.

) В литературе часто приводится определение емкостной сложности машины Тьюринга, при котором не учитывается число клеток, просмотренных на входной ленте,- ведь на входной ленте нельзя изменять символы. При таком определении можно также рассматривать и функции для емкостной сложности, меньшие п, и из посылки георемы убрать условия Si(/i)/i и Sa(n)n. Поскольку здесь нас интересуют лишь большие емкостные сложности, то результат для сложностей, меньших п, не стоит дополнительных деталей, нужных для него, и мы его опускаем. В этой теореме можно ослабить ограничение на конструируемость Si(n) по памяти.

ствия 3 леммы 10.1 существует одноленточная ДМТ УИц, эквивалентная Мо к имеющая ту же емкостную сложность Поскольку сама машина Мо тоже представлена в таблице (скажем, это k-я ДМТ при некотором k) и она не может отличаться от себя, то можно заключить, что емкостная сложность машин Мо и Мо не есть Si(n). Фактическая конструкция Мо усложнена из-за нашего желания построить Мо так, чтобы она имела такую емкостную сложность 5г(«), что Si(n) и Siln) почти одинаковы.

Определение. Пусть /(п) - произвольная функция. Обозначим через inf / (п) предел при п->-оо наибольшей нижней грани последо-

П->ао

вательности /(п), /(п+1).....

Пример 11.1. Так как (п=+1)/п монотонно убывает, то

mf-=lim -=1.

В качестве второго примера рассмотрим /(п) = 1-1/п, если п не есть степень числа 2, и / (п)=п в противном случае. Тогда inf / («)=1,

поскольку наибольшая нижняя грань последовательности /(«), /(п+1), .. ., равна либо 1-1/п, если п не есть степень числа 2, либо 1-1/(п+1), если п - степень числа 2. □

Теорема 11.1. Пусть Si(n)>n и 8г{п)п - две функции, конструируемые по памяти, причем

ыФ!=о.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 [147] 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0052