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

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

2. Если X не является кодом никакой одноленточной ДМТ, Л!» останавливается, не допуская вход.

3. В прочих случаях пусть х - код ДМТ М. Мо определяет число t используемых машиной М символов на ленте и число s ее состояний. Третья лента машины Мо может играть роль "промежуточной" памяти при вычислении t. Затем Мо разбивает свою вторую ленту на Si (п) блоков по Г og О клеток в каждом, эти блоки отделяются друг от друга клетками, содержащими маркер #; таким образом, всего клеток (1-f -f Г og П )5i (n), если (1 + Г log П )Si ("XSj («). Каждый символ на ленте машины М будет закодирован двоичным числом в соответствующем блоке на второй ленте машины Мо. Вначале Мо помещает свой вход в виде его двоичного кода в блоки ленты 2, а неиспользованные блоки заполняет кодом пустого символа.

4. На ленте 3 Мо образует блок из flogsl + flog Si («)"! + -f Г log П -Si (") клеток и вначале записывает в них нули; здесь снова предполагается, что число требуемых клеток не превосходит Sin). Лента 3 играет роль счетчика, в который можно помещать числа вплоть до sSl{n)tK

5. Мо моделирует машину М, используя ленту 1 (т. е. свою входную ленту) для определения шагов машины М и ленту 2 для моделирования ленты машины М. Номера шагов машины М записываются в виде двоичных чисел в блок на ленте 3, а на ленте 4 хранится состояние машины М. Если М допускает свой вход, то Мо останавливается, не допуская свой. Мо допускает вход, если М останавливается, не допуская свой вход, или если для моделирования работы М машина М» пытается занять больше клеток на ленте 2, чем отведено, или если переполняется счетчик на ленте 3, т. е. число шагов, сделанное машиной М, превосходит sSl{n)tK.

Машина Тьюринга Мо, описанная выше, обладает емкостной сложностью Sa{«) и допускает некоторый язык L. Допустим, что L допускается какой-то ДДТ М, с емкостной сложностью Si («). В силу следствия 3 леммы 10.1 можно считать машину М,- одноленточной. Пусть Mi имеет s состояний и t символов на ленте. Записывая одну за другой пятерки, изображающие команды машины М; и добавляя при необходимости единицы к началу полученной цепочки, можно построить цепочку w длины п, представляющую машину Mi, причем п столь велико, что

S,(«)>MAX[(1 + riogn)5i(«),

Г log s 1 + Г log S, (n) 1 + Г log t -] S, («)].

Равенство inf [Si (rt)/Sj («)1=0 гарантирует, что такое n можно найти.

15** 4SS



Теперь, когда на вход машины Ма подается цепочка w, у Мо достаточно места для моделирования работы Mi. Она допускает вход w тогда и только тогда, когда Mi не допускает его. Но мы предположили, что машина М; допускает L, т. е. ее выход совпадает с выходом М на всех входах. Заключаем отсюда, что машина Mi невозможна, т. е. язык L не допускается никакой ДМТ с емкостной сложностью Si(n). □

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

11.3. ЗАДАЧА, ТРЕБУЮЩАЯ ЭКСПОНЕНЦИАЛЬНЫХ ВРЕМЕНИ И ПАМЯТИ

В разд. 10.6 мы изучили задачу пустоты дополнения для регулярных выражений и показали, что она полна для полиномиальной емкости. Поскольку класс регулярных множеств замкнут относительно пересечения и дополнения, то добавление знаков операций пересечения П и дополнения -i к системе обозначений для регулярных выражений не увеличивает класса множеств, которые можно описать такими выражениями. Однако использование этих знаков сильно сокращает длину выражений, необходимых для описания некоторых регулярных множеств. Из-за возможности такого сокращения для решения ряда задач с расширенными регулярными выражениями требуется еще больше времени, чем для решения задач с "обычными" регулярными выражениями (при условии, что время измеряется как функция длины данного выражения).

Определение. Расширенное регулярное выражение над алфавитом 2 определяется следующим образом.

1. е, 0 и а из 2 являются расширенными регулярными выражениями, представляющими соответственно {е}, пустое множество и {а}.

2. Если Rl и Ra - расширенные регулярные выражения, представляющие соответственно языки Li и La, то (Ri+Ra), (RiRa), {Rl), {Rif)Ra) и (-i/?i) - тоже расширенные регулярные выражения, представляющие соответственно языки LiULa.LiLa, Ll, LiflLa и 2*-Ll.

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

+ Л -1 • *.



Далее, знак операции - обычно не пишется. Например a~[b*+cnd означает

((а-(-!(&.))) +(end)).

Если расширенное регулярное выражение не содержит знаков дополнения, то его называют полу расширенным. Задача пустоты дополнения для полурасширенных регулярных выражений состоит в выяснении, пусто ли дополнение множества, представленного данным выражением R (или, что эквивалентно, представляет ли R все цепочки во входном алфавите). Например, регулярное выражение

Ь* + Ь*аа*{г + & (а + Ь) (а + &)•) + b*aa*b

представляет множество {а+Ь)*, поскольку

Ь* + Ь*аа* {& + b{a + b){a+ b)*) = -i b*aa*b.

Приступим к доказательству того, что задача пустоты дополнения для полурасширенных регулярных выражений не принадлежит классу -SPACE и, значит, не принадлежит классу olf-TIME, ибо оЛГ-ТШЕ содержится в -SPACE. Фактически мы покажем, что существуют такие полурасширенные регулярные выражения длины п, что решение задачи пустоты дополнения для них требует память (и, следовательно, время) по меньшей мере ссЧ°", где с>»0 и с>»1- некоторые постоянные.

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

Кроме сокращений, введенных в разд. 10.6, будем использовать

Rt для обозначения расширенного регулярного выражения

Ri+R2+- +Rh- Mbi также будем писать R+ вместо RR*. Когда мы будем говорить о длине выражения, то будем подразумевать длину исходного выражения, записанного без этих сокращений.

Теперь введем понятие измерителя. Пусть 2 - алфавит их - произвольная цепочка в 2*. Положим ЦИКЛ (х)={гг/х=г/г, где уЕ* и гЕ*}. Пусть # -специальный маркер, не принадлежащий Е. Множество ЦИКЛ {х#) называется измерителем с длиной \х#\. Таким образом, измеритель - это множество всех циклических перестановок цепочки х#. Когда это не будет вызывать недоразумений, мы будем называть измерителем саму цепочку х#.

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





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