dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 87
Текст из файла (страница 87)
Пусть L = L (M1) и__L = L(M2). Параллельная работа машин имитируется МТ M. Чтобы эта модель сталапростой и очевидной, можно взять МТ с двумя лентами и затем преобразовать ее в одноленточную. Одна из них имитирует ленту M1, а вторая — ленту M2. Состояния M1 и M2являются компонентами состояния M.Если вход w машины M принадлежит L, то M1 в конце концов попадает в допускающее состояние; тогда M допускает и останавливается. Когда же в допускающее со9.2. ÍÅÐÀÇÐÅØÈÌÀß ÐÏ-ÏÐÎÁËÅÌÀСтр. 385385стояние попадает M2, M останавливается, не допуская.
Таким образом, M останавливается при любом входе, и L(M) — это в точности L. Отсюда заключаем, что язык L —рекурсивный. ДопуститьДопуститьДопуститьОтвергнутьРис. 9.4. Моделирование двух МТ, одна из которых допускаетнекоторый язык, а вторая — его дополнениеТеоремы 9.3 и 9.4 можно объединить следующим образом. Из девяти способов рас__положения языка L и его дополнения L (см. диаграмму на рис.
9.2) возможны лишь следующие четыре2.__1.Оба языка L и L рекурсивны, т.е. оба они находятся во внутреннем кольце.2.Ни L, ни L не являются РП, т.е. оба они находятся во внешнем кольце.3.L является РП, но не рекурсивным, и L не является РП, т.е. один находится в среднем кольце, а другой — во внешнем.________L является РП, но не рекурсивным, и L не является РП, т.е. L и L меняются местами по отношению к случаю 3.4.В качестве доказательстваотметим, что теорема 9.3 исключает возможность того, что__один из языков (L или L ) является рекурсивным, а второй принадлежит какому-либо изоставшихся классов.
При этом теорема 9.4 исключает возможность того, что оба языкаявляются РП, но не рекурсивными.Пример9.5. Рассмотрим язык Ld, который, __как мы знаем, не является РП. Поэтому__язык L d не может быть рекурсивным. Однако L d может быть либо не-РП, либо РП, ноне рекурсивным.На самом деле верно последнее.__L d есть множество цепочек wi, допускаемых соответствующими Mi. Этот язык похож на универсальный язык Lu, состоящий из всех пар (M, w), где M допускает w, который,как мы покажем в разделе 9.2.3, является РП.
Точно так же можно показать,__что L d является РП. 2386Стр. 386По существу, их всего три. — Прим. ред.ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜ9.2.3. Óíèâåðñàëüíûé ÿçûêВ разделе 8.6.2 уже неформально обсуждалось, как можно использовать машинуТьюринга в качестве модели компьютера с загруженной в него произвольной программой.
Иными словами, отдельно взятая МТ может использоваться как “компьютер с записанной программой”, который считывает свою программу и данные с одной или нескольких лент, содержащих входную информацию. В данном разделе будет формализована идея того, что машина Тьюринга является представлением программы, записаннойв память компьютера.Универсальный язык Lu определяется как множество двоичных цепочек, которые являются кодами (в смысле определения из раздела 9.1.2) пар (M, w), где M — МТ с двоичным входным алфавитом, а w — цепочка из (0+1)*, принадлежащая L(M). Таким образом, Lu — это множество цепочек, представляющих некоторую МТ и допускаемый еювход. Покажем, что существует МТ U, которую часто называют универсальной машинойТьюринга, для которой Lu = L(U).
Поскольку входом U является двоичная цепочка, то вдействительности U — это некоторая Mj в списке машин Тьюринга с двоичным входом(см. раздел 9.1.2).Проще всего U описывается как многоленточная машина Тьюринга в стиле рис. 8.22.В машине U переходы M вначале хранятся на первой ленте вместе с цепочкой w.
Втораялента используется для моделирования ленты машины M, в том же формате, что и у кодаM. Таким образом, ленточный символ Xi машины M кодируется как 0i, а коды разделяются одиночными 1. На третью ленту U записывается состояние M, причем состояние qiпредставляется в виде i нулей. Схема U представлена на рис. 9.5.КонечноеуправлениеВходЛентаСостояние00010000010100010000Рабочая лентаРис. 9.5. Структура универсальной машины Тьюринга9.2. ÍÅÐÀÇÐÅØÈÌÀß ÐÏ-ÏÐÎÁËÅÌÀСтр. 387387Машина U производит следующие операции.1.Исследует вход для того, чтобы убедиться, что код M является правильным кодомМТ.
Если это не так, U останавливается, не допуская. Это действие корректно, поскольку неправильные коды по договоренности представляют МТ без переходов, атакие МТ не допускают никакого входа.2.Записывает на вторую ленту код входной цепочки w. Таким образом, каждому символу 0 из w на второй ленте ставится в соответствие цепочка 10, а каждой 1 — цепочка 100. Отметим, что пустые символы, которые находятся на ленте самой M ипредставляются цепочками вида 1000, на этой ленте появляться не будут.
Все клетки, кроме занятых символами цепочки w, будут заполняться пустыми символамимашины U. Но при этом U знает, что если она ищет имитируемый символ M и находит свой собственный пустой символ, то она должна заменить его последовательностью 1000, имитирующей пустой символ M.3.На третьей ленте записывает 0, т.е. начальное состояние M, и перемещает головкувторой ленты U в первую имитируемую клетку.4.Для того чтобы отобразить переход M, U отыскивает на своей первой ленте переход0i10j10k10l10m, у которого 0i есть состояние на ленте 3, а 0j — ленточный символ M,начинающийся с позиции на ленте 2, обозреваемой U. Это переход, который M совершает на следующем шаге.
Машина U должна выполнить следующие действия:а) изменить содержимое ленты 3 на 0k, т.е. отобразить изменение состояния M.Для этого U вначале заменяет все символы 0 на ленте 3 пустыми символами,а затем копирует 0k с ленты 1 на ленту 3;б) заменить 0j на ленте 2 символами 0l, т.е. поменять ленточный символ M.
Если потребуется больше или меньше места (т.е. j ≠ l), то для управления пространством используются рабочая лента и техника переноса (см. раздел 8.6.2);в) переместить головку на ленте 2 в ту позицию слева или справа, в которойнаходится ближайший символ 1. При m = 1 совершается сдвиг влево, апри m = 2 — вправо. Таким образом, U имитирует движение M влево иливправо.5.Если M не имеет перехода, соответствующего имитируемым состоянию и ленточному символу, то в п. 4 переход не будет найден. Таким образом, в данной конфигурации M останавливается, и то же самое должна делать U.6.Если M попадает в свое допускающее состояние, то U допускает.Этими действиями U имитирует работу M со входом w. U допускает закодированную пару (M, w) тогда и только тогда, когда M допускает w.388Стр.
388ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜÁîëåå ýôôåêòèâíàÿ óíèâåðñàëüíàÿ ÌÒМашина U, эффективно имитирующая M, т.е. не требующая сдвига ленточных символов, должна вначале определять число ленточных символов, используемых M. Есличисло символов лежит в пределах от 2k–1 до 2k – 1, то однозначно представить различные ленточные символы можно с помощью k-битового двоичного кода. Каждойклетке M можно поставить в соответствие k клеток машины U. Для того чтобы упростить имитацию, можно переписать в машине U данные переходы M и вместо описанного нами унарного кода переменной длины использовать бинарный код фиксированной длины.9.2.4.
Íåðàçðåøèìîñòü óíèâåðñàëüíîãî ÿçûêàПредставим проблему, которая является РП, но не рекурсивной. Это язык Lu. Неразрешимость Lu (т.е. его нерекурсивность) во многих отношениях важнее, чем наш предыдущий вывод о том, что язык Ld не является РП. Причина состоит в следующем. Сведением Lu к другой проблеме P можно показать, что алгоритма, решающего P, не существует, независимо от того, является ли P РП.
Однако сведение Ld к P возможно лишьтогда, когда P не является РП, поэтому Ld не может использоваться при доказательственеразрешимости проблем, которые являются РП, но не рекурсивными. Вместе с тем, если нужно показать, что проблема не является РП, то можно использовать только Ld, в товремя как язык Lu оказывается бесполезным, поскольку он является РП.Теорема 9.6. Lu является РП, но не рекурсивным.Доказательство.
В разделе 9.2.3__доказано, что язык Lu является РП. Допустим, что Luрекурсивен. Тогда по теореме 9.3 L u __(дополнение Lu) — также рекурсивный язык. Ноесли существует МТ M, допускающая L u, то, используя описанный ниже метод, можнопостроить МТ, допускающую Ld. Поскольку нам известно, что Ld не является РП, приходим к противоречию с предположением, что язык Lu является рекурсивным.Ïðîáëåìà îñòàíîâàПроблема останова машины Тьюринга считается подобной проблеме Lu; она такжеявляется РП, но не рекурсивной.
В действительности, определенная А. М. Тьюрингоммашина допускала, не попадая в допускающее состояние, а останавливаясь. Для МТM можно определить H(M) как множество входов w, на которых M останавливаетсянезависимо от того, допускает ли M вход w. Тогда проблема останова состоит в определении множества таких пар (M, w), у которых w принадлежит H(M). Это еще одинпример проблемы/языка, которая является РП, но не рекурсивной.__Предположим, что L(M) = L u. На рис. 9.6 показано, как можно преобразовать МТ Mв МТ M′, которая допускает Ld с помощью следующих действий.9.2. ÍÅÐÀÇÐÅØÈÌÀß ÐÏ-ÏÐÎÁËÅÌÀСтр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
