dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 89
Текст из файла (страница 89)
Какбудет видно, Lne является “более легким”. Он РП, но не рекурсивный, в то время какLe — не-РП.Теорема 9.8. Язык Lne рекурсивно перечислим.Доказательство. Достаточно предъявить МТ, допускающую Lne. Проще всего этосделать, описав недетерминированную МТ M, которая схематично изображена нарис. 9.8. Согласно теореме 8.11 M можно преобразовать в детерминированную МТ.УгадываемаяДопуститьДопуститьРис.
9.8. Конструкция НМТ, допускающей язык Lne394Стр. 394ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜРабота M заключается в следующем.1.На вход M подается код МТ Mi.2.Используя недетерминизм, M угадывает вход w, который, возможно, допускается Mi.3.M проверяет, допускает ли Mi свой вход w. В этой части M может моделировать работу универсальной МТ U, допускающей Lu.4.Если Mi допускает w, то и M допускает свой вход, т.е.
Mi.Таким образом, если Mi допускает хотя бы одну цепочку, то M угадает ее (среди прочих,конечно) и допустит Mi. Если же L(Mi) = ∅, то ни одна из угаданных w не допускаетсяMi, и M не допустит Mi. Таким образом, L(M) = Lne. Следующим шагом будет доказательство, что язык Lne не является рекурсивным. Дляэтого сведем к Lne язык Lu, т.е.
опишем алгоритм, который преобразует вход (M, w) в выход M′ — код еще одной машины Тьюринга, для которой w принадлежит L(M) тогда итолько тогда, когда язык L(M′) не пуст. Таким образом, M допускает w тогда и только тогда, когда M′ допускает хотя бы одну цепочку. Прием состоит в том, что M′ игнорируетсвой вход, а вместо этого моделирует работу M на w.
Если M допускает w, то M′ допускает свой собственный вход. Таким образом, L(M′) не пуст тогда и только тогда, когда Mдопускает w. Если бы Lne был рекурсивным, то у нас был бы алгоритм выяснения, допускает ли M вход w: построить M′ и проверить, будет ли L(M′) = ∅.Теорема 9.9. Язык Lne не является рекурсивным.Доказательство. Уточним доказательство, кратко описанное выше. Нужно построить алгоритм, который преобразует свой вход — двоичный код пары (M, w) — в МТ M′,для которой L(M′) ≠ ∅ тогда и только тогда, когда M допускает вход w.
Данная конструкция схематично представлена на рис. 9.9. Как будет показано, если M не допускает w,то M′ не допускает никакого входа, т.е. L(M′) = ∅. Но если M допускает w, то M′ допускает любой вход, и поэтому, конечно же, L(M′) ≠ ∅.ДопуститьДопуститьРис. 9.9. Схема МТ M′, построенной по (M, w) в теореме 9.9; M′ допускаетпроизвольный вход тогда и только тогда, когда M допускает wM′ по построению выполняет следующие действия.1.M′ игнорирует собственный вход.
Она заменяет его цепочкой, представляющей МТM и ее вход w. Поскольку M′ строится для конкретной пары (M, w), имеющей неко-9.3. ÍÅÐÀÇÐÅØÈÌÛÅ ÏÐÎÁËÅÌÛ, ÑÂßÇÀÍÍÛÅ Ñ ÌÀØÈÍÀÌÈ ÒÜÞÐÈÍÃÀСтр. 395395торую длину n, можно построить M′ с состояниями q0, q1, …, qn (q0 — начальное состояние), причем:а) в состоянии qi, i = 0, 1, …, n – 1, M′ записывает (i + 1)-й бит кода (M, w), переходит в состояние qi+1 и сдвигается вправо;б) в состоянии qn в случае необходимости M′ сдвигается вправо и заполняет всенепустые клетки (содержащие “хвост” цепочки x, если ее длина больше n)пробелами.2.
Когда M′ достигает пробела в состоянии qn, она, используя похожий набор состояний, перемещает головку в левый конец ленты.3. M′, используя дополнительные состояния, моделирует универсальную МТ U на полученной ленте.4. Если U допускает, то и M′ допускает. Если U никогда не допускает, то и M′ никогдане допускает.Приведенное описание M′ показывает возможность построения машины Тьюринга, которая переводит код M и цепочки w в код M′. Таким образом, существует алгоритм сведенияLu к Lne. Кроме того, если M допускает w, то M′ допускает любой вход x, который первоначально содержался на ее ленте. То, что вначале вход x был проигнорирован, не имеетникакого значения, поскольку по определению МТ допускает то, что было на ее ленте доначала операций.
Таким образом, если M допускает w, то код M′ принадлежит Lne.Наоборот, если M не допускает w, то M′ никогда не допустит свой вход, каким бы онни был. Следовательно, в этом случае код M′ не принадлежит Lne. Таким образом, Lu сводится к Lne с помощью алгоритма, который строит M′ по данным M и w. Поскольку Lu неявляется рекурсивным, то и Lne также не рекурсивен. Того, что это сведение существует,вполне достаточно для завершения доказательства. Однако для того, чтобы проиллюстрировать значимость сведения, продолжим наши рассуждения. Если бы Lne был рекурсивным, то можно было бы построить алгоритм для Lu следующим образом.1.Преобразовать (M, w) в МТ M′ описанным выше способом.2.Выяснить с помощью гипотетического алгоритма для Lne, верно ли L(M′) = ∅. Еслиэто так, то сказать, что M не допускает w, если же L(M′) ≠ ∅, то сказать, что Mдопускает w.Поскольку из теоремы 9.6 известно, что такого алгоритма для Lu нет, приходим к противоречию с тем, что Lne является рекурсивным, и делаем вывод, что Lne — не рекурсивный.
Теперь известен и статус языка Le. Если бы Le был РП, то по теореме 9.4 и он, и Lneбыли бы рекурсивными. Но поскольку Lne не является рекурсивным по теореме 9.9, тосправедливо следующее утверждение.Теорема 9.10. Язык Le не является РП. 396Стр. 396ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜ9.3.3. Òåîðåìà Ðàéñà è ñâîéñòâà ÐÏ-ÿçûêîâНеразрешимость языков, подобных Le и Lne, в действительности представляет собойчастный случай гораздо более общей теоремы: любое нетривиальное свойство РПязыков неразрешимо в том смысле, что с помощью машин Тьюринга невозможно распознать цепочки, которые являются кодами МТ, обладающих этим свойством.
Примеромсвойства РП-языков служит выражение “язык является контекстно-свободным”. Вопросо том, допускает ли данная МТ контекстно-свободный язык, является неразрешимым частным случаем общего закона, согласно которому все нетривиальные свойства РПязыков неразрешимы.Свойство РП-языков представляет собой некоторое множество РП-языков. Такимобразом, формально свойство языка быть контекстно-свободным — это множество всехКС-языков.
Свойство быть пустым есть множество {∅}, содержащее только пустой язык.Ïî÷åìó ïðîáëåìû è èõ äîïîëíåíèÿ ðàçëè÷íûИнтуиция подсказывает, что в действительности проблема и ее дополнение — одна ита же проблема. Для решения одной можно использовать алгоритм решения другой, илишь на последнем шаге взять отрицание ответа: вместо “нет” сказать “да” и наоборот. Если проблема и ее дополнение рекурсивны, это действительно верно.Однако, как обсуждалось в разделе 9.2.2, существуют две другие возможности.
Вопервых, может быть, что ни сама проблема, ни ее дополнение не являются даже РП.Тогда ни одна из них вообще не может быть решена никакой МТ. В этом смысле онипо-прежнему похожи друг на друга. Существует, однако, еще одна интересная ситуация типа Le и Lne, когда один из языков является РП, а другой — нет.Для языка, являющегося РП, можно построить МТ, которая получает на вход цепочкуw и исследует, почему данная цепочка принадлежит языку. Так, для Lne и данной в качестве входа МТ M мы заставляем нашу МТ искать цепочки, которые допускает этаМТ, и, обнаружив хотя бы одну такую цепочку, допускаем M. Если M — МТ с пустым языком, то мы никогда не будем знать наверняка, что M не принадлежит Lne, нопри этом никогда и не допустим M, и это будет правильным откликом МТ.С другой стороны, для дополнения этой проблемы — языка Le, который не являетсяРП, вообще не существует способа, позволяющего допустить все его цепочки.
Предположим, что нам дана цепочка M, представляющая МТ с пустым языком. Проверяяразличные входы M, мы можем никогда не найти такого, который M допускает, нопри этом не сможем и быть уверенными в том, что такого входа нет среди еще непроверенных. Поэтому M никогда не сможет быть допущена, даже если и должна.Свойство называется тривиальным, если оно либо пустое (т.е. никакой язык вообщеему не удовлетворяет), либо содержит все РП-языки. В противном случае свойство называется нетривиальным.9.3. ÍÅÐÀÇÐÅØÈÌÛÅ ÏÐÎÁËÅÌÛ, ÑÂßÇÀÍÍÛÅ Ñ ÌÀØÈÍÀÌÈ ÒÜÞÐÈÍÃÀСтр. 397397• Отметим, что пустое свойство ∅ и свойство быть пустым языком — не одно и то же.Мы не можем распознать множество языков так, как сами эти языки. Причина в том,что обычный бесконечный язык нельзя записать в виде цепочки конечной длины, которая может быть входом некоторой МТ.
Вместо этого мы должны распознавать машиныТьюринга, которые допускают эти языки. Код самой МТ конечен, даже если язык, который она допускает, бесконечен. Таким образом, если P — это свойство РП-языков, тоLP — множество кодов машин Тьюринга Mi, языки L(Mi) которых принадлежат P. Говоря о разрешимости свойства P, мы имеем в виду разрешимость языка LP.Теорема 9.11 (теорема Райса). Всякое нетривиальное свойство РП-языков неразрешимо.Доказательство. Пусть P — нетривиальное свойство РП-языков. Вначале допустим,что пустой язык ∅ не принадлежит P; противоположный случай рассмотрим позже. Поскольку P — нетривиально, должен существовать непустой язык L, принадлежащий P.Пусть ML обозначает МТ, допускающую L.Сведем Lu к LP, и этим докажем, что язык LP неразрешим, поскольку Lu неразрешим.Алгоритм сведения получает на вход пару (M, w) и выдает некоторую МТ M′.
СтруктураM′ представлена на рис. 9.10. Если M не допускает w, то L(M′) есть ∅, и L(M′) = L, еслиM допускает w.ДопуститьначалоДопуститьДопуститьРис. 9.10. Схема M′ для доказательства теоремы РайсаM′ — двухленточная МТ. Одна лента используется для моделирования работы M совходом w.
Напомним, что алгоритм сведения получает на вход пару (M, w) и может использовать ее для построения переходов M′. Таким образом, имитация M со входом w“встроена” в M′, которой не нужно считывать с ленты переходы M.Вторая лента M′ используется для моделирования работы ML с цепочкой x, входной для M′ . Еще раз отметим, что переходы ML известны алгоритму сведения и могут быть “встроены” в переходы M′ . По построению МТ M′ должна выполнять следующие операции.1.398Стр. 398Имитировать работу M со входом w. Отметим, что w не является входом M′. M′ записывает M и w на одну из своих лент и имитирует МТ U на этой паре, как в доказательстве теоремы 9.8.ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜ2.Если M не допускает w, то M′ больше ничего не делает, т.е. не допускает любой свойвход x, поэтому L(M′) = ∅.
Мы предположили, что ∅ не содержится в свойстве P,поэтому код M′ не принадлежит LP.3.Если M допускает w, то M′ начинает имитацию ML на своем собственном входе x.Таким образом, M′ допускает именно язык L. Поскольку L принадлежит P, то код M′принадлежит LP.Как видим, построение M′ по M и w можно провести в соответствии с некоторым алгоритмом. Поскольку этот алгоритм превращает (M, w) в M′, которая принадлежит LP тогда и только тогда, когда (M, w) принадлежит Lu, этот алгоритм представляет собой сведение Lu к LP и доказывает неразрешимость свойства P.Для завершения доказательства нужно еще рассмотреть вариант, когда ∅ принадлежит P. Для этого рассмотрим дополнение P свойства P, т.е. множество РП-языков, необладающих свойством P. Из описанных выше рассуждений следует, что свойство Pнеразрешимо.
Однако поскольку всякая МТ допускает некоторый РП-язык, то LP , т.е.множество (кодов) машин Тьюринга, не допускающих языки из P, совпадает с LP —множеством МТ, допускающих языки из P . Предположим, что язык LP разрешим. Тогда LP также должен быть разрешимым, поскольку дополнение рекурсивного языка рекурсивно (теорема 9.3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
