1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 8
Текст из файла (страница 8)
Если мгновенное описаниеР, переходит в мгновенное описание О, заодиишагмашины Тьюринга М, то пишут О,| — ИР,(знак ! — читается "переходит в"). Если О, ! — МО,)-м... 1-мО„для некоторого п)2, то пишут О, ) — м0„. Если либо 0=0', либо О!-'м Р', то пишут 0 ! — "ИО'.
Данная й-ленточная машина Тьюринга М= (|е, Т, 1, 6, Ь, д„а|) допускает слово а,а,... а„, где а| — элементы из 1, если (деа, а,... ...а„, д„д„..., ае)) — "м (а„а„..., аа) для некоторых а,, содержащих дь !!ример 1.9. На рис. !.22 приведена последовательность мгновенных списаний машины Тьюринга, изображенной на рис. 1.21, ко- ') Полпндромом навмваетсн слово, совпадающее с самим собой при чтении с копна, например 0|000|0.
42 ч я ю и Ц Ф ,о о и х Ф ч о о ш о Новый символ, сдвиг головки Символ вз Примечания ленте ! ~ ленте 2 лента ! ~ лента 2 О, 5 1, 5 Ь, 5 Если вход иепуст, го на ленте 2 печатается Х и головка сдвигается вправо; машина переходит в состояние В противном случае машина переходит в состояние дз. х, В Х, й Ь, 5 рз чз сз Ь, 5 Ь, 5 Ь, 1. Головка на ленте 1 остается на месте, а на ленте 2 движется влево до Х Затем машина переходит в состояние Сз О 1 Х О, !. 1, !. х, й Состояния дз и оз чередуются. В зз сравниваются символы на обеих лентах, головка на ленте 2 сдвигается вправо н машина переходит в дз. Иэ Озона переходит в дз и допускает входное слово, если головка достигла Ь на ленте 2.
Если же не достигла, то головка на ленте 1 сдви. гается влево н машина возвращается е сосгаяние Сз. Чередование Чз и оз предотвращает уход головки на ленте ! за ее левый конек. О, 5 1, 5 О, К 1, В чз дз О. 1. О, 1. 1, Ь О, 5 1, 5 О, 5 1, 5 О, 5 1, 5 ! О 1 Ь Ь чз йз йз чз чв сз В ходное слово допус- кается 43 Рис. !.2!. Функпня переходов машины Тьюринга распознавшей палиндромы.
гл. 1 модели вычисления Риш П22. Послеаоватааьиость МО машины Тьюринга, торой подано на вход слово 010. Так как д,— заключительное сос- тояние, эта машина Тьюринга допускает 010. В дополнение к естественной интерпретации машины Тьюринга как устройства, допускающего какой-то язык, ее можно рассматривать как устройство, которое вычисляет некоторую функцию 1.
Аргументы втой функции кодируются на входной ленте в виде слова х со специальным маркером ~, отделяющим )ах друг от друга. Если машина Тьюринга останавливается, имея на ленте, выделенной в качестве выходной, целое число у (значение функции), то полагают )'(х)=у.
Таким образом, процесв вычисления мало отличается от процесса допускания языка. Временная сложность Т(п) машины Тьюринга гИ равна наибольшему числу шагов, сделанных ею при обработке входа длины и (для всех входов длины п), Если на каком-нибудь входе длины п машина Тьюринга не останавливается, то для этого п значение Т(п) не определено.
Емкастная сложность 5(п) машины Тьюринга равна наиболь. шему расстоянию от левого конца ленты, которое должна пройти головка при обработке входа длины п. Если головка на какой-то ленте неопределенно долго движется вправо, то функция В(п) не определена. Порядок величин при применении з качестве модели машины Тьюринга мы будем обозначать через Омг. 44 (ч,01 0, д,»- (т,01 0, 1- (Од,)О, ~- (01д,О, )- (О)ОЙ„ )- (0)Од„ )- (0)Од„ 1- (0)Од„ )- (0)Од„ )- (О)д,О, )- (0(а,О, )- (Од„(0, )- (Од,10, )- (<)аО(О )-(<),010 )- (д,01 0 хд,) х Од,) х01 ),) х 0)Од,) х 01д,О) х Од,)О) х д,010) ),х 010) х да010) х Оо,10) х Од,10) хО(д,О) х О)д,О) х 0)Од,) х 010),) ЬГ, СВЯЗЬ МАШИН ТЬЮРИНГА Н РАМ Пример 1.
!б. Временная сложность машины Тьюринга, изображенной на рив. 1.20, равна Т(п)=4п+3, а ее емкостная сложность равна 5 (п)=а+2. Это можно проверить, последовав случай, когда вход на самом деле является палиндромом. ( ) 1.7. СВЯЗЬ МАШИН ТЬЮРИНГА И РАМ Основное применение машины Тьюринга (МТ) находят в установлении нижних опенок на время и память, необходимые для решения данной задачи. В большинстве случаев мы можем установить нижние оценки только с точностью до полиномиальной связанности.
Лля более точных оценок потребуется рассматривать более специфические детали конкретных моделей. К счастью, вычисления на РАМ и РАСП полиномиально связаны с вычислениями на МТ. Рассмотрим связь между РАМ и МТ. Очевидно, что РАМ может моделировать работу й-ленточной МТ, помещая по одной клетке МТ в регистр. В частности,!-ю клетку 1-й ленты можно хранить в регистре к(+!+с, где с — постоянная, назначение которой — дать РАМ некоторое "оперативное пространство".
В него включаются й регистров для запоминания положений й головок МТ. РАМ может считывать клетки МТ, используя косвенную адресацию с помощью региитров, содержащих положения головок на лентах. Предположим, что данная МТ имеет временную сложность Т(п))п. Тогда РАМ может прочитать ее вход, запомнить его в регистрах, представляющих первую ленту, и смоделировать эту МТ за время 0 (Т (и)) при равномерном весовом критерии и 0(Т(п) 1оя Т(п)) при логарифмическом.
В любом случае время на РАМ ограничено сверху полиномом от времени МТ, ибо любая функция типа 0(Т(п) !од и) есть, разумеется, 0(Т1(п)). Обратное утверждение верно только при логарифмическом весовом критерии для РАМ. При равномерном весе п-шаговая про. грамма для РАМ без входа может вычислять числа порядка 2*", что требует порядка 2" клеток МТ только для запоминания и считывания, Поэтому при равномерном весе, очевидно, нет полиномиальной связи между РАМ и МТ (упр.
1.19). Хотя при анализе алгоритмов мы предпочитаем равномерный весовой критерий в силу его простоты, мы должны отвергнуть его, если пытаемся установить нижние границы на временную сложность. РАМ с равномерным весом вполне разумна, когда рост чисел по порядку не превосходит размера задачи.
Но, как мы уже говорили, при использовании РАМ в качестве модели размер чисел "заметается под ковер", н вряд лн можно получить полезные нижние оценки. Для логарифмического веса, однако, верна следующая теорема. Теорема 1.3. Пусть Š— язык, допускаемый некоторой РАМ ва время Т(п) при логарифмическом весе. Если в РАМ-программе ГЛ. Ь МОДЕЛИ ВЫЧИСЛЕНИЙ т(а 11 Ф С1 Яа ВЕ 11 Ва СЕ Яв ЧЕ ' 1Е тй СЕ Е)Е 1(е !1 Рнс. !.23. Представление РАМ на МТ.
нет умнозсений и делений, то на многоленточных машинах Тыо. ринга Е имеет временную сложность не более 0(Т'(п)). Д о к а з а тел ь с т в о. Представим все не содержащие нуля регистры рассматриваемой РАМ, как показано на рис. 1.23. На ленте помещена последовательность паР чисел (1л с;), записанных в двоичной форме без нулей в начале слова и разделенных маркера. ми.
Для каждого ! число с1 есть содержимое регистра 11 РАМ. Содержимое сумматора РАМ хранится в двоичном коде на второй ленте, а третья играет роль рабочей памяти. Еще две ленты служат для записи входа и выхода РАМ. Каждый шаг программы РАМ пре1~- ставлеи конечным числом состояний МТ. Мы не будем описывать моделирование всех команд РАМ, а рассмотрим только команды А00»20 и 8ТОНЕ 30, которые разъясняют общую идею. Для А00 «20 можно устройть МТ так, чтобы она работала следующим образом. 1.
На ленте 1 разыскивается место, соответствующее регистру 20 в РАМ, т.е. последовательность 4е4~ 10100 4с. Если оно находится, на ленту 3 помещается следующее за ним число, которое будет содержимым регистра 20. Если такое место не нашлось, машина останавливается — содержимое регистра 20 равно О, и поэтому косвенную адресацию произвести нельзя. 2. На ленте 1 разыскивается место, где хранится регистр РАМ, номер которого записан на ленте 3.
Если оно находится, то содержимое этого регистра записывается на ленту 3. Если нет, туда помещается О. 3. Число, записанное на ленту 3 на шаге 2, прибавляется к содержимому сумматора, которое хранится на ленте 2. Для моделирования 8ТОРсЕ 30 можно так построить МТ, чтобы она работала следующим образом. 1, Разыскивается место расположения регистра 30 в РАМ, т. е. р(е.ф11110ф. 2.
Если оно находится, то на ленту 3 записывается все, что расположено справа от .фри.111104с, кроме числа, стоящего непосредственно справа (т. е. старого содержимого регистра 30). Затем содержимое сумматора (на ленте 2) записывается непосредственно справа от э~~111!ОФ, а за ним помещается слово, скопированное иа ленту 3. 1 В ЯЗЫК ВЫСОКОГО УРОВНЯ вЂ” УПРОЩЕННЫЙ АЛГОЛ 3. Если на ленте 1 не нашлось места, соответствующего регистру 30, то, дойдя до самого левого пустого символа, машина печатает 111!04.', затем содержимое сумматора и, наконец, э~~-. Подумав немного, нетрудно понять, что можно указать МТ, которая правильно смоделирует РАМ.
Мы должны показать, что вычисление иа РАМ с логарифмическим весом й потребует не более 0(й') шагов на машине Тьюринга. Сначала заметим, что регистр может появиться иа ленте 1, только если его текущее значение когда-то раньше было помещено в этот регистр. Вес записи с! в регистр (; равен 1(с;)+1((г), что с точностью до постоянной равно длине нашего представления гвг',е(гфсзфф..
Отсюда мы заключаем, что длина непустой части ленты 1 есть 0(я). Моделирование любой команды, отличной от 3ТОРсЕ, имеет порядок длины ленты 1, т. е. 0 (й)„ибо основное время уходит на поиск на ленте. Аналогично время моделирования 3ТОЙЕ не больше суммы времен поиска на ленте 1 и копирования ее — все вместе 0(й). Следовательно, одну команду РАМ (кроме умножения и деления) можно промоделировать не более чем за 0(й) шагов МТ. Так как одна команда РАМ занимает при логарифмическом весе по крайней мере одну единицу времени, общее время, затрачиваемое соответствующей МТ, есть 0(й'), что и требовалось доказать. С! Если в РАМ-программе участвуют команды умножения и деления, то можно написать подпрограммы для МТ, выполняющие эти операции с помощью сложений и вычитаний.
Читателю предоставляем доказать, что логарифмические веса этих подпрограмм не больше квадрата логарифмических весов соответствующих команд. Таким образом, нетрудно доказать следующую теорему. Теорема 1.4. РАМ и РАСП с логарифмическим весом и многоленгпочные машины Тьюринга полиномиально связаны, Д о к а з а те л ь с т в о.
Примените теоремы 1.1 — !.3 и проанализируйте подпрограммы для умножения и деления. С) Аналогичный результат справедлив и для емкостной сложности хотя он представляется менее интересным. 1.8. ЯЗЫК ВЫСОКОГО УРОВНЯ вЂ” УПРОЩЕННЫЙ АЛГОЛ Наши основные меры сложности определяются в терминах операций для РАМ, РАСП и машин Тьюринга, но мы, вообще говоря, не хотим описывать алгоритмы в терминах столь простых машин, да в этом и иет необходимости. Для того чтобы нагляднее описывать алгоритмы, мы введем некоторый язык высокого уровня, называемый Упрощенным Алголам. Программу на Упрощенном Алголе можно перевести непосредственно в программу для РАМ или РАСП. Фактически это была бы гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
