Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Обратимся к доказательству теоремы 8.2. БуДем рассматривать всевозможные ДЭ-машины с входным алфавитом W. Без ущерба для общности можно считать, что рабочие алфавиты и множества состояний всех рассматриваемых машин содержатся в непересекающихся счетных множествах U и R соответственно, и сверх того R |>М = 0 (поскольку это ограничение не сказывается на объеме класса вычисляемых машинами функций). Класс всех таких машин мы обозначим через 2JJ. Сопоставим каждой машине М е 2JJ цепочку х(М) е W+, которая будет называться кодом машины М, следующим образом.
а) Допустим сначала, что мощность W не меньше двух. Выберем в W произвольным образом два символа а и Ь. Положим Z = V U U U R и X = Z U {П, Л, —*?}, где П, Л, —? — некоторые символы, не входящие в Z. Занумеруем каким-либо образом элементы X (например, элементы V U {П, Л, —»-} первыми р + 3 целыми положительными числами, где р — мощность V, а элементы R и U—V соответственно четными и нечетными числами, большими р + З). Для произвольного символа ае! обозначим через и (а) цепочку bahb, где k — номер а. Для произвольной непустой цепочки со = ai . .. ... as, где ai, ..., aisl, обозначим через х(со) цепочку x(ai) ... x(as). Наконец, для произвольной машины М е 2JJ обозначим через сом цепочку qtq1. . . q41... /„,
§ 8.2] ИНВАРИАНТНЫЕ СВОЙСТВА ПРОИЗВОЛЬНЫХ ГРАММАТИК 259
где qi — начальное состояние М, ql, ..., ql — все заключительные состояния М и /1, . ..; /„ — все инструкции М, причем qi расположены в порядке возрастания их номеров в выбранной нами нумерации X, а /,} — в лексикографическом порядке (т. е. сначала по возрастанию номеров первых символов, затем вторых и т. д.), и положим к(М) — х(сом).
б) Если W состоит из одного элемента ао, то сначала построим для каждой машины М <= ЯЛ цепочку к'(М) точно так же, как в предыдущем случае строилась к(М), но используя вместо а и b произвольные различные символы а' и Ь', а затем положимк(М) — а%~1 где v—отображение, определенное в упражнении 1.3 (при k = 2, cti = а', а2 = b ).
Будем называть машину МеЯЙ самопримени-м о й, если область определения вычисляемой этой машиной функции содержит код М, и несамопримени-мой в противном случае. Имеет место
Лемма 8.1. Не существует алгоритма, позволяющего для любой машины из ЗЯ распознать, является ли она самоприменимой.
Доказательство леммы 8.1. Поскольку машина класса 2JJ восстанавливается по своему коду однозначно и эффективно, существование указанного алгоритма означало бы существование ДЭ-машины Мь вычисляющей функцию, определенную на всех кодах ма* шин из 2JJ и принимающей на кодах всех самопримени-мых машин одно и то же значение он, а на кодах всех несамоприменимых машин — одно и то же значение (о2, отличное от coi. Допустим, что такая машина Mi существует; без нарушения общности можно считать, очевидно, что она принадлежит 2JJ. По Mi легко построить (это предоставляется читателю) другую машину М%, тоже принадлежащую 2JJ и работающую на кодах несамоприменимых машин так же, как Mi, а на кодах самоприме-нимых машин работающую вечно, так что вычисляемая этой машиной функция / определена на кодах всех несамоприменимых машин и не определена ни на одном коде самоприменимой машины. Но машина М2 не может быть самоприменимой, поскольку это означало бы, что функция f определена на коде Мг, который был бы при этом кодом самоприменимой машины; в то же время и
9*
260 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. 8
несамоприменимой М2 быть не может — ведь эго равносильно тому, что на коде М2 функция f не определена, и в то же время код М2 был бы кодом несамоприменимой машины, а на таких кодах f как раз определена. Имеем противоречие.
Доказательство теоремы 8.2. Пусть So — подкласс S, состоящий из всех функций, обладающих свойством а, и Si = S — So- По условию оба класса So и Si не пусты. Класс S содержит, в частности, нигде не определенную функцию (т. е. функцию с пустой областью определения) f0; допустим для определенности, что fo е So- Фиксируем далее некоторую функцию /1 е е Si и вычисляющую ее машину Mi е 2JJ. Рассмотрим произвольную машину Mel и построим по ней другую машйну М' е 2JJ, работающую следующим образом. В начале вычисления машина М', «не обращая внимания» на содержимое входной л^нты, записывает на рабочей ленте цепочку к{М) и затем работает как п.о.м. машины М, «пытаясь», таким образом, вычислить значение определяемой этой машиной функции при значении аргумента, являющемся ее собственным кодом. Если соответствующее значение будет вычислено, то вслед за этим рабочая лента уничтожается, а потом машина начинает работать, как Mi, т. е. вычислять значение fi от входной цепочки. В противном случае М' работает вечно. Итак, машина М' вычисляет функцию fie Si, если М самоприменима, и нигде не определенную функцию /о е So, если М несамоприменима. При этом f0 и fi совпадают со своими проекциями на V. Следовательно, проблема распознавания самоприменимости для машин класса Ш сводится к проблеме распознавания свойства а для проекций на V функций, вычисляемых машинами того же класса, так что, согласно замечанию в конце § 8.1, неразрешимость первой проблемы влечет неразрешимость второй.
