Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

390 П Фишер, А. Мейер, А. Розенберг
имеет в рабочем алфавите т различных символов: 0 (пустой), 1, . . . , т — 1. Если в некоторый момент непустая часть ленты ТМ имеет вид агаг-\ . . . а^сЬйЬ\ ... bs, а пишуще-читающая головка стоит в с, тогда счетчик А содержит число
\аг\-т'+ аг_! | • тг~1 4- ... + а, | • т счетчик В — число
Ь - т5 + b- | - га5"1 + ... + b | • m
a счетчик С — нуль ( ak означает номер символа ak в вышеприведенном списке). Число \с\ хранится в конечной памяти.
Если ТМ заменяет с на а и передвигает головку вправо, СМ умножает содержимое счетчика Л на m и прибавляет \d\, затем делит содержимое В на т, запоминая остаток Ьо\ в конечной памяти. Передвижение влево моделируется аналогично. В процессе работы счетчик С используется как вспомогательный регистр.
Теперь ясно, что если ТМ просматривает не более [log 5] квадратов ленты, то содержимое счетчиков Л, В, С никогда не превосходит
Результат следует теперь из леммы 3.2.
3.2. Связь пространственных и временных ограничений. Су-
ществует сильная зависимость между временем и пространством при вычислениях на СМ, точно выражаемая следующей теоремой.
Теорема 3.2. Пусть S — функция, S(n) >я. Язык L распознаваем СМ, которая работает на пространстве S, в том и только в том случае, когда он распознаваем СМ, время работы которой ограничено полиномом от 5.
Доказательство. Пусть L распознается СМ, которая имеет q состояний, k счетчиков и работает на пространстве 5. При работе со входом длины п может возникнуть не более q-n(S(n) + \)h различных конфигураций (определение конфигурации см. в разд. 1.1). Ясно, что машина никогда не остановится, если в процессе вычислений какая-то конфигурация повторяется. Но по определению при распознавании СМ всегда останавливается, поэтому время работы СМ оценивается как
Т (п) = q • п - (S (п) + 1 f ^ с • S (n)k+l
для некоторой не зависящей от п константы с. Обратно, если время работы ограничено полиномом от S, то и пространство

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 391 392 393 394 395 396 397 398 399 400 410 420 430


Математика