Гладкий - Формальные грамматики и языки - 1973 (947381), страница 52
Текст из файла (страница 52)
Но машина Мз не может быть самоприменимой, поскольку это означало бы, что функция 1 определена на коде Мь который был бы при этом кодом самоприменимой машины; в то же время и 266 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. В несамоприменимой М, быть не может — ведь это равносильно тому, что на коде Мз функция 1 яе определена, и в то же время код Мв был бы кодом несамоприменимой машины, а на таких кодах 1 как раз определена, Имеем противоречие. Доказательство теоремы 82. Пусть [уев подкласс [у, состоящий из всех функций, обладающих ° свойством а, и 5[ = 5 — 5о.
По условию оба класса [уа и 5, не пусты. Класс 5 содержит, в частности, ниг,де не определенную функцию (т. е. функцию с пустой областью определения) [е; допустим для определенности, что [вен 5а. ФиксиРУем далее некотоРУю фУнкцию )[еи ~ 5[ и вычисляющую ее машину М[ ы И. Рассмотрим произвольную машину М ~ И и построим по ней другую машнну М'ен И, работающую следующим образом. В начале вычисления машина М', «не обращая внимания» на содержимое входной ленты, записывает на рабочей ленте цепочку и(М) и затем работает как п.о.м. Машины М, «пытаясь», таким образом, вычислить значение определяемой этой машиной функции при значении аргумента, являющемся ее собственным кодом.
Если со" ответствующее значение будет вычислено, то вслед за этим рабочая лента уничтожается, а потом машина начинает работать, как Мь т. е. вычислять значение 1, от входной цепочки. В противном случае М' работает вечно. Итак, машина М' вычисляет функцию )[ ее 5[, если М самоприменима, н нигде не определенную функцию (о~ 6о, если М несамопРименима. ПРН этом [а и 1[ совпадают со своими проекциями на )У. Следовательно, проблема распознавания самопрнменимости для машин класса И сводится к проблеме распознавания свойства а для проекций на )у функций, вычисляемых машинами того же класса, так что, согласно замечанию в конце 5 8.1, неразрешимость первой проблемы влечет неразрешимость второй.
й 8.3. Инвариантные свойства НС-грамматик В предыдущем параграфе мы показали, что в классе произвольных грамматик все нетривиальные свойства языков нераспознаваемы. Уже в классе НС-грамматик ' дело обстоит иначе. Действительно, для произвольной 5 аз] инвАРиАнтные сВОпствА нс-ГРАммАтик 26! цепочки х свойство языка содержать х, как уже отме. чалось, распознаваемо в этом классе *).
Поэтому в нем распознаваемы и такие свойства, как «содержать хотя бы одну из двух данных цепочек», «содержать одну данную цепочку и не содержать другую» и т. п. Вообще, если Ф(Е, хь ..., ха) — произвольное булево выражение от предикатов «х[ ее Е», ..., «ха ~ Е» (т, е. выражение, составленное из этих предикатов с помощью пропозициональных связок 1, о[, з У,:э) и Фо(х[, ..., ха)— свойство языка Е удовлетворять условию Ф(Е, х,, ... ..., ха), то Фо(х[, ..., хь) распознаваемо в классе НС. Такие свойства мы назовем булевым и. Однако для некоторого весьма общего типа инвариантных свойств все же удается доказать их нераспознаваемость в классе НС; это и будет основной целью настоящего параграфа. Предварительно докажем несколько лемм. Л ем м а 8.2.
Для всякой ДЭ-машин[я М, входной алфавит которой содержит символ а, можно построить такие НС-грамматики Гм[ и Гвм с одним и тем же одно; элементным основным словарем (Ь), что: а) если вьшисляемая машиной М функция определена для значения аргумента, равного а, то Е(Г[)= =(Ь" ~п)по), Е(Гз)=(Ь" ~1(~п~(по), где по — целое положительное число, зависящее от М; б) в противном случае Е(ГМ[)= О, Е(Гвм)=Ь+.
До к аз а тельство. Построим сначала по машине М ее детерминированную и. о. м. М, (лемма 1.5). Затем построим по М[ другую ДЭ-машину Ма так, чтобы она также представляла собой и. о. м. для М и в то же время обладала тем свойством, что в случае, когда вычисляемая машиной М функция не определена, М, работала бы вечно и при этом ее рабочая лента при достаточно долгой работе оказывалась бы сколь угодно длинной. (Это можно сделать, например, перестроив М[ так, чтобы она: а) перед каждым своим шагом добавляла ' з'з ~й ° з' ° ~гз, р з ю > к,, а.,з В отношеннн распознаваемости ннварнантных свойств зтн два класса вообше ведут себя одинаково (см. сноску на стр.
254). лбл НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОбЛЕМЫ 1ГЛ 8 $8 81 инвАРиАнтные своиствА нс-ГРАММАТИК ЕВЗ бы лишь после перехода машины в «заключительное М1-состояние»; б) в случае <безрезультатной остановки» начинала добавлять и рабочей ленте ячейку за ячейкой без конца.) Кроме того, мы будем считать, что левые части инструкций М2 не содержат заключительных состояний; это, очевидно, не уменьшает общности. В силу теоремы 3.1 достаточно построить неукорачиваю1цие грамматики Гм1 и Г»м со свойствами а) и б):, мы определим их следующим образом. 1) Основной и вспомогательный словари )Г и Ф' и начальный символ 1 — общие для обеих грамматик, а ИМЕННО: )Г=(Ь), )Р =3()аг()(ЧР, 1, Сь), ГдЕ 2, (г— соответственно рабочий алфавит и множество состояй М, йЬ, 1, С, ~3 () О () (Ь). 2) Схемы обеих грамматик содержат правило 1 — » яр а1ай, где д1 — начальное состояние М, и й — «разделительный символ» (см.
определение и. о. м., стр. 45), . всевозможные правила вида Сьа — »аС8, где иена', и правила, сопоставляемые инструкциям М, следующим образом: каждой инструкции Аа, -» а типа (В) сопоставляется правило Ад — а„С„каждой инструкции а -» Ад типа (ш) — правило а,— » Ада, каждой инструка ции д — а Л типа (1ч) — всевозможные правила вида а Ва,— »1! В, где Вен3, и каждой инструкции '11,-+д„П типа (ч) — всевозможные правила вида а„ — Ва„, где Вен3.
3) Сверх того, схема Г, содержит всевозможные правила вида а — Ь, где д! — заключительное состояние М„вида ЬВ- ЬЬ, где Вен%', вида ВЬ вЂ” ЬЬ, где В~)Р'()(ЧЦ, и правило Ь вЂ” »ЬЬ, а схема Г2 — правила 1-+Ь, 1-+ЬЬ, 1-+ЬЬЬ и всевозможные правила вида В Ь, где В ~ Х () 1Е () (4Р).
Ясно, что если вычисляемая машиной М функция определена на а, то ситуаций машины Мь достижимых ' из ситуации 38=(д„Л, 4~ ф, Л, Чрай), имеется лишь конечное число, причем длины отвечающих этим ситуациям рабочих лент пробегают все натуральные числа от 2 до некоторого п, включительно; поэтому в ГМ1 будут в этом случае выводимы из ! всевозможные цепочки вида ЬА, где Й ) и, + 2, и только такие степени Ь, а в. Г»м — всевозможные цепочки вида Ь', где: 1 ( 1 ( п1 + 2, и только такие степени Ь. В противном случае достижимых из 58 ситуаций будет бесконечно много, длины отвечающих им рабочих лент будут пробегать все натуральные числа, не меньшие 2, но ни одна из этих ситуаций не будет содержать заключительных состояний; поэтому в Г1 не будет выводима из 1 ни -м одна степень Ь, а в Г2, напротив, все степени Ь будут -м выводимы из 1. Л е м м а 8.3, Для любь1х двух НС-грамматик Г1 и Г2 можно построить НС-грамматику, порождаюшую ЯЗЬ1К (х! х 1(Г1) 8 Ву(у -=1(Г2)й1у ~=~ щ.
Д о и а з а т е л ь с т в о. В силу теоремы З.З достаточно построить почти неукорачивающую грамматику, порождающую нужный язык. Пусть Г1 = (1 1~ )Рн 1!г !11), 12 = (1 2ю 1~~2 12ю Й2) Без ограничения общности мы можем считать, что 1<'1 П )<'2 = О. Сопоставим каждому символу аен 'Р'1 новый символ а и обозначим через Г1 грамматику, полученную из Г, заменой каждого символа вен 'Р'1 и каждого его вхождения в каждое правило на а. Положим Г=(111,А ()(!),1,В), где а) 3 = )А»0%1 () %20 0 (а ~ а ~ 'РЛ1), 1 Ф Е () 'Р'1; б) !! получается из объединения схем Г, и Г2 добавлением правил 1 -+ 111» аЬ вЂ” Ьа, Ьа - а, где а и Ь пробегают 1'1 и 112 соответственно. Ясно, что при Р1()'Р2 = Н1Г есть нужная грамматика. В противном случае следует предварительно преобразовать Г2 так же, как было сделано с Г1.
Положим теперь для произвольного языка 1- и произвольного и = 1, 2, ... У-'"'=(х| хенЕ.8с14 х ~(п), 1.чч=(х~ х~ЕЙ1х1>п) и докажем следующую лемму. Л е м м а 8.4. Пусть 1.8, 1.„Ц вЂ” НС-языки и Ы'— класс языков, содержащий 18()11 и не содержащий ни одного из языков 1.8()1)ю()Х2"~. Тогда свойство принадлежать классу 2' нераспознаваемо в классе НС-грамматик.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
