dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 82
Текст из файла (страница 82)
Ìàøèíû Òüþðèíãà è êîìïüþòåðûТеперь сравним машины Тьюринга с обычным компьютером. Эти модели кажутсясовершенно разными, но они допускают одни и те же языки — рекурсивно перечислимые. Поскольку понятие “обычный компьютер” математически не определено, аргументация данного раздела не является формальной. Нам приходится обращаться к интуициичитателя по поводу того, что могут компьютеры, в частности, если рассматриваемыечисла превосходят обычные пределы, обусловленные архитектурой компьютеров(например, 32-битовым представлением чисел). Утверждения данного раздела можноразделить на две части.1.Компьютер может имитировать машину Тьюринга.2.Машина Тьюринга может имитировать компьютер, причем за время, котороеможно выразить в виде некоторого полинома от числа шагов, совершаемыхкомпьютером.8.6.1. Èìèòàöèÿ ìàøèíû Òüþðèíãà íà êîìïüþòåðåВначале посмотрим, как компьютер имитирует машину Тьюринга.
Имея некоторуюконкретную машину Тьюринга M, мы должны написать программу, которая работает,как M. Одним из составляющих M является ее конечное управление. Поскольку M имееттолько конечное число состояний и конечное число правил перехода, наша программаможет закодировать состояния в виде цепочек символов и использовать таблицу переходов, которую она просматривает для определения каждого перехода. Аналогично, ленточные символы можно закодировать в виде цепочек символов фиксированной длины,поскольку ленточных символов также конечное число.Серьезный вопрос возникает, когда мы решаем, как программа должна имитироватьленту машины Тьюринга.
Эта лента может стать бесконечно длинной, но память компь-8.6. ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ È ÊÎÌÏÜÞÒÅÐÛСтр. 365365ютера — главная память, диск или другие устройства — конечна. Можно ли проимитировать бесконечную ленту с помощью фиксированного объема памяти?Если у нас нет возможности заменять запоминающие устройства, то проимитироватьдействительно нельзя; в таком случае компьютер был бы конечным автоматом, и допускал бы только регулярные языки.
Однако обычные компьютеры имеют заменяемые запоминающие устройства, например, “Zip”-диски. В действительности обычный жесткийдиск можно снять и заменить пустым, но идентичным диском.Поскольку очевидного предела на количество используемых дисков нет, будем считать, что доступны столько дисков, сколько может потребоваться компьютеру. Тогда этидиски можно разместить в двух магазинах (рис.
8.21). Один магазин содержит данные вудаленных клетках ленты машины Тьюринга, расположенных слева от ее головки, а другой — в дальних клетках справа от головки. Чем дальше в магазине расположены данные, тем дальше они от головки на ленте.ПроцессорЛента слева от головкиЛента справа от головкиРис. 8.21. Имитация машины Тьюринга на обычном компьютереЕсли ленточная головка МТ сдвигается далеко влево и достигает клеток, не представленных в текущем смонтированном диске, то программа печатает сообщение “обменслева”. Смонтированный диск снимается человеком-оператором и помещается на вершину правого магазина.
На компьютер монтируется диск с вершины левого магазина, ивычисления продолжаются.Аналогично, если ленточная головка МТ достигает удаленных клеток, не представленных на текущем смонтированном диске, то печатается сообщение “обмен справа”. Человекперемещает текущий диск на вершину левого магазина и монтирует на компьютер диск с366Стр. 366ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀвершины правого магазина. Ситуация, когда какой-либо магазин пуст, а компьютер требует, чтобы диск из него был смонтирован, означает, что МТ достигла области пробелов наленте.
В этом случае оператору придется купить новый диск и смонтировать его.8.6.2. Èìèòàöèÿ êîìïüþòåðà íà ìàøèíå ÒüþðèíãàНужно также провести обратное сравнение: существуют ли вещи, которые можетсделать обычный компьютер, а машина Тьюринга — нет. Важным вторичным вопросомявляется вопрос, может ли компьютер делать определенные вещи существенно быстрее,чем машина Тьюринга. В этом разделе обосновывается, что МТ может имитироватькомпьютер, а в разделе 8.6.3 — что эта имитация может быть достаточно быстрой в томсмысле, что “всего лишь” полиномиальная зависимость разделяет время работы компьютера и МТ для решения какой-либо проблемы. Напомним читателю еще раз, что существуют немаловажные причины считать подобными все времена работы, лежащие в пределах полиномиальной зависимости друг от друга, тогда как экспоненциальные отличияво времени работы “слишком велики”.
Теория, в которой проводится сравнение полиномиального и экспоненциального времени работы, будет рассмотрена в главе 10.Ïðîáëåìà î÷åíü áîëüøèõ ëåíòî÷íûõ àëôàâèòîâДоводы раздела 8.6.1 становятся сомнительными, если число ленточных символов настолько велико, что код одного ленточного символа не умещается на диске. Для этогонужно действительно очень много ленточных символов, поскольку 30-гигабайтныйдиск, например, может представить любой из 2240000000000 символов. Аналогично, число состояний могло бы быть настолько большим, что состояние нельзя было представить, используя целый диск.Для одного из разрешений этой проблемы следует ограничить число ленточных символов, используемых МТ. Любой ленточный алфавит можно закодировать в двоичном виде.
Таким образом, любая МТ M может быть проимитирована с помощью другой МТ M′, использующей только ленточные символы 0, 1 и B. Однако у M′ должнобыть очень много состояний, поскольку для имитации перехода M МТ M′ должнасканировать ее ленточный символ и запомнить в своем конечном управлении все биты, показывающие, какой ленточный символ сканируется. Таким же образом мысталкиваемся с огромными множествами состояний, и компьютер, который имитирует M′, должен монтировать и демонтировать несколько дисков, решая, каким же является и каким будет следующее состояние M′. Естественно, о компьютерах, решающих задачи подобного рода, никто и не задумывается, поэтому обычные операционные системы не имеют поддержки для таких задач.
Однако при желании мы могли бызапрограммировать “голый”, лишенный операционной системы компьютер, снабдивего соответствующими возможностями.8.6. ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ È ÊÎÌÏÜÞÒÅÐÛСтр. 367367К счастью, вопрос о том, как имитировать МТ с огромным числом состояний илиленточных символов, разрешим. В разделе 9.2.3 будет показано, что можно построить МТ, которая по существу есть МТ с “запоминаемой программой”. Эта МТ, называемая “универсальной”, считывает функцию переходов любой МТ, закодированнуюв двоичном виде на ленте, и имитирует ее.
Универсальная МТ имеет вполне разумноечисло состояний и ленточных символов. С помощью имитации универсальной МТобычный компьютер может быть запрограммирован для допускания какого угоднорекурсивно перечислимого языка без необходимости имитировать количества состояний, которые нарушают пределы того, что может быть записано на диске.Приведем реалистичную, хотя и неформальную, модель функционирования обычногокомпьютера.1.Предполагается, что память компьютера состоит из неопределенно длинной последовательности слов, каждое из которых имеет адрес. В реальном компьютере словабыли бы длиной 32 или 64 бит, но мы длину слова ограничивать не будем.
В качестве адресов используются целые 0, 1, 2 и т.д. В реальном компьютере последовательными целыми нумеровались бы отдельные байты, поэтому адреса слов были быкратны 4 или 8, но это различие несущественно. В реальном компьютере количествослов “памяти” также было бы ограничено, но мы хотим учесть содержимое произвольного числа дисков или других запоминающих устройств, поэтому предполагаем,что количество слов ничем не ограничено.2.Предполагается, что программа компьютера записывается в некоторые слова памяти. Каждое из этих слов представляет простую инструкцию, как в машинном или ассемблерном языке обычного компьютера.
Примерами служат инструкции перемещения данных из одного слова в другое или прибавления одного слова к другому.Допускается “непрямая адресация”, т.е. инструкция может ссылаться на другое слово и использовать его содержимое в качестве адреса слова, к которому применяетсяоперация. Эта возможность, обычная для современных компьютеров, нужна длядоступа к массивам, для следования по связям списков и вообще для выполненияопераций с указателями.3.Предполагается, что каждая инструкция использует ограниченное (конечное) числослов и изменяет значение не более одного слова.4.Обычный компьютер имеет регистры — слова памяти с особо быстрым доступом.Часто такие операции, как сложение, применяются только к регистрам, но мы подобные ограничения не вводим и считаем, что с любым словом можно произвестилюбую операцию.
Относительная скорость операций на различных словах значенияне имеет, поскольку вообще не нужна при сравнении возможностей компьютеров имашин Тьюринга по распознаванию языков. Даже если нас интересует полиноми-368Стр. 368ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀальная связь между временами работы, разница в скорости доступа к различнымсловам остается неважной, поскольку влияет “лишь” на константный сомножитель.Возможная конструкция машины Тьюринга для имитации компьютера представленана рис. 8.22.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
