Гладкий - Формальные грамматики и языки - 1973 (947381), страница 51
Текст из файла (страница 51)
К этому типу относятся проблема распознавания принадлежности цепочки языку, порождаемому данной грамматикой, проблема распознавания замещаемости одной цепочки на другую в языке, порождаемом данной грамматикой, и т. п. Заметим, что при фиксировании цепочек хь,, х общая проблема распознавания Р(1., хь ..., х„) переходит в проблему первого типа — о распознавании некоторого свойства языков.
Например, фиксируя х в предикате х ен 1., получаем проблему распознавания свойства языка содержать данную цепочку. В заключение параграфа сделаем одно простое замечание, которое будет чрезвычайно полезно нам в дальнейшем. Пусть л и 3 — классы конструктивных объектов, а — свойство объектов класса % и () — свойство объектов класса Ф. Пусть, далее, имеется алгоритм лоо НЕРАЗРЕШИМЫЕ, АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ )ГЛ. й К Злд ИНВАРИАНТНЫЕ СВОЙСТВА ПРОИЗВОЛЬНЫХ ГРАММАТИК ОК7 т(з, позволяющий для всякого а еи "й построить такое Ь(а) еп Е, что Ь(а) обладает свойством р тогда и толь-: ко тогда, когда а обладает свойством а.
Если при этом существует также алгоритм И, позволяющий для всякого объекта Ь ен 6 распознать, обладает ли он свойством !), то есть и алгоритм, позволяющийдля всякогообъекта. а ен й распознать, обладает ли он свойством а (доста-. точно по данному а построить Ь(а) и затем применить к Ь(а) алгоритм Я).
Поэтому при наличии алгоритма т)) неразрешимость проблемы распознавания и влечет неразрешимость проблемы распознавания р. Если описанный алгоритм ф существует, мы бу.- дем говорить, что проблема распознавания а сводится к проблеме распознавания !3. Таким образом, для доказательства неразрешимости алгоритмической проблемы достаточно свести к ней какую-либо другую алгоритмическую проблему, неразрешимость которой уже доказана. Точнее, мы установили,. это для проблем распознавания свойств; но тот же прием мы можем использовать и для проблем распознавания отношений, поскольку отношение, например, между двумя конструктивными объектами можно рассмлтривать как свойство упорядоченной пары объектов, а йара конструктивных объектов также есть конструктивный объект.
2 8.2. Инварнантиые свойства произвольных грамматик В дальнейшем нам часто придется, рассматривая не. который класс грамматик э, выделять те грамматики: этого класса, которые имеют фиксированный основной' словарь )г. Совокупность всех таких грамматик мы бу-: дем обозначать через э к, а класс языков, ими порождаемых,— в соответствии с соглашением на стр. ЗО— через 2'(з и).
Напомним также, что класс произволь. ных грамматик мы договорились обозначать через Г. Целью настоящего параграфа является доказательл ство следующей теоремы. Теорема 8.1. Каков бы ни был словарь )г, никакое свойство язгяков, нетривиальное в классе .У(ГР)— иначе говоря, в классе рекурсивно перечислимых язЫт ков, содержащихся в )г", — не может быть распознаваемым в классе Гк и тем более в классе всех грамматик. Вместо этого утверждения нам удобнее будет доказывать другое, равносильное ему ввиду теоремы 1.4, а именно: Теорем а 8.!'. Каково бьг ни было свойство языков а, нетривиальное в классе рекурсивно перечислилгых языков, содержащихся в )'*, где )7 — фиксированньгй непустой алфавит, не существует алгоритма, поэволягощего для любой Э-машины М с входным алфавитом )л распознать, обладает ли язык Т.(М) свойством а.
Для доказательства теоремы 8.1' установим, в свою очередь, справедливость следующей теоремы, которая понадобится иам и дальше. Теорема 8.2 (теорема Райса). Пусть В' и фиксированнгяе непустые алфавиты и 5 — класс всевозможных частично рекурсивных функций, области определения и множества значений которых содержатся в (г'к и )г* соответственно. Пусть, кроме того, а — произвольное свойство функций, нетривиальное. в классе О, г.
е. такое, что в 5 есть как функции, обладаюи!ие этим свойством, так и функции, им не обладающие. Тогда не сугцествуег алгоритма, позволяющего для любой ДЭ- машины с входным алфавитом (Тг распознать, обладает ли функция Прт!(х), где !(х) — вычисляемая данной машиной функция *), свойством и. Нетрудно видеть, что теорема 8.2 влечет теорелгу 8.!'.
Действительно, по теоремам 1.2 и 1.3 для всякой Э-машины М, допускающей Т. (М) с: — )г', можно построить ДЭ-машину М', вычисляющую функцию с множеством значений !.(М). Область определения этой функции не обязана, вообще говоря, содержаться в йуе, но она, во всяком случае, представляет собой язык в некотором (конечном) алфавите 2, и легко построить ДЭ-машину М" (см., например, упражнение !.19, а), б) ), осуществляющую взаимно однозначное отображение Ю'* на Я'. Комбинируя машины М" и М', получаем ДЭ- машину Мг, вычисляющую функцию с множеством значений с(М) и областью определения, содержащейся в )лт*.
С другой стороны, для любой Э-машины, *) Очевидно, всякая ДЭ-машина вычисляет некоторую фуницвю !кггторая может, впрочем, оказаться нигде не определенной). 9 А. В, Гладкий 25З НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПГОВЛЕМЫ [ГЛ. В ! ЯП ИНВАРИАНТНЫЕ СВОЙСТВА ПРОИЗВОЛЬНЫХ ГРАММАТИК 259 вычисляющей функцию ) (х), тривиальным образом строится э-машина, вычисляющая функцию прГ((х), а это ввиду теоремы 1.3 позволяет построить Э-машину (с входным алфавитом )т), допускающую множество значений Прг((х). Пусть теперь 8 — произвольное свойство языка и а — свойство функции иметь множество значений, проекция которого на )тобладает свойством 8.
Из предыдущего ясно, что если 8 нетривиально в классе рекурсивно перечислимых языков в алфавите )т, то а нетривиально в классе 5, и из существования алгоритма, распознающего по любой Э-машине 'М с входным алфавитом Г', обладает ли Е(М) свойством 8, немедленно вытекало бы существование алгоритма, позволяющего по любой ДЭ-машине с входным алфавитом В' распознать, обладает ли соответствующая функция Пр!1(х) свойством а.
Обратимся к доказательству теоремы 8.2. Будем рассматривать всевозможные ДЭ-машины с входным алфавитом В'. Без ущерба для общности можно считать, что; рабочие алфавиты и множества состояний всех рассматриваемых машин содержатся в непересекающихся счетных множествах У и )Г соответственно, н сверх того )т' ()'Ф = 8 (поскольку это ограничение не сказывается на объеме класса вычисляемых машинами функций). ' Класс всех таких машин мы обозначим через И.
Сопоставим каждой машине М еи И цепочку х(М) еи У', которая будет называться кодом машины М, следующим образом. а) Допустим сначала, что мощность %' не меньше двух. Выберем в (Г! произвольным образом два символа а и Ь. Положим 2=)т()0())т' и Х=Я()(П, Л, — ), где П, Л, - — некоторые символы, не входящие в Я. Занумеруем каким-либо образом элементы Х (например, элементы )Г () (П, Л,- ) первыми р+3 целыми положительными числами, где р — мощность (т, а эле- -' менты )Г' и У вЂ” )т соответственно четными и нечетными числами, ббльшими р+3). Для произвольного символа аеяХ обозначим через х(а) цепочку Ьа"Ь, где Ь вЂ” номер а. Для произвольной непустой цепочки ы = а!...
...а„где а!, ..., а,енХ, обозначим через х(м) цепочку х(а!) ... х(а,). Наконец, для произвольной машины М ее И обозначим через ым цепочку д!в!... !)!1!... 1„, где д! — начальное состояние М, д!, ..., д! — все заключительные состояния М и 1!, ..., 1„— все инструкции М, причем д! расположены в порядке возрастания их номеров в выбранной нами нумерации Х, а / — в лексикографическом порядке (т. е. сначала по возрастанию номеров первых символов, затем вторых и т.
д.), и положим х(М) = х(ь)м) б) Если %' состоит из одного элемента аь то сначала построим для каждой машины М ее И цепочку х'(М) точно так же, как в предыдущем случае строилась х(М), но используя вместо а и Ь произвольные различные символы а' и Ь' а затем положимх(М)=а' !"'!МВ, где ч — отображение, определенное в упражнении 1.3 (при й = 2, а! — — а', аз = Ь').
Будем называть машину М ее И с ам оп р и ме- ни, если область определения вычисляемой этой машиной функции содержит код М, и н е с а м о п р и м е н им ой в противном случае. Имеет место Л е м м а 8.1. Ое существует алгоритма, позволяющего для любой машины из И распознать, является ли Она самоприл!гнилой. Доказательство леммы 8.1. Поскольку ма'- шина класса И восстанавливается по своему коду однозначно и эффективно, существование указанного алгоритма означало бы существование ДЭ-машины Мь вычисляющей функцию, определенную на всех кодах машин из И и принимающей на кодах всех самоприменимых машин одно и то же значение и!, а на кодах всех несамоприменимых машин — одно и то же значение !ь„ отличное от ьз!.
Допустим, что такая машина М! существует; без нарушения общности можно считать, очевидно, что она принадлежит И. По М, легко построить (это предоставляется читателю) другую машину Мь тоже принадлежащую И и работающую на кодах несамоприменимых машин так же, как М!, а на кодах самоприменнмых машин работающую вечно, так что вычисляемая этой машиной функция ) определена на кодах всех несамоприменимых машин и не определена ни на одном коде самоприменимой машины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
