Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 90
Текст из файла (страница 90)
2 Рис. 9. 7. Сведение переводит позитивные знземпляры в позитивные, а негативные — в негативные Формально сведение Р1 к Р, является машиной Тьюринга, которая начинает работу с экземпляром проблемы Р~ на ленте и останавливается, имея на ленте экземпляр проблемы Рз. Как правило, сведения описываются так, как если бы они были компьютерными программами, которые на вход получают экземпляры Р, и выдают экземпляры Р,.
Эквиваяентность машин Тьюринга и компьютерных программ позволяет описывать сведение в терминах как тех, так и других. Значимость пропедуры сведения подчеркивается следующей широко используемой теоремой. Теорема 9.7. Если Р, можно свести к Рз, то: а) если Р, неразрешима, то и Рз неразрешима; б) если Р~ не-РП, то Р, также не-РП. Доказательство. Предположим сначала, что проблема Р1 неразрешима. Если решить Р, возможно, то, объединяя сведение Р, к Р, и алгоритм решения последней, можно построить алгоритм, решающий Рь Эта идея была проиллюстрирована на рис. 8.7. Поясним подробнее.
Пусть дан экземпляр зе проблемы Рь Применим к нему алгоритм, который переводит зе в экземпляр х проблемы Ръ Затем применим к х алгоритм, решающий Р,. Если алгоритм выдает ответ "да", то х принадлежит Рз. Поскольку Р, была сведена к Ръ то известен ответ "да" для Р, на и, т.е. зе принадлежит Ро Точно так же, если х не принадлежит Р„то и и не принадлежит Р,.
Итак, ответ на вопрос "х принадлежит Рз7" является также правильным ответом на вопрос "и принадлежит Р,7". Таким образом, получено противоречие с предположением, что проблема Р, неразрешима. Делаем вывод, что если Р, неразрешима, то и Р, неразрешима. Рассмотрим теперь часть б. Предположим, что Рз (в отличие от Р,) является РП. В данном случае у нас есть алгоритм сведения Р, к Р„но для Р, существует лишь пропедура распознавания, т.е. МТ, которая дает ответ "да", когда ее вход принадлежит Р„и мо- 9.3.
НЕРАЗРЕШИМЫЕ ПРОЕЛЕМЫ, СВЯЗАННЬГЕ С МАШИНАМИ ТЬЮРИНГА 393 жет работать бесконечно, когда вход не принадлежит Р,. Как и в части а, с помощью алгоритма сведения преобразуем экземпляр и проблемы Р, в экземпляр х проблемы Р,. Затем применим к х МТ для Р,. Если х допускается, то допустим н и . Эта процедура описывает МТ (возможно, работающую бесконечно), языком которой является Рп Если и принадлежит Р„то х принадлежит Р„и поэтому данная МТ допускает зс. Если же ту не принадлежит Рь то х не принадлежит Р,. Тогда МТ может или остановиться, или работать бесконечно, но в обоих случаях она не допустит и.
Поскольку по предположению МТ, распознающей Р„ не существует, то полученное противоречие доказывает, что МТ для Рз также не существует. Таким образом, если Р, не-РП, то и Р, не-РП. П 9,3.2. Машины Тьюринга, допускающие пустой язык В качестве примера сведения, связанного с машинами Тьюринга, исследуем языки, известные как з'., и Т.„,. Оба они состоят из двоичных цепочек.
Если и — двоичная цепочка, то она представляет некоторую МТ М; из перечисления, описанного в разделе 9.1.2. Если Л4 = И, т.е. Лз, не допускает никакого входа, то М принадлежит Ди Таким образом, Е, состоит из кодов всех МТ, языки которых пусты. С другой стороны, если ЦМ) не пуст, то и принадлежит з'.„,. Таким образом, з',„, состоит из кодов всех машин Тьюринга, которые допускают хотя бы одну цепочку. В дальнейшем нам будет удобно рассматривать цепочки как машины Тьюринга, представленные этими цепочками.
Итак, упомянутые языки определяются следующим образом. ° з'., = 1М ) ЦМ) = И) ° Т,м = (М! ЦЩ и И) Отметим, что )„и з.„, — языки над алфавитом (О, 1), дополняющие друг друга. Как будет видно, Тм является "более легким". Он РП, но не рекурсивный, в то время как )„— не-РП. Теорема 9.8. Язык Ди рекурсивно перечислим. Доказательство. Достаточно предъявить МТ, допускающую Т,„,. Проще всего это сделать, описав недетерминированную МТ )з', которая схематично изображена на рис.
9.8. Согласно теореме 8.11 з)з можно преобразовать в детерминированную МТ. Допустить Рис. 9.8 Кокструкция НЛ4Т, дояускаюиЗсй язык гзк 394 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ Работа М заключается в следующем. 1. На вход М подается код МТ М,. ! 2. Используя недетерминизм, М угадывает вход и, который, возможно, допускается М. 3. Мпроверяет, допускает ли М; свой входи. В этой части М может моделировать ра- боту универсальной МТ (з'„допускающей 2.„.
4. Если М, допускает н, то и М допускает свой вхол, т.е. М,. Таким образом, если М допускает хотя бы одну цепочку, то М угадает ее (среди прочих, конечно) н допустит М,. Если же ЦМ) = О, то ни одна из угаданных и не допускается М, н Мне допустит Мь Таким образом, ЦМ) = 2.„,. П Следующим шагом будет доказательство, что язык з.„, не является рекурсивным. Для этого сведем к 2,„, язык А„, т.е. опишем алгоритм, который преобразует вход (М, и) в вы- ход М' — код еще одной машины Тьюринга, для которой зс принадлежит ЦМ) тогда и только тогда, когда язык т,(М') не пуст.
Таким образом, М допускает и тогда и только тогда, когда М'допускает хотя бы одну цепочку. Прием состоит в том, что М'игнорирует свой вход, а вместо этого моделирует работу М на н. Если М допускает и, то М' допускает свой собственный вход. Таким образом, ЦМ') не пуст тогда и только тогда, когда М допускает зв.
Если бы 2„, был рекурсивным, то у нас был бы алгоритм выяснения, допускает ли М вход н: построить М'и проверить, будет лн ЦМ') = О. Теорема 9.9. Язык 2„, не является рекурсивным. Доказательство. Уточним доказательство, кратко описанное выше. Нужно построить алгоритм, который преобразует свой вход — двоичный код пары (М, и) — в МТ М; лля которой ЦМ') и О тогда и только тогда, когда М допускает вход и. Данная конструкция схематично представлена на рнс. 9.9.
Как булет показано, если М не допускает и, то М'не допускает никакого входа, т.е. ЦМ') = О. Но если М допускает и, то М'допускает любой вход, и поэтому, конечно же, ЦМ) зь О. Допустить Рис. 9.9. Схема МТМ', построенной по (М, в) в теореме 9.9; М' допускает произвольный вход тогда и только тогда, когда М допускает зи М'по построению выполняет следующие действия. 1.
М'игнорирует собственный вход. Она заменяет его цепочкой, представляющей МТ М и ее вход зо. Поскольку М'строится для конкретной пары (М, и), имеющей неко- 9.3. НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ, СВЯЗАННЫЕ С МАШИНАМИ ТЬЮРИНГА 395 торую длину и, можно построить М'с состояниями д„уь ..., су„(гуа — начальное со- стояние), причем: а) в состоянии гу„! =О, 1, ..., и — 1, Мзаписывает (1+ 1)й бит кода (М и), переходит в состояние гуи, и сдвигается вправо; б) в состоянии у„в случае необходимости М'сдвигается вправо и заполняет все непустые клетки (содержащие "хвост" цепочки х, если ее длина больше и) пробелами. 2.
Когда М'достигает пробела в состоянии д„, она, используя похожий набор состояний, перемещает головку в левый конец ленты. 3. М; используя дополнительные состояния„моделирует универсальную МТ П на полученной ленте. 4, Если ЕУ допускает, то и М'допускает. Если ЕУ никогда не допускает, то и М' никогда не допускает. Привеленное описание М' показывает возможность построения машины Тьюринга, которая переводит код М и цепочки и в код М'. Таким образом, существует алгоритм сведения Е„к Е„,.
Кроме того, если М допускает и, то М'допускает любой вход х, который первоначально содержался на ее ленте. То, что вначале вход х был проигнорирован, не имеет никакого значения, поскольку по определению МТ допускает то, что было на ее ленте до начала операций. Таким образом, если М допускает и, то код М'принадлежит У.„,. Наоборот, если Мне допускает и, то М' никогда не допустит свой вход, каким бы он ни был.
Следовательно, в этом случае код М'не принадлежит У „. Таким образом, Е„сводится к Е„, с помощью алгоритма, который строит М'по данным М и зг. Поскольку Е„не является рекурсивным, то и Е„, также не рекурсивен. Того, что это сведение существует, вполне достаточно лля завершения доказательства. Однако для того, чтобы проиллюстрировать значимость сведения, продолжим наши рассуждения. Если бы Е„, был рекурсивным, то можно было бы построить алгоритм для Е„следующим образом. !. Преобразовать (М, и) в МТ М'описанным выше способом.
2. Выяснить с помощью гипотетического алгоритма для Е„„верно ли ЦМ) =- О. Если это так, то сказать, что М не допускает и, если же ЦМ') ~ 121, то сказать, что М допускает и. Поскольку из теоремы 9.6 известно, что такого алгоритма для Е„нет, приходим к противоречию с тем, что Е является рекурсивным, и делаем вывод, что Е„, — не рекурсивный. ь1 Теперь известен и статус языка Е,.
Если бы Е, был РП, то по теореме 9.4 и он, и Е„, были бы рекурсивными. Но поскольку Е„, не является рекурсивным по теореме 9.9, то справедливо следующее утверждение. Теорема 9.10. Язык Е, не является РП. П 396 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ 9.3.3.
Теорема Райса и свойства РП-языков Неразрешимость языков, подобных Е, и А„„в действительности представляет собой частный случай гораздо более общей теоремы: любое нетривиальное свойство РП- языков неразрешимо в том смысле, что с помощью машин Тьюринга невозможно распознать цепочки, которые являются кодами МТ, обладающих этим свойством. Примером свойства РП-языков служит выражение "язык является контекстно-свободным'*. Вопрос о том, допускает ли данная МТ контекстно-свободный язык, является неразрешимым частным случаем общего закона, согласно которому все нетривиальные свойства РП- языков неразрешимы.
Сеойсгнео РП-языков представляет собой некоторое множество РП-языков. Таким образом, формально свойство языка быть ко~пекстно-свободным — это множество всех КС-языков. Свойство быть пустым есть множество (О), содержащее только пустой юык. 11очему проблемы и их дополнения различны Интуиция подсказывает, что в действительности проблема и ее дополнение — одна и та же проблема. Для решения одной можно использовать алгоритм решения другой, и лишь на последнем шаге взять отрицание ответа; вместо "нет" сказать "да" и наоборот. Если проблема и ее дополнение рекурсивны, это действительно верно. Однако, как обсуждалось в разделе 9.2.2, существуют две другие возможности, Вопервых, может быть, что ни сама проблема, ни ее дополнение не являются даже РП.
Тогда ни одна из них вообще не может быть решена никакой МТ. В этом смысле они по-прежнему похожи друг на друга. Существует, однако, еше одна интересная ситуация типа Е, и А„„когда один из языков является РП, а другой — нет. Для языка, являющегося РП, можно построить МТ, которая получает на вход цепочку в и исследует, почему данная цепочка принадлежит языку. Так, для 1,„, и данной в качестве входа МТ М мы заставляем нашу МТ искать цепочки, которые допускает эта МТ, и, обнаружив хотя бы одну такую цепочку, допускаем М. Если М вЂ” МТ с пустым языком, то мы никогда не будем знать наверняка, что М не принадлежит Ь„„но при этом никогда и не допустим М, и это будет правильным откликом МТ. С другой стороны, для дополнения этой проблемы — языка йы который не является РП, вообще не существует способа, позволяющего допустить все его цепочки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
