dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 88
Текст из файла (страница 88)
389389ГипотетическийалгоритмдляКопированиеДопуститьДопуститьОтвергнутьОтвергнуть__Рис. 9.6. Сведение Ld к L u1.M′ преобразует входную цепочку w в w111w. В качестве упражнения читатель можетнаписать программу для выполнения этого шага на одной ленте. Однако легче этосделать, используя для копии w вторую ленту, и затем преобразовать двухленточнуюМТ в одноленточную.2.M′ имитирует M на новом входе. Если w есть wi в нашем __перечислении, то M′ определяет, допускает ли Mi вход wi. Поскольку M допускает L u, то она допускает тогдаи только тогда, когда Mi не допускает wi, т.е. когда wi принадлежит Ld.Таким образом, M′ допускает w тогда и только тогда, когда w принадлежит Ld.
Посколькупо теореме 9.2 машины M′ не существует, приходим к выводу, что язык Lu не являетсярекурсивным. 9.2.5. Óïðàæíåíèÿ ê ðàçäåëó 9.29.2.1.Покажите, что проблема останова, т.е. проблема определения множества пар(M, w), где M останавливается (допуская или нет) на входе w, является РП, но нерекурсивной. (См. врезку “Проблема останова” в разделе 9.2.4.)9.2.2.Во врезке “Почему “рекурсивные”?” из раздела 9.2.1 говорилось о “рекурсивных функциях” как модели вычислимости, используемой наравне с машинамиТьюринга. В данном упражнении рассмотрим пример записи рекурсивныхфункций.
Рекурсивная функция — это функция F, определенная конечным набором правил. Каждое правило устанавливает значение функции F для определенных аргументов; в правиле могут присутствовать переменные, неотрицательные целочисленные константы, функция прибавления единицы (successor),сама функция F и выражения, построенные композицией перечисленных функций. Например, функция Аккермана определяется следующим образом.390Стр.
3901.A(0, y) = 1 для всех y ≥ 1.2.A(1, 0) = 2.3.A(x, 0) = x + 2 для x ≥ 2.4.A(x + 1, y + 1) = A(A(x, y + 1), y) для любых x ≥ 0 и y ≥ 0.ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜВыполните следующее:а) (∗) вычислите A(2, 1);б) (!) опишите A(x, 2) как функцию от x;в) (!) вычислите A(4, 3).9.2.3.Опишите неформально многоленточные машины Тьюринга, которые перечисляют следующие множества целых чисел в том смысле, что, начав с пустыхлент, они печатают на одной из лент цепочкумножество {i1, i2, …}:10 i110 i2 1... , представляющуюа) (∗) множество квадратов целых чисел {1, 4, 9, …};б) множество простых чисел {2, 3, 5, 7, 11, …};в) (!!) множество всех таких i, для которых Mi допускает wi.
Указание. Такие iневозможно генерировать в порядкевозрастания. Причина состоит в том,__что данный язык, который есть L d, является РП, но не рекурсивным. Такиеязыки по определению можно перечислить, но не в порядке возрастания.“Прием” с их перечислением состоит в том, чтобы смоделировать работувсех Mi со входами wi. При этом мы не можем позволить какой-либо Mi работать вечно, поскольку это помешает продолжать проверку для других Mj, гдеi ≠ j.
Поэтому мы вынуждены работать поэтапно, проверяя на k-м этапе лишьконечное множество машин Mi и ограничивая проверку каждой машины конечным числом шагов. Таким образом, каждый этап проверки будет выполнен за конечное время. Поскольку для всякой МТ Mi и всякого числа шагов sнайдется такой этап, на котором будет промоделировано не менее s шаговMi, то в конце концов мы обнаружим все Mi, допускающие wi, и перечислимномера i.9.2.4.(∗) Пусть L1, L2, …, Lk — набор языков в алфавите Σ, для которого верны следующие утверждения.1.Li I Lj ≠ ∅ для всех i ≠ j, т.е.
никакая цепочка не принадлежит сразудвум языкам.2.L1 U L2 U L U Lk = Σ*, т.е. каждая цепочка принадлежит одному из этих языков.3.Все языки Li, где i = 1, 2, …, k, рекурсивно перечислимы.Докажите, что тогда каждый из этих языков рекурсивен.__9.2.5.(∗!) Пусть L рекурсивно перечислим и L не является РП. Рассмотрим языкL′ = {0w | w принадлежит L} U {1w | w не принадлежит L}.Можете ли вы наверняка сказать, что язык L′ или его дополнение являются рекурсивными, РП или не-РП? Ответ обоснуйте.9.2. ÍÅÐÀÇÐÅØÈÌÀß ÐÏ-ÏÐÎÁËÅÌÀСтр.
3913919.2.6.(!) За исключением операции дополнения в разделе 9.2.2, свойства замкнутостирекурсивных и РП-языков пока не обсуждались. Выясните, замкнуты ли рекурсивные и/или РП-языки относительно перечисленных ниже операций:а) (∗) объединение;б) пересечение;в) конкатенация;г) замыкание Клини (звездочка);д) (∗) гомоморфизм;е) обратный гомоморфизм.Обосновывая замкнутость, можно использовать неформальные, но достаточнопонятные конструкции.9.3.
Íåðàçðåøèìûå ïðîáëåìû, ñâÿçàííûåñ ìàøèíàìè ÒüþðèíãàСтатус языков Lu и Ld относительно неразрешимости и рекурсивной перечислимости нам уже известен. Используем их для демонстрации других неразрешимых или неРП-языков. В доказательствах используется техника сведения. Все неразрешимыепроблемы, которые рассматриваются вначале, связаны с машинами Тьюринга. Кульминацией данного раздела является доказательство “теоремы Райса”. В ней утверждается, что любое нетривиальное свойство МТ, зависящее лишь от языка, допускаемогомашиной Тьюринга, должно быть неразрешимым. Материал раздела 9.4 позволяет исследовать некоторые неразрешимые проблемы, не связанные ни с машинами Тьюринга, ни с их языками.9.3.1. CâåäåíèÿПонятие сведения было введено в разделе 8.1.3.
В общем случае, если у нас есть алгоритм, преобразующий экземпляры проблемы P1 в экземпляры проблемы P2, которыеимеют тот же ответ (да/нет), то говорят, что P1 сводится к P2. Доказательство такой сводимости используется, чтобы показать, что P2 не менее трудна, чем P1. Таким образом,если P1 не является рекурсивной, то и P2 не может быть рекурсивной. Если P1 не является РП, то и P2 не может быть РП. Как уже упоминалось в разделе 8.1.3, чтобы доказать,что проблема P2 не менее трудна, чем некоторая известная P1, нужно свести P1 к P2, а ненаоборот.Как показано на рис.
9.7, сведение должно переводить всякий экземпляр P1 с ответом“да” (позитивный) в экземпляр P2 с ответом “да”, и всякий экземпляр P1 с ответом “нет”(негативный) — в экземпляр P2 с ответом “нет”. Отметим, что неважно, является ли каж392Стр. 392ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜдый экземпляр P2 образом одного или нескольких экземпляров P1. В действительности,обычно лишь небольшая часть экземпляров P2 образуется в результате сведения.ДаДаНетНетРис. 9.7. Сведение переводит позитивные экземпляры в позитивные,а негативные — в негативныеФормально сведение P1 к P2 является машиной Тьюринга, которая начинает работу сэкземпляром проблемы P1 на ленте и останавливается, имея на ленте экземпляр проблемы P2. Как правило, сведения описываются так, как если бы они были компьютернымипрограммами, которые на вход получают экземпляры P1 и выдают экземпляры P2.
Эквивалентность машин Тьюринга и компьютерных программ позволяет описывать сведениев терминах как тех, так и других. Значимость процедуры сведения подчеркивается следующей широко используемой теоремой.Теорема 9.7. Если P1 можно свести к P2, то:а) если P1 неразрешима, то и P2 неразрешима;б) если P1 не-РП, то P2 также не-РП.Доказательство. Предположим сначала, что проблема P1 неразрешима. Если решитьP2 возможно, то, объединяя сведение P1 к P2 и алгоритм решения последней, можно построить алгоритм, решающий P1.
Эта идея была проиллюстрирована на рис. 8.7. Поясним подробнее. Пусть дан экземпляр w проблемы P1. Применим к нему алгоритм, который переводит w в экземпляр x проблемы P2. Затем применим к x алгоритм, решающийP2. Если алгоритм выдает ответ “да”, то x принадлежит P2. Поскольку P1 была сведена кP2, то известен ответ “да” для P1 на w, т.е. w принадлежит P1. Точно так же, если x непринадлежит P2, то и w не принадлежит P1.
Итак, ответ на вопрос “x принадлежит P2?”является также правильным ответом на вопрос “w принадлежит P1?”.Таким образом, получено противоречие с предположением, что проблема P1 неразрешима. Делаем вывод, что если P1 неразрешима, то и P2 неразрешима.Рассмотрим теперь часть б.
Предположим, что P2 (в отличие от P1) является РП. Вданном случае у нас есть алгоритм сведения P1 к P2, но для P2 существует лишь процедура распознавания, т.е. МТ, которая дает ответ “да”, когда ее вход принадлежит P2, и мо9.3. ÍÅÐÀÇÐÅØÈÌÛÅ ÏÐÎÁËÅÌÛ, ÑÂßÇÀÍÍÛÅ Ñ ÌÀØÈÍÀÌÈ ÒÜÞÐÈÍÃÀСтр. 393393жет работать бесконечно, когда вход не принадлежит P2. Как и в части а, с помощью алгоритма сведения преобразуем экземпляр w проблемы P1 в экземпляр x проблемы P2. Затем применим к x МТ для P2.
Если x допускается, то допустим и w.Эта процедура описывает МТ (возможно, работающую бесконечно), языком которой является P1. Если w принадлежит P1, то x принадлежит P2, и поэтому данная МТдопускает w. Если же w не принадлежит P1, то x не принадлежит P2. Тогда МТ можетили остановиться, или работать бесконечно, но в обоих случаях она не допустит w.Поскольку по предположению МТ, распознающей P1, не существует, то полученноепротиворечие доказывает, что МТ для P2 также не существует. Таким образом, если P1не-РП, то и P2 не-РП. 9.3.2.
Ìàøèíû Òüþðèíãà, äîïóñêàþùèå ïóñòîé ÿçûêВ качестве примера сведения, связанного с машинами Тьюринга, исследуем языки,известные как Le и Lne. Оба они состоят из двоичных цепочек. Если w — двоичная цепочка, то она представляет некоторую МТ Mi из перечисления, описанного в разделе 9.1.2.Если Mi = ∅, т.е. Mi не допускает никакого входа, то Mi принадлежит Le. Таким образом, Le состоит из кодов всех МТ, языки которых пусты. С другой стороны, если L(Mi) непуст, то w принадлежит Lne. Таким образом, Lne состоит из кодов всех машин Тьюринга,которые допускают хотя бы одну цепочку.В дальнейшем нам будет удобно рассматривать цепочки как машины Тьюринга,представленные этими цепочками. Итак, упомянутые языки определяются следующимобразом.• Le = {M | L(M) = ∅}• Lne = {M | L(M) ≠ ∅}Отметим, что Le и Lne — языки над алфавитом {0, 1}, дополняющие друг друга.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
