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

Чтобы обработать список целых чисел ij, i,. . ., i, машина Mi просматривала бы входную цепочку x=#B{ii)#B{i2). . .#B{i). Машина М при решении той же задачи просматривала бы входную цепочку а;=1010. . .10*, которая может оказаться экспоненциально длиннее цепочки х. Таким образом, хотя Mi в некотором смысле экспоненциально быстрее, чем НМТ на рис. 10.1, ее временная и емкостная сложности, поскольку вход соответственно укорочен, все равно равны 0{п), где п - длина входа. □

С помощью моделирования можно показать, что любой язык, допускаемый какой-нибудь НМТ, допускается также и некоторой ДМТ, но за это, по-видимому, придется расплачиваться сильным увеличением временной сложности. Наименьшая верхняя граница, которую можно установить для такого моделирования, экспоненциальна. Другими словами, если Т{п) - разумная функция, задающая временную сложность (разумная в том смысле, что она "конструируема по времени", этот термин определяется в гл. И), то для каждой НМТ М, время работы которой ограничено функцией Т{п), можно найти такие постоянную с и ДМТ М, что L(M)= =L{M) и время работы машины М составляет 0(с""").

Этот результат можно доказать, построив ДМТ М, моделирующую машину М путем полного перебора возможных вычислений. Существует постоянная d, ограничивающая число выборов очередного шага машины М во всех ситуациях. Поэтому последовательность, содержащую вплоть до Т{п) шагов работы машины М, можно представить цепочкой в алфавите 2 = {О, 1,. . ., d-l}, длина которой не превосходит Т{п). М моделирует поведение машины М на входе X длины п следующим образом. М последовательно порождает в лексикографическом порядке все цепочки из S*, длины которых не превосходят Г(п). Таких цепочек не более (d+l)"". Когда новая цепочка w порождена, машина М моделирует последовательность шагов машины М, представленную цепочкой w. Если приводит к тому, что М допускает х, то М также допускает х. Если не представляет возможную последовательность шагов машины М или не приводит к допусканию х машиной М, то М повторяет этот процесс со следующей цепочкой из S*.

М может промоделировать последовательность a„, за время 0{Т{п)). Порождение очередной цепочки w занимает 0{Т{п)) шагов. Поэтому все моделирование работы НМТ М может занять время 0(Г(п)(с(+1 )""), которое не превосходит 0(с<") для некоторой постоянной с. Детали моделирования оставляем в качестве упражнения.

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



Т{п), но про который можно доказать, что он не допускается никакой ДМТ с временной сложностью Т{п). Ситуация, связанная с емкостной сложностью, много приятнее.

Определение. Функцию S(n) назовем конструируемой по емкости (памяти), если некоторая ДМТ М, начав работу над данным входом длины п, поместит специальный маркер на 8{п)-ю клетку одной из своих лент, просмотрев не более S{n) клеток на каждой ленте. Самые обычные функции, например полиномы с целыми коэффициентами, 2", п\, Г " log(n+l) ~, конструируемы по емкости.

Можно показать, что если S (п) - конструируемая по емкости функция, а М - НМТ с емкостной сложностью, ограниченной функцией S{n), то найдется такая ДМТ М с емкостной сложностью O(Sn)), что L(M)=L{M).

Одна из стратегий, с помощью которой М может моделировать машину М, заключается в интересном приложении приема "разделяй и властвуй". Если емкостная сложность ленточной НМТ М= =(Q, Т, I, б, Ь, 0. gt) ограничена функцией S(n), конструируемой по емкости, то для некоторой постоянной с число различных МО, в которые М может попасть, начав работу с входа длины п, не превосходит с"", а точнее IIQII •(11Л1+1)*"" "(S (п))*, где первый множитель представляет число состояний, второй ограничивает число возможных состояний лент, а последний - число возможных положений головок. Поэтому если Cil-mCj, to М может дойти из МО Ci в МО Са по некоторому пути, состоящему не более чем из (.sm) шагов. Можно выяснить, осуществим ли переход Ci j-Jti за 2t шагов, проверив для всех Сз, осуществимы ли переходы С, НмСз и Сз h-AjCa за i шагов.

Таким образом, стратегия, на которой основана работа УИ, состоит в том, чтобы установить с помощью описанного ниже алгоритма, приведет ли начальное МО Со к какому-нибудь допускающему МО.

Алгоритм 10.1. Детерминированное моделирование НМТ

Вход. НМТ М с границей S (л) на емкостную сложность, где S (п) - конструируемая по емкости функция, и входная цепочка w длины п.

Выход. "Да", если wL{M), и "нет" в противном случае.

Метод. Рекурсивная процедура nPOBEPKA(Ci, Са, i), приведенная на рис. 10.3, распознает, осуществим ли переход Ci I-м Са за / шагов. Если да, то она принимает значение true, в противном случае false. В этом алгоритме Ci и Са обозначают МО, в которых на каждой ленте использовано не более S (п) клеток.

Полный алгоритм состоит в вызове ПРОВЕРКА(Со, Cj, С"") для каждого допускающего МО Cj, где Со - начальное МО машины М для входа W. Если обнаружится, что один из таких



procedure ПРОВЕРКА (С„ С, i): if 1 = 1 tlien

if Cjl-Cj или Ci = C2 then return true

else return false else

begin

for каждого MO C3, в котором на каждой ленте использовано не более S{n) клеток do if ПРОВЕРКА (С., Сз, Г i/21) и ПРОВЕРКА (С„ С, L i/2 J> then return true; return false end

Рис. 10.3. Процедура ПРОВЕРКА.

вызовов выдал значение true, то ответом алгоритма будет "да", в противном случае "нет". □

Теорема 10.1. Если М - НМТ с конструируемой по емкости емкостной сложностью S (п), то найдется такая ДМТ М с емкостной сложностью 0(S{n)), что L(M)=L{M).

Доказательство. Доказательство состоит в реализации алгоритма 10.1 на машине Тьюринга. Мы знаем из разд. 2.5, как промоделировать на РАМ рекурсивную процедуру ПРОВЕРКА. Ту же стратегию со стеком можно применить на машине Тьюринга. Поскольку аргументами процедуры ПРОВЕРКА, занимающими существенную память, служат МО длины 0(S(n)), то на ленте надо расположить фрагменты стека того же размера; это можно сделать потому, что функция S (п) конструируема по емкости. Анализируя процедуру ПРОВЕРКА, видим, что при каждом ее рекурсивном вызове третий аргумент уменьшается, по существу, вдвое. Поэтому можно показать, что в любой момент число фрагментов стека не превосходит l+logfc*""!. т. е. 0(5 (л)). Поскольку на каждый фрагмент приходится О (S (п)) ячеек, всего для стека наша машина Тьюринга использует 0(S(n)) клеток. Остальные детали конструкции машины Тьюринга оставляем в качестве упражнения. □

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





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.0027