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

(„010, 9jb (?,010,

XQx)

к (0,10,

XOq,)

X0\q,)

\- (010,,

XOIOJ

xOlqO)

X 02 10)

ХгОЮ)

К {010<7з,

гХОЮ)

Н (01с?з0,

Xq,0\0)

Н (01 аД

X 0,10)

ь (0310,

xOq.m

ь (0410,

xO\q,0)

к (зОю,

Х01з0)

h-(4010,

X 010(7,)

к (.010,

xOlOq,)

Рис. 1.22. Последовательность МО машины Тьюринга.

торой подано на вход слово 010. Так как 95- заключительное состояние, эта машина Тьюринга допускает 010. □

В дополнение к естественной интерпретации машины Тьюринга как устройства, допускающего какой-то язык, ее можно рассматривать как устройство, которое вычисляет некоторую функцию /. Аргументы этой функции кодируются на входной ленте в виде слова X со специальным маркером #, отделяющим их друг от друга. Если машина Тьюринга останавливается, имея на ленте, выделенной в качестве выходной, целое число у (значение функции), то полагают fix)-у. Таким образом, процесс вычисления мало отличается от процесса допускания языка.

Временная сложность Т (п) машины Тьюринга М равна наибольшему числу шагов, сделанных ею при обработке входа длины п (для всех входов длины п). Если на каком-нибудь входе длины п машина Тьюринга не останавливается, то для этого п значение Т(п) не определено.

Емкостная сложность S(n) машины Тьюринга равна наибольшему расстоянию от левого конца ленты, которое должна пройти головка при обработке входа длины п. Если головка на какой-то ленте неопределенно долго Движется вправо, то функция S{n) не определена. Порядок величин при применении в качестве модели машины Тьюринга мы будем обозначать через 0мг.



1.7, СВЯЗЬ МАШИН ТЬЮРИНГА И РАМ

Пример 1.10. Временная сложность машины Тьюринга, изображенной на рис. 1.20, равна Т (п)=4п+3, а ее емкостная сложность равна S {п)=п+2. Это можно проверить, исследовав случай, когда вход на самом деле является палиндромом. □

1.7. СВЯЗЬ МАШИН ТЬЮРИНГА И РАМ

Основное применение машины Тьюринга (МТ) находят в установлении нижних оценок на время и память, необходимые для решения данной задачи. В большинстве случаев мы можем установить нижние оценки только с точностью до полиномиальной связанности. Для более точных оценок потребуется рассматривать более специфические детали конкретных моделей. К счастью, вычисления на РАМ и РАСП полиномиально связаны с вычислениями на МТ.

Рассмотрим связь между РАМ и МТ. Очевидно, что РАМ может моделировать работу ft-ленточной МТ, помещая по одной клетке Л\Т в регистр. В частности, i-ю клетку /-й ленты можно хранить в регистре ki+j+c, где с - постоянная, назначение которой - дать РАМ некоторое "оперативное пространство". В него включаются k регистров для запоминания положений k головок МТ. РАМ может считывать клетки МТ, используя косвенную адресацию с помощью регистров, содержащих положения головок на лентах.

Предположим, что данная МТ имеет временную сложность Т (п)п. Тогда РАМ может прочитать ее вход, запомнить его в регистрах, представляющих первую ленту, и смоделировать эту МТ за время 0(Т{п)) при равномерном весовом критерии и О (7 (п) log Т (п)) при логарифмическом. В любом случае время на РАМ ограничено сверху полиномом от времени МТ, ибо любая функция типа О (Т (п) ]og, п) есть, разумеется, 0(Т?(«)).

Обратное утверждение верно только при логарифмическом весовом критерии для РАМ. При равномерном весе /г-шаговая программа для РАА без входа может вычислять числа порядка 2", что требует порядка 2" клеток МТ только для запоминания и считывания. Поэтому при равномерном весе, очевидно, нет полиномиальной связи между РАМ и МТ (упр. 1.19).

Хотя при анализе алгоритмов мы предпочитаем равномерный весовой критерий в силу его простоты, мы должны отвергнуть его, если пытаемся установить нижние границы на временную сложность. РАМ с равномерным весом вполне разумна, когда рост чисел по порядку не превосходит размера задачи. Но, как мы уже говорили, при использовании РАМ в качестве модели размер чисел "заметается под ковер", и вряд ли можно получить полезные нижние оценки. Для логарифмического веса, однако, верна следующая теорема .

Теорема 1.3, Пусть L - язык, допускаемый некоторой РАМ за время Т{п) при логарифмическом весе. Если в VPJA-программе



. . .

Рис. 1.23. Представление РАМ

нет умножений и делений, то на многоленточных машинах Тьюринга L имеет временную сложность не более 0{Т{п)).

Доказательство. Представим все не содержащие нуля регистры рассматриваемой РАМ, как показано на рис. 1.23. На ленте помещена последовательность пар чисел (ij, Cj), записанных в двоичной форме без нулей в начале слова и разделенных маркерами. Для каждого / число Cj есть содержимое регистра ij РАМ. Содержимое сумматора РАМ хранится в двоичном коде на второй ленте, а третья играет роль рабочей памяти. Еще две ленты служат для записи входа и выхода РАМ. Каждый шаг программы РАМ представлен конечным числом состояний МТ. Мы не будем описывать моделирование всех команд РАМ, а рассмотрим только команды ADD *20 и STOR Е 30, которые разъясняют общую идею. Для ADD *20 можно устроить МТ так, чтобы она работала следующим образом.

1. На ленте 1 разыскивается место, соответствующее регистру 20 в РАМ, т.е. последовательность## 10100 #. Если оно находится, на ленту 3 помещается следующее за ним число, которое будет содержимым регистра 20. Если такое место не нашлось, машина останавливается - содержимое регистра 20 завно О, и поэтому косвенную адресацию произвести нельзя.

2. На ленте 1 разыскивается место, где хранится регистр РАМ, номер которого записан на ленте 3. Если оно находится, то содержимое этого регистра записывается на ленту 3. Если нет, туда помещается 0.

3. Число, записанное на ленту 3 на шаге 2, прибавляется к содержимому сумматора, которое хранится на ленте 2.

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

1. Разыскивается место расположения регистра 30 в РАМ, т. е. ##11110#.

2. Если оно находится, то на ленту 3 записывается все, что расположено справа от #ф\1110#, кроме числа, стоящего непосредственно справа (т. е. старого содержимого регистра 30). Затем содержимое сумматора (на ленте 2) записывается непосредственно справа от #-#1П10#, а за ним помещается слово, скопированное на ленту 3.





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