dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 78
Текст из файла (страница 78)
Постарайтесь самипредставить подходящую запись МО (конфигураций) многоленточных МТ; формальноона здесь также не приводится. Многоленточные МТ, как и одноленточные, допускают,попадая в допускающее состояние.8.4.2. Ýêâèâàëåíòíîñòü îäíîëåíòî÷íûõ è ìíîãîëåíòî÷íûõìàøèí ÒüþðèíãàНапомним, что рекурсивно перечислимые языки определяются как языки, допускаемые одноленточными МТ.
Очевидно, что многоленточные МТ допускают все рекурсивно перечислимые языки, поскольку одноленточная МТ является частным случаем многоленточной. Но существуют ли не рекурсивно перечислимые языки, допускаемые многоленточными МТ? Ответом является “нет”, и мы докажем это, показав, как многоленточная МТ имитируется с помощью одноленточной.Теорема 8.9. Каждый язык, допускаемый многоленточной МТ, рекурсивно перечислим.Доказательство. Идею доказательства иллюстрирует рис. 8.17. Предположим, чтоязык L допускается k-ленточной МТ M. Она имитируется с помощью одноленточной МТN, лента которой состоит из 2k дорожек. Половина этих дорожек содержит ленты машины M, а каждая из дорожек второй половины содержит один-единственный маркер, указывающий позицию, в которой в данный момент времени находится головка соответствующей ленты.
Рис. 8.17 соответствует тому, что k = 2. Вторая и четвертая дорожки хранят содержимое первой и второй лент машины M, дорожка 1 хранит позицию головки наленте 1, а дорожка 3 — позицию на ленте 2.Для имитации перехода МТ M головка МТ N должна посетить k головочных маркеров. Чтобы не “заблудиться”, N должна помнить, сколько маркеров находятся слева от ееголовки каждый раз; этот учет ведется с помощью компонента конечного управления N.После посещения каждого головочного маркера и запоминания обозреваемого символа вкомпоненте управления N знает, какие символы обозреваются каждой из головок M.
Nтакже знает состояние M, которое запоминается в конечном управлении N. Таким образом, N знает, какой переход сделает M.Теперь N еще раз посещает каждый из головочных маркеров на своей ленте, изменяетсимвол в дорожке, представляющей соответствующую ленту, и при необходимости пе348Стр. 348ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀремещает головочные маркеры влево или вправо. Наконец, N изменяет состояние M, записанное в конечном управлении N. В этот момент N проимитировала один переход M.Рис. 8.17. Имитация двухленточной МТ с помощью одноленточнойВ качестве допускающих состояний N выбираются все те ее состояния, в которых запомнено допускающее состояние M.
Таким образом, как только имитируемая M допускает, N также допускает, и не допускает в противном случае. Íàïîìèíàíèå î êîíå÷íîñòèОбычное заблуждение — путать значение, конечное в каждый момент времени, с конечным множеством значений. Конструкция сведения многих лент к одной помогает оценитьразницу между этими “конечностями”. В данной конструкции использованы дорожки наленте для запоминания позиций ленточных головок. Почему нельзя записать эти позиции в виде целых чисел в конечное управление? Будучи небрежным, кто-то мог бы утверждать, что после n переходов головки МТ находятся в позициях, отличающихся неболее, чем на n от начальной, и поэтому достаточно записать целые не больше n.Проблема состоит в том, что, хотя позиции конечны в каждый момент времени, всемножество позиций может быть и бесконечным.
Если состояние должно представлятьлюбую позицию головки, то в состоянии должен быть компонент данных, имеющийлюбое целое в качестве значения. Из-за этого компонента множество состоянийдолжно быть бесконечным, даже если только конечное число состояний используетсяв любой конечный момент времени. Определение же машин Тьюринга требует, чтобы множество состояний было конечным.
Таким образом, запомнить позицию ленточной головки в конечном управлении нельзя.8.4. ÐÀÑØÈÐÅÍÈß ÁÀÇÎÂÎÉ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀСтр. 3493498.4.3. Âðåìÿ ðàáîòû è êîíñòðóêöèÿ “ìíîãî ëåíò ê îäíîé”Здесь представлено понятие, которое в дальнейшем окажется чрезвычайно важным, аименно: “временная сложность”, или “время работы” машины Тьюринга. Временем работы машины Тьюринга на входе w называется число шагов, которые M совершает доостанова. Если M не останавливается на w, то время работы бесконечно. Временнаясложность МТ M есть функция T(n), которая представляет собой максимум времени работы M на w по всем входам w длины n.
Для МТ, не останавливающихся на всех своихвходах, T(n) может быть бесконечным для некоторых или даже для всех n. Однако особое внимание будет уделено машинам Тьюринга, которые обязательно останавливаютсяна всех своих входах, и в частности, тем машинам, которые имеют полиномиальнуювременную сложность.
Они будут изучаться, начиная с раздела 10.1.Конструкция теоремы 8.9 кажется неуклюжей. Действительно, построенной одноленточной МТ может понадобится гораздо больше времени для работы, чем многоленточной. Однако время работы этих двух машин соразмерно в том смысле, что время работы одноленточной МТ есть не более чем квадрат времени работы многоленточной. Хотя “возведение в квадрат” не является хорошей соразмерностью, оносохраняет свойство времени работы быть полиномиальным.
В главе 10 будут представлены следующие факты.1.Разница между полиномиальным временем и более высокими степенями его возрастания — это в действительности граница между тем, что можно решить с помощьюкомпьютера, и тем, что практически нерешаемо.2.Несмотря на обширные исследования, время, необходимое для решения многихпроблем, не удается определить точнее, чем “некоторое полиномиальное”. Такимобразом, когда изучается время, необходимое для решения некоторой проблемы, использование многоленточной или одноленточной МТ не является критичным.Докажем, что время работы многоленточной МТ является не более чем квадратомвремени работы одноленточной МТ.Теорема 8.10. Время, необходимое одноленточной МТ N для имитации n переходовk-ленточной МТ M, есть O(n2).Доказательство. После n переходов машины M головочные маркеры не могутбыть разделены более, чем 2n клетками. Таким образом, если N стартует на крайнемслева маркере, ей нужно сдвинуться не более, чем на 2n клеток вправо, чтобы найтивсе головочные маркеры.
Затем ей нужно совершить проход влево, изменяя содержимое лент M и сдвигая головочные маркеры вправо или влево, если необходимо. Выполнение этого требует не более 2n сдвигов влево, плюс не более 2k переходов дляизменения направления движения и записи маркера X в клетку справа (когда головкаM сдвигается вправо).350Стр. 350ÃËÀÂÀ 8.
ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀТаким образом, число переходов N, необходимых для имитации одного из первых nпереходов, не более 4n + 2k. Поскольку k — константа, не зависящая от числа имитируемых переходов, это чиñло переходов есть O(n). Имитация n переходов требует временине более, чем в n раз больше, т.е. O(n2).8.4.4. Íåäåòåðìèíèðîâàííûå ìàøèíû ÒüþðèíãàНедетерминированная машина Тьюринга (НМТ) отличается от изученных нами детерминированных тем, что ее δ(q, X) для каждого состояния q и ленточного символа Xпредставляет собой множество троек{(q1, Y1, D1), (q2, Y2, D2), …, (qk, Yk, Dk)},где k — натуральное число.
НМТ может выбирать на каждом шаге любую из троек дляследующего перехода. Она не может, однако, выбрать состояние из одной тройки, ленточный символ из другой, а направление из какой-нибудь еще.Язык, допускаемый НМТ M, определяется по аналогии с другими недетерминированнымиустройствами, вроде НКА или МП-автоматов.
Таким образом, M допускает вход w, если существует некоторая последовательность выборов переходов, ведущая из начального МО с wна входе в МО с допускающим состоянием. Существование других выборов, которые не ведут в допускающее состояние, не имеет значения, как и для НКА или МП-автоматов.Недетерминированные МТ допускают те же языки, что и детерминированные (илиДМТ, если нам нужно подчеркнуть их детерминированность).
Доказательство основано натом, что для любой НМТ MN можно построить ДМТ MD, которая исследует конфигурации,достигаемые MN с помощью любой последовательности переходов. Если MD находит хотябы одно МО с допускающим состоянием, то сама переходит в допускающее состояние. MDдолжна помещать новые МО в очередь, а не в магазин, чтобы после некоторого конечноговремени были проимитированы все последовательности длиной до k (k = 1, 2, …).Теорема 8.11. Если MN — недетерминированная машина Тьюринга, то существуетдетерминированная машина Тьюринга MD, у которой L(MD) = L(MN).Доказательство.
Построим MD в виде многоленточной МТ, общий вид которойпредставлен на рис. 8.18. Первая лента MD хранит последовательность МО MN, включаясостояние MN. Одно МО MN отмечено как “текущее”; следующие за ним МО должныбыть исследованы после него. На рис. 8.18 третье МО отмечено символом x вместе сразделителем МО — символом *. Все МО слева от текущего уже исследованы, и в дальнейшем их можно игнорировать.Для обработки текущего МО машина MD совершает следующие действия.1.MD проверяет состояние и обозреваемый символ текущего МО.
Информация о том,какие выборы перехода есть у MN для каждого состояния и символа, хранится в конечном управлении MD. Если состояние в текущем МО является допускающим, тоMD допускает и прекращает имитацию.8.4. ÐÀÑØÈÐÅÍÈß ÁÀÇÎÂÎÉ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀСтр. 3513512.Если состояние в текущем МО не допускающее, а пара состояние-символ имеет kпереходов, то MD использует свою вторую ленту для копирования МО и создания kкопий этого МО в конце очереди МО на ленте 1.3.MD изменяет каждое из этих k МО в соответствии с k различными выборами переходов, которые есть у MN из текущего МО.4.MD возвращается к отмеченному (текущему) МО, удаляет отметку и перемещает еена следующее МО справа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
