dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 92
Текст из файла (страница 92)
9.15.Отметим, что M допускает входную цепочку 01 в результате следующей последовательности переходов.q101 |− 1q21 |− 10q1 |− 1q201 |− q3101Рассмотрим последовательность частичных решений, которая имитирует эти вычисленияM и в конце концов приводит к решению. Начать нужно с первой пары, как того требуетвсякое решение МПСП.A: #B: #q101#Для того чтобы частичное решение можно было продолжить, следующая цепочка изсписка A должна быть префиксом разности q101#. Поэтому следующей парой должнабыть (q10, 1q2). Это одна из пар, имитирующих переходы, полученная по правилу 3.Итак, получаем следующее частичное решение.A: #q10B: #q101#1q2Теперь можно продолжить частичное решение, используя “копирующие” пары из правила 2 до тех пор, пока не дойдем до состояния во втором МО.
Тогда частичное решениепримет такой вид.A: #q101#1B: #q101#1q21#19.4. ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀСтр. 409409Для имитации перехода тут снова можно использовать пару из правила 3. Подходящейявляется пара (q21, 0q1), и в результате получается следующее частичное решение.A: #q101#1q21B: #q101#1q21#10q1ПравилоСписок AСписок B(1)##q101#(2)01#01#(3)q100q11#1q11#0q1#1q1#0q201q20q21q2#1q2q200q210q201#q211#q300#q310#0q10q2#(4)0q300q311q301q310q31q3q30q31q3q3q3q3q3q3q3q3(5)q3###Источникδ(q1, 0) = (q2, 1, R)δ(q1, 1) = (q2, 0, L)δ(q1, 1) = (q2, 0, L)δ(q1, B) = (q2, 1, L)δ(q1, B) = (q2, 1, L)δ(q2, 0) = (q3, 0, L)δ(q2, 0) = (q3, 0, L)δ(q2, 1) = (q1, 0, R)δ(q2, B) = (q2, 0, R)Рис.
9.15. Экземпляр МПСП, построенный по МТ M и слову w из примера 9.18Теперь можно было бы использовать пары из правила 3 и скопировать следующие трисимвола #, 1 и 0. Однако это решение было бы ошибочным, поскольку следующий переходM сдвигает головку влево, и символ 0, стоящий непосредственно перед состоянием, потребуется в следующей паре из правила 3. Поэтому копируются лишь два следующих символа.A: #q101#1q21#1B: #q101#1q21#10q1#1410Стр. 410ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜПодходящей парой из правила 3 является (0q 1#, q 201#), и получается новое частичное решение.A: #q101#1q21#10q1#B: #q101#1q21#10q1#1q201#Используя теперь еще одну пару (1q20, q310) из правила 3, приходим к допусканию.A: #q101#1q21#10q1#1q20B: #q101#1q21#10q1#1q201#q310Теперь, с помощью пар из правила 4 в МО исключаются все символы, кроме q3. Дляправильного копирования символов нужны также пары из правила 2.
Частичное решениепродолжается до следующего.A: #q101#1q21#10q1#1q201#q3101#q301#q31#B: #q101#1q21#10q1#1q201#q3101#q301#q31#q3#Теперь в МО находится лишь q3. Чтобы завершить решение, можно использовать пару(q3##, #) из правила 5.A: #q101#1q21#10q1#1q201#q3101#q301#q31#q3##B: #q101#1q21#10q1#1q201#q3101#q301#q31#q3##Теорема 9.19. Проблема соответствий Поста неразрешима.Доказательство. Цепь сведений, представленная на рис.
9.11, почти завершена. Сведение МПСП к ПСП было показано в теореме 9.17. В данном разделе приведена конструкция, позволяющая свести Lu к МПСП. Таким образом, для завершения доказательстванеразрешимости ПСП покажем, что эта конструкция корректна, т.е.• M допускает w тогда и только тогда, когда построенный экземпляр МПСП имеетрешение.(Необходимость) Основную идею подсказывает пример 9.18. Если w принадлежитL(M), то можно проимитировать работу M со входом w, начав с пары из правила 1. Длякопирования состояния каждого МО и имитации одного перехода M используются парыиз правила 3, а для копирования ленточных символов и при необходимости маркера # —из 2.
Если M попадает в допускающее состояние, то с помощью пар из правила 4 и заключительной пары из 5 мы позволяем цепочке A догнать цепочку B, тем самым формируя решение.(Достаточность) Нужно доказать, что если данный экземпляр МПСП имеет решение, то только потому, что M допускает w. Отметим, что, поскольку мы имеем дело сМПСП, любое решение должно начинаться с первой пары, так что начало частичногорешения имеет следующий вид.A: #B: #q0w#9.4. ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀСтр.
411411Поскольку в этом частичном решении нет допускающего состояния, то пары из правил 4и 5 бесполезны. Состояния и окружающие их один или два символа могут быть обработаны только с помощью пар из правила 3, а все остальные ленточные символы и # должны быть обработаны с помощью пар из правила 2. Поэтому, если M не попала в допускающее состояние, все частичные решения имеют общий видA: xB: xy,где x — последовательность МО машины M, представляющих вычисления M со входомw, возможно, с символом # и началом α следующего МО в конце. Разность y содержитзавершение α, еще один символ # и начало МО, следующего за α, вплоть до точки, накоторой заканчивается α в x.Отметим, что до тех пор, пока M не попадает в допускающее состояние, частичноерешение не является решением, поскольку цепочка B длиннее цепочки A.
Поэтому, еслирешение существует, то M должна когда-нибудь попасть в допускающее состояние, т.е.допустить w. 9.4.4. Óïðàæíåíèÿ ê ðàçäåëó 9.49.4.1.Выясните, имеют ли решение следующие экземпляры ПСП. Каждый из нихпредставлен двумя списками — A и B, и i-е цепочки списков соответствуют другдругу (i = 1, 2, ...).а) (∗) A = (01, 001, 10); B = (011, 10, 00).б) A = (01, 001, 10); B = (011, 01, 00).в) A = (ab, a, bc, c); B = (bc, ab, ca, a).9.4.2.(!) Было доказано, что ПСП неразрешима в предположении, что алфавит Σ может быть произвольным.
Покажите, что ПСП неразрешима даже при ограничении Σ = {0, 1}, сведя ПСП к данному частному случаю.9.4.3.(∗!) Допустим, ПСП ограничена односимвольным алфавитом Σ = {0}. Будет лиПСП и в этом ограниченном случае по-прежнему неразрешимой?9.4.4.(!) ТАГ-система Поста образуется множеством пар цепочек в некотором конечном алфавите Σ и стартовой цепочкой. Если (w, x) — пара и y — произвольная цепочка в Σ, то мы говорим, что wy |− yx. Таким образом, на одном шагеможно стереть некоторый префикс w “текущей” цепочки wy и вместо него в*конце приписать второй компонент пары с w — цепочку x. Определим |− какнуль или несколько шагов |− , точно так же, как для порождений в КС-грам*матиках.
Покажите, что проблема выяснения, верно ли z |− ε для данного множества пар P и стартовой цепочки z, неразрешима. Указание. Пусть для любых412Стр. 412ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜМТ M и цепочки w стартовая цепочка z является начальным МО со входом w иразделителем # на конце. Выберите пары P так, что всякое МО M должно в конце концов превращаться в МО, в которое M попадает за один переход.
Устройтетак, что если M попадает в допускающее состояние, то текущая цепочка можетбыть в конце концов стерта, т.е. сведена к ε.9.5. Äðóãèå íåðàçðåøèìûå ïðîáëåìûЗдесь рассматривается ряд других неразрешимых проблем. Основным методом доказательства их неразрешимости является сведение к ним ПСП.9.5.1. Ïðîáëåìû, ñâÿçàííûå ñ ïðîãðàììàìèПрежде всего, отметим, что на любом привычном языке можно написать программу,которая на вход получает экземпляр ПСП и ищет решение по определенной системе, например, в порядке возрастания длины (числа пар) потенциальных решений. ПосколькуПСП может иметь произвольный алфавит, нужно закодировать символы ее алфавита спомощью двоичного или другого фиксированного алфавита, о чем говорилось во врезке“ПСП как язык” в разделе 9.4.1.Наша программа может выполнять любое конкретное действие, например, останавливаться или печатать фразу hello, world, если она нашла решение. В противномслучае программа никогда не выполняет это конкретное действие.
Таким образом, вопрос о том, печатает ли программа hello, world, останавливается ли, вызывает лиопределенную функцию, заставляет ли консоль звенеть, или выполняет любое другое нетривиальное действие, неразрешим. В действительности для программ справедлив аналог теоремы Райса: всякое нетривиальное свойство программы, связанное с ее действиями (но не лексическое или синтаксическое свойство самой программы), является неразрешимым.9.5.2. Íåðàçðåøèìîñòü ïðîáëåìû íåîäíîçíà÷íîñòè ÊÑ-ãðàììàòèêПрограммы и машины Тьюринга — это в общем-то одно и то же, так что в замечаниях из раздела 9.5.1 нет ничего удивительного.
Теперь мы увидим, как ПСП можно свестик проблеме, которая, на первый взгляд, совсем не похожа на вопрос о компьютерах. Этопроблема выяснения, является ли данная КС-грамматика неоднозначной.Основная идея заключается в рассмотрении цепочек, представляющих обращение последовательности индексов, вместе с соответствующими им цепочками одного из списковэкземпляра ПСП. Такие цепочки могут порождаться некоторой грамматикой. Аналогичноемножество цепочек для второго списка экземпляра ПСП также может порождаться некоторой грамматикой. Если объединить эти грамматики очевидным способом, то найдется цепочка, которая порождается правилами каждой исходной грамматики тогда и только тогда,9.5. ÄÐÓÃÈÅ ÍÅÐÀÇÐÅØÈÌÛÅ ÏÐÎÁËÅÌÛСтр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
