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

Верхтя дорожка

Нижняя дорожка

Рис. 11.2. Новая форма правильных вычислений с измерителем.

функции S{n). Прежде чем приступить к доказательству, изменим немного определение правильного вычисления машины Тьюринга A1=(Q, Т, I, б, Ь, Qo, qt) с измерителем ЦИКЛ(л:#). Удалим первый маркер # и заменим последний маркер новым символом $ (рис. И.2). Обозначим через С; МО (дополненные, если надо, пустыми символами, чтобы их длина стала равной длине цепочки х); как и раньше, Ci\-Ci+i за один шаг машины М для 0<i<f, Со - начальное МО и С, содержит состояние

Будем использовать следующие обозначения (предполагаем, что

1) Ai=Tu (QxT) и {#, $} - алфавит верхней дорожки,

2) Aa=S и {#, $} - алфавит нижней дорожки,

3) hi. AiXAa->-Ai, причем hi {\а, b])=a,

4) hi. AiXA2->-Aa, причем hi{[a, b])=b.

Лемма 11.5. Пусть Ri - расширенное регулярное выражение для множества ЦИКЛ(л:#). Можно построить такое расширенное регулярное выражение Rt, представляющее множество циклических перестановок правильных вычислений машины Тьюринга М с из.чери-телем ЦИКЛ(л:#), что /?а есть 0(\Ri\), где постоянная зависит только от М.

Доказательство. Цепочка является циклической перестановкой правильного вычисления с измерителем ЦИКЛ(л:#) тогда и только тогда, когда

1) нижняя дорожка - циклическая перестановка цепочки вида {хф)*х$,

2) верхняя дорожка - циклическая перестановка правильного вычисления машины М и

3) верхняя и нижняя дорожки циклически переставлены одинаково.

Пусть R[ - это выражение Ri, в котором вместо # стоит символ $. Цепочки, удовлетворяющие условию 1, можно представить выражением /гг(UiOUf] Ua), где

Ui = 2* (#-f $) [(/?, + Ri)[\ (S* #H-S* $)J* S»,

i/a = (S + #)*$(S + #r.

Us-iRi + Ri)*.



Подвыражение [(/?i+/?i) П (2*#Ч-2*$)] в Ui представляет две цепочки хф и х%. Поэтому представляет 2*(#+$)(x#+ Выражение t/j содержит цепочки с ровно одним вхождением $. Поэтому всякая цепочка из i/iflj имеет вид У2фхфхф...х#х%хф...хфу1,

где Ух и у2 - некоторые цепочки из 2*. Выражение Un приводит к тому, что «/al+«/il=jf, откуда легко следует, что ухУгх для цепочек из Ui{\Ui{\ Ua- Таким образом, Si=Ui П П представляет нижнюю дорожку всех цепочек, удовлетворяющих условию 1.

Что касается условия 2, то в лемме П.4 мы видели, как Написать полурасширенное регулярное выражение для неправильных вычислений машины М с измерителем ЦИКЛ(л:#). Эта техника легко переносится на форму, показанную на рис. П.2, и мы предлагаем читателю самому построить выражение Е, представляющее циклические перестановки неправильных вычислений машины М с корректным измерителем на нижней дорожке. Применение операции дополнения к Е дает расширенное регулярное выражение Sg. Это единственное место, где применяется дополнение. Должно быть ясно, что все цепочки, представленные выражением SiRSa, удовлетворяют обоим условиям 1 и 2.

Выражение для условия 3 в предположении, что условия 1 и 2 выполнены, строится без особого труда. Надо лишь проверить, что один символ имеет $ на обеих дорожках. Пересекая это выражение с SiDSa, получаем требуемое. □

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

Интуитивно мы строим регулярное выражение для какого-то измерителя с небольшой длиной, скажем с длиной п. Затем используем его, чтобы построить новое регулярное выражение для всех циклических перестановок правильных вычислений с этим измерителем для некоторой машины Тьюринга, допускающей в точности одну цепочку длины п. Машина Тьюринга специально выбирается так, чтобы на входе длины п она делала по меньшей мере 2"+" шагов, поэтому множество циклических перестановок ее правильных вычислений само будет измерителем с длиной 2» или более. Повторяя этот процесс с новым измерителем, получаем измерители все с большими и большими длинами, но не меньшими 2", 2" и т. д.

Пусть Мо - конкретная одноленточная машина Тьюринга, которая ведет себя так:

1) проверяет, что ее входная лента начинается с последовательности символов а, для чего просматривает эту ленту до первого пустого символа,

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



ОТ О до 2"+-1 на части своей ленты, которая была занята символами а и следующим за ними пустым символом, 3) досчитав до 2"+!-1, останавливается и допускает свой вход.

Итак, Мо обладает следующими свойствами. Для каждого п она допускает в точности одну цепочку длины л, а именно а". Она делает это, выполняя единственное правильное вычисление, состоящее не менее чем из 2"+ шагов, поскольку половина ее шагов добавляет биты, а другая половина осуществляет переносы. Наконец, Мо просматривает только «-f 1 клеток ленты, когда ей подан вход длины п.

Исследуем теперь правильные вычисления машины Мо с измерителем ЦИКЛ(л:#), имеющие вид, показанный на рис. 11.2. Если л:=п+1, то существует единственное правильное вычисление машины Мо с измерителем ЦИКЛ(л:#), у которого верхняя дорожка начинается с [oOla. . . а Ь#. По лемме 11.5 для всех его циклических перестановок можно построить регулярное выражение/?2. Оно будет представлять множество, состоящее из циклических перестановок фиксированной цепочки 0)6(1X2)*- Цепочка hi{w) будет правильным вычислением машины Мо на входе а", где, напомним, jc=n+l. Так как Мо делает на входе а" не менее 2"* шагов, Ri можно взять в качестве измерителя с длиной не менее

Итак, пусть дан измеритель ЦИКЛ(л;#), представленный выражением Ru где JCgS*. Тогда по Ri и описанной выше ДМТ Мо можно построить измеритель с длиной, не меньшей 2-*i. По лемме 11.5 для него найдется регулярное выражение Ri длины не более где постоянная d зависит только от Мо.

Лемма 11.6. Для всех il и т2 существует измеритель с длиной, не меньшей g{i, т) который можно представить расширенным регулярным выражением длины не более сфу-т, где Ci- постоянная, зависящая omMoU введенная в предыдущем абзаце, ас - постоянная из леммы 11.1.

Доказательство. Докажем индукцией по i, что найдется расширенное регулярное выражение Ri, представляющее ЦИКЛ(л;#) для некоторого х, где \x#\g(i, т) и /?iKc(Ci)-/k=. Базис (1 = 1) следует из леммы 11.1 при k=m, поскольку можно построить расширенное регулярное выражение длины ст, представляющее ЦИКЛ(л:#).

Для шага индукции допустим, что построено расширенное регулярное выражение Ri длины /?ic(ci)~W, представляющее ЦИКЛ(л:#), где (j-1, т). Тогда на основе проведенного

выше анализа, касающегося ДМТ Мо, заключаем, что можно по-

) Функция g определена в самом начале раздела.





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