Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 83
Текст из файла (страница 83)
СЗ Теорема 8.15. Каждый рекурсивно перечислимый язык допускается двухсчетчиковой машиной. Доказательство. С учетом прелыдущей теоремы нужно лишь показать, как имитировать три счетчика с помощью двух. Идея состоит в том, чтобы представить три счетчика, скажем, 1, ! и !г, одним целым числом. Этим числом б>дет т = 2'3'5". Од><н счетчик будет хранить это число, а второй использоваться в качестве вспомогательного для умножения и деления и на одно из трех простых чисел 2, 3 или 5.
Для имитации трехсчетчиковой машины нужно реализовать следующие операции. !. Увеличиты, / и/или lс Для того чтобы увеличить! на 1, нужно умножить ш на 2. В теореме 8.14 уже показано, как умножить содержимое счетчика на константу г, используя второй счетчик. Аналогично ! увеличивается путем > множения гл на 3, а !г — на 5. 8.5. МАШИНЫ ТЬЮРИНГА С ОГРАНИЧЕНИЯМИ ЗбЗ 3.
Уменьшить Еу и/нли 1;. Длй этого т делится на 2, 3 или 5, соответственно. В доказательстве теоремы 8.14 описано, как выполнить деление на любую константу с использованием дополнительного счетчика. Трехсчетчиковая машина не может уменьшить число О (это ошибка, вед>'щая к останову без допускания), поэтому если ~л не делится нацело на соответствующую константу, то имитирующая двухсчетчи- ковая машина также останавливается без допускания. 8.5.5. Упражнения к разделу 8.5 Неформально, но четко и ясно опишите счетчиковые машины, которые допус- кают следующие языки.
В каждом случае используйте как можно меньше счет- чиков, но не более двух: 8.5.1. а) (я) ! О" 1 ~ и й т й 1); б) ! О" 1 ~ 1 < л < и); в) (я!) (а'угс" )! =у или г' = Е); г) (! !) ! аоус" ~ г = У или ! =- lг или / =- 8) . (!!) Цель этого упражнения — показать, что мощность односчетчиковых машин с маркером конца входа не превосходит мощности детерминированных МП- автоматов. Е8 — это конкатенация языка Е с языком, содержащим одну- единственную цепочку 5, т.е. Е5 состоит из всех строк и 8, где ж принадлежит Е. Покажите, что если язык Еб допускается ДМП-автоматом, где 8 — концевой маркер, не встречающийся в цепочках из Е, то Е также допускается некоторым ДМП-автоматом.
Указание. Этот вопрос совпадает с вопросом замкнутости языков, доп>скаемых ДМП-автоматами, относительно операции ЕУа, определенной в упражнении 4.2.2. Нужно модифицировать ДМП-автомат Р для Е5 путем замены каждого из его магазинных символов Х всеми возможными парами 1Х, 5), где Я есть множество состояний.
Если Р имеет магазин ХХл ..Х„, то построенный для 1. ДМП-автомат имеет магазин (Хь Я~)(Хл Яэ)...(Х„, Я„), где каждое 5, есть множество состояний у, в которых Р, начав с МО (у, а, ХХ,.ь ..Х„), 8.5.2. допускает. 364 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 2. Различить, какие из чисел, Е у или й, равны О. Для того чтобы выяснить, что 1= О, нужно определить, делится ли л~ без остатка на 2. Число т копируется во второй счетчик с использованием состояния машины, чтобы запомнить, уменьшено гл четное или нечетное число раз.
Если ш уменьшено нечетное число раз к тому моменту, когда оно стало равно О, то 1 = О. В таком случае гл копируется из второго счетчика в первый. Аналогично, равенство)'= О проверяется путем определения, делится ли ш на 3, а Уг = Π— делится ли оно на 5. 8.6. Машины Тьюринга и компьютеры Теперь сравним машины Тьюринга с обычным компьютером. Эти модели кажутся совершенно разными, но они допускают одни и те же языки — рекурсивно перечислимые. Поскольку понятие "обычный компьютер" математически не определено, аргументация данного раздела не является формальной.
Нам приходится обращаться к интуиции читателя по поволу того, что могут компьютеры, в частности, если рассматриваемые числа превосходят обычные пределы, обусловленные, архитектурой компьютеров (например, 32-битовым представлением чисел). Утверждения данного раздела можно разделить на две части. 1. Компьютер может имитировать машину Тьюринга.
2. Машина Тьюринга может имитировать компьютер, причем за время, которое можно выразить в виде некоторого полинома от числа шагов, совершаемых ьом пьютером. 8.6.1. Имитация машины Тьюринга на компьютере Вначале посмотрим, как компьютер имитирует машину Тьюринга. Имея некоторую конкретную машину Тьюринга М, мы должны написать программу, которая работает, как М. Одним из составляющих М является ее конечное управление.
Поскольку М имеет только конечное число состояний и конечное число правил перехола, наша программа может закодировать состояния в виде цепочек символов и использовать таблицу переходов, которую она просматривае~ для определения каждого перехода. Аналогично, ленточные символы можно закодировать в виде цепочек символов фиксированной длины, поскольку ленточных символов также конечное число. Серьезный вопрос возникает, когла мы решаем, как программа должна имитировать ленту машины Тьюринга.
Эта лента может стать бесконечно длинной, но память компьютера — главная память, диск или другие устройства — конечна. Можно ли проимитировать бесконечную ленту с помощью фиксированного объема памяти? Если у нас нет возможности заменять запоминающие устройства, то проимитировать действительно нельзя; в таком случае компьютер был бы конечным автоматом. н допускал бы золько регулярные языки. Однако обычные компьютеры имеют заменяемые запоминающие устройства, например, "21р"-диски. В действительности обычный жесткий диск можно снять и заменить пустым, но идентичным диском.
Поскольку очевидного предела на количество используемых дисков нет, будем считать, что доступны столько дисков, сколько может потребоваться компьютеру. Тогда зти диски можно разместить в двух магазинах (рис. 8.2!). Один магазин содержит данные в удаленных клетках ленты машины Тьюринга, расположенных слева от ее головки, а другой — в дальних клетках справа от головки.
Чем дальше в магазине расположены дан- ные, тем дальше они от головки на ленте, 366 8.6. МАШИНЫ ТЬЮРИНГА И КОМПЬЮТЕРЫ Лента слева от головки Лента справа от головки Рис 82/ Иииюаггил машины Тьюринга ни обычном комньююере Если ленточная головка МТ сдвигается далеко влево и достигает клеток, не представленных в текущем смонтированном диске, то программа печатает сообщение "обмен слева".
Смонтированный диск снимается человеком-оператором и помещается на вершину правого магазина. На компьютер монтируется диск с вершины левого магазина, и вычисления продолжаются, Аналогично, если ленточная головка МТ достигает удаленных клеток, не представленных на текущем смонтированном диске, то печатается сообщение "обмен справа". Человек перемещает текущий диск на вершину левого магазина и монтирует на компьютер диск с вершины правого магазина. Ситуация, когда какой-либо магазин пуст, а компьютер требует, чтобы диск из него был смонтирован, означает, что МТ достигла области пробелов на ленте. В этом случае оператору придется купить новый диск и смонтировать его.
8.6.2, Имитация компьютера на машине Тьюринга Нужно также провести обратное сравнение: существую~ ли вещи, которые может сделать обычный компьютер, а машина Тьюринга — нет. Важным вторичным вопросом является вопрос, может ли компьютер делать определенные вещи существенно быстрее, чем машина Тьюринга. В этом разделе обосновывается, что МТ может имитировать компьютер, а в разделе 8.6,3 — что эта имитация может быть достаточно быстрой в том смысле, что "всего лишь" полиномиальная зависимость разделяет время работы компьютера и МТ для решения какой-либо проблемы.
Напомним читателю еще раз, что существуют немаловажные причины считать подобными все времена работы, лежащие в пределах полиномиальной зависимости друг от друга, тогда как экспоненциальные отличия 366 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА во времени работы "слишком велики". Теория, в которой проводится сравнение полино- виыьного и экспоненциального времени работы, будет рассмотрена в главе 1О. Проблема очень больших ленточных алфавитов Доводы раздела 8.6.1 становятся сомнительными, если число ленточных символов настолько велико, что код одного ленточного символа не у14гещается на диске.
Для этого нужно действительно очень много ленточных символов, поскольку 30-гигабайтный диск, например, может представить любой из 2 ~ символов. Аналогично, чисэ 040000000000 по состояний могло бы быть настолько большим, что состояние нельзя было представить, используя целый диск. Для одного из разрешений этой проблемы следует ограничить число ленточных символов, используемых МТ. Любой ленточный алфавит можно закодировать в двоичном виде.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
