Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 93
Текст из файла (страница 93)
Посколькууин = 3, ахи, = *3, получим: УчКУ2 ''У Уин гег гм..г гин. Итак, показано, что последовательность О, 1ь 1„..., 1, й т 1 — решение экземпляра ПСП. Теперь докажем обратное, т.е. если построенный экземпляр ПСП имеет решение, то исходный экземпляр МПСП также имеет решение. Заметим, что решение данного экземпляра ПСП должно начинаться индексом 0 и заканчиваться индексом 4с + 1, поскольку только в нулевой паре цепочки ур и гс начинаются и только в ф + 1)-й паре цепочки уси и гьп оканчиваются одним и тем же символом. Таким образом, решение экземпляра ПСП можно записать в виде О, зь 1г, ..., 1, А + ! .
Мы утверждаем, что 1ь 1г, ..., 1 есть решение экземпляра МПСП. Действительно, из цепочки усу„уи...у уи„можно удалить все символы е и символ 3 в конце. В результате получим цепочку и ~зсии „...и . Точно так же, удалив символы * и символ 3 из цепочки г,гиги...г;„хмь получим х,хи ха ...х, . Поскольку Учу'Р " У, Уи ~ = го- Д ".г,,ги ~ получаем: и'~ и'изин" . и', Итак, решение экзеыпляра ПСП содержит в себе решение экземпляра МПСП. Теперь ясно, что конструкция, описанная перед данной теоремой, представляет собой алгоритм, который переводит экземпляр МПСП, имеющий решение, в экземпляр ПСП, ГЛАВА 9. НЕРАЗРЕШИМОСТЬ 406 также имеющий решение, а экземпляр МПСП, не имеющий решения, — в экземпляр ПСП, не имеющий решения.
Таким образом, МПСП сводится к ПСП, а это означает, что ш разрешимости ПСП следовала бы разрешимость МПСП. С) 9.4.3. Завершение доказательства неразрешимости ПСП Завершим цепь сведений (см. рис, 9.11), сведя В„к МПСП. По заданной паре (М, эг) строится экземпляр МПСП (А, В), имеющий решение тогда и только тогда, когда МТ М допускает вход и. Основная идея состоит в том, что частичные решения экземпляра МПСП (А, В) имитируют обработку входа ш машиной лт.
Частичные решения будут состоять из цепочек, которые являются префиксами последовательности МО лт' Фа~да,дазд..., где а~ — начальное МО лт' при входной цепочке в и а )- а, для всех ~'. Цепочка из списка В всегда на одно МО впереди цепочки из списка А, за исключением ситуации, когда М попадает в допускающее состояние. В этом случае используются специальные пары, позволяющие списку А "догнать" список В и в конце концов выработать решение. Однако если машина ие попадает в допускающее состояние, то эти пары не могут быть использованы, и проблема не имеет решения. Для того чтобы упростить построение эюемпляра МПСП, воспользуемся теоремой 8.12, согласно которой можно считать, что МТ никогда не печатает пробел и ее головка не сдвигается левее исходного положения.
Тогда МО машины Тьюринга всегда будет цепочкой вида сиЩ где а и Р— цепочки непустых символов на ленте, а д — состояние. Однако тогда, когда головка обозревает пробел непосредственно справа от а, позволим цепочке )З быть пустой вместо того, чтобы помещать пробел справа от состояния. Таким образом, символы цепочек а и Д будут в точности соответствовать содержи- мому клеток, в которых записан вход, а также всех тех клеток справа, в которых головка уже побывала. Пусть М = (Д, Х, Г, В, дм В, Е) — машина Тьюринга, удовлетворяющая условиям теоремы 8.12, и ж — входная цепочка из Х . По ним строится эюемпляр МПСП следукнцим образом. Чтобы понять, почему пары выбираются пары именно так, а не иначе, нужно помнить, что нам нужно, чтобы первый список всегда на одно МО отставал от второго, если только Мне попадает в допускающее состояние.
1. Первая пара имеет следующий вид. Список А Список В Ф Д9ои4 В соответствии с правилами МПСП эта пара — первая в любом решении. С нее начинается имитация М на входе ч. Заметим, что в начальный момент список В опе- режает список А на одно полное МО. 9.4. ПРОБЛЕМА СООТВЕТСТВИЙ ПОСТА 407 2. Ленточные символы и разделитель № могут быть добавлены в оба списка. Пары Список А Список В Х Х для каждого Хиз Г позволяют "копировать" символы, не обозначающие состояния.
Выбирая такие пары, можно одновременно и удлинить цепочку списка А до соответствующей цепочки списка В, и скопировать часть предыдущего МО в конец цепочки списка В. Это поможет нам записать в конец цепочки списка В следующее МО в последовательности переходов М. 3.
Для имитации перехода И применяются специальные пары. Для всех д из Д- г" (т.е. состояние д не является допускающим),р из Д иХ У, азиз Г есть следующие пары. Список А Список В цХ Ур еслиф),Х) =~р, У,В) ЛуХ рему если оГд, Х) = (р, У, Е); 2 — любой ленточный символ г)№ Ур№ если фд, В) =(р, У,В) А9№ АУ№ если фд, В) = ф, У, Е); У вЂ” любой ленточный символ Как и в пункте 2, эти пары позволяют добавить к цепочке В следующее МО, дописывая цепочку А таким образом, чтобы она соответствовала цепочке В. Однако эти пары используют состояние для определения, как нужно изменить текущее МО, чтобы получить следующее. Этн изменения — новое состояние, ленточный символ и сдвиг головки — отображаются в МО, которое строится в конце цепочки В, 4. Если МО, которое находится в конце цепочки В, содержит допускающее состояние, нужно сделать частичное решение полным.
Для этого добавляются "МО", которые в действительности не являются МО машины М а отображают ситуацию, при которой в допускающем состоянии разрешается поглощать все ленточные символы по обе стороны от головки. Таким образом, если д — допускающее состояние, то для всех ленточных символов Хи У существуют следующие пары.
Список А Список В х)у д Хд ) ду д 5. Наконец, если допускающее состояние поглотило все ленточные символы, то оно остается в одиноиестве как последнее МО в цепочке В. Таким образом, раэиосгпь цепочек (суффикс цепочки В, который нужно дописать к цепочке А для того, чтобы она соответствовала В) есть ф, и для завершения решения используется последняя пара. ГЛАВА 9. НЕРАЗРЕШИМОСТЬ 408 Список А Список В 9№№ № В дальнейшем пары этих пяти типов называются парами из правила 1, из правила 2 я так далее. Пример 9.18. Преобразуем в экземпляр МПСП машину стаблицей В 9, ~йь О) б(Е, 1) (дз, О,Ц Ф (92 1 В) Вэ (Вь О, Е) (9п О, г) в входной цепочкой и = 01.
Чтобы упростить построение, заметим, что М никогда не печатает пробел В, и его не будет ни в одном МО. Поэтому все пары с пустым символом В опускаются. Полный список пар с указанием их происхождения представлен на рис. 9.15. Отметим, что М допускает входную цепочку 01 в результате следующей последова- тельиости переходов. д>01 1- !п 1 1- 109у 1- 1дрО! 1- 9~101 Рассмотрим последовательность частичных решений, которая имитирует эти вычисления М и в конце концов приводит к решению. Начать нужно с первой пары, как того требует всякос решение МПСП. В: №9,0!№ Для того чтобы частичное решение можно было продолжить, следующая цепочка из списка А должна быть префиксом разности о~01№.
Поэтому следующей парой должна быть (9~0, 19~). Это одна из пар, имитирующих переходы, полученная по правилу 3. Итак, получаем следующее частичное решение. А: №9,0 В: №9,01№!9, Теперь можно продолжить частичное решение, используя "копирующие" пары из прави- ла 2 до тех пор, пока не дойдем до состояния во втором МО. Тогда частичное решение примет такой вид. А: №9,01№1 В: №Ф01№19э!№1 9.4. ПРОБЛЕМА СООТВЕТСТВИЙ ПОСТА 409 и = ((дь Вь д,), (О, 1), (О, 1, В), В, дь В, (д,)) ~д„В) (дь 1, Е) (Вь О, В) Для имитации перехода тут снова можно использовать пару из правила 3. Подходящей является пара (Чг!, ОЧ,), и в результате получается следующее частичное решение.
А: №Ч,О!№!Ч,! В: №Ч,О!№!Ч,!№!ОЧ, Правило Список А Список В Источник №Ч,О!№ (2) (3) (4) Чз Чз Чз Чз Чз Рис. 9 У5. Экземпляр МПСП, построенный по МТ М и слову ге из примера 9 УВ Теперь можно было бы использовать пары из правила 3 и скопировать следующие три символа №, 1 и О, Однако это решение было бы ошибочным, поскольку следующий переход М сдвигает головку влево, и символ О, стоящий непосредственно перед состоянием, потребуется в следующей паре из правила 3. Поэтому копируются лишь два следующих символа.
А: №Ч,О!№!Ч,1№1 В: №Ч,01№ ! Ч,1 №10Ч,№1 410 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ Ч,О ОЧ, 1№ 1суг1№ ОЧ,№ 1суг№ ОЧгО !ЧгО Чг1 Чг№ ОЧ,О ОЧ,1 1Ч,О !Ч,! ОЧ, !Чз Ч,О Чз! 1Чг Ч,ОО Чг10 Ч,О!№ Чг1 1№ Ч,ОО№ Ч,!О№ ОЧ, ОЧ,№ б(Чь О) ы (Чг, 1, УУ) б(Ч,,1) =(Ч„О,Ц Жуь 1) = (Ч, О, Ц б(Чь В) =(Ч,),У) б(Чь В) ы (Ч, 1, У) 4Ч,, 0) = (Чз, О, В) б(Ч„О) = (Ч,, О, Ь) ~Чг, !) = (Чь О, УУ) ~Чг, В) = (Чги О, В) Подходящей парой из правила 3 является (Одг№, дг01№), и получается новое частич- ное решение. А; №д~01№1д~1№10уг№ В: №д О!№!д,!№10д,№!д,О!№ Используя теперь еще одну пару (! д,О, д,10) из правила 3, приходим к допусканию. А: №д,О!№1д !№!Од,№!д О В; №дг01№1дг1№!Од,№1дгО 1№дг!0 Теперь, с помощью пар из правила 4 в МО исключаются все символы, кроме дг. Для правильного копирования символов нужны также пары из правила 2.
Частичное решение продолжается до следующсго. А: №дг01№!дг! №1Одг№)дг01№дг101№дг01№дг1№ В: №дг0 ! № ! дг1№ ! Одг№ 1дгО! №дг101 №дгО ! №дг! №дг№ Теперь в МО находится лишь дг. Чтобы завершить решение, можно использовать пару (дг№№, №) из правила 5. А: №дг01№1дг1№10д,№! дгО! №дг1 О! №дг01№д,1№д,№№ В: №дг01№1дг!№10дг№1дг01№дг101№дг01№дг1№дг№№ (3 Теорема 9.19. Проблема соответствий Поста неразрешима. Доказательство.
Цепь сведений, представленная на рис. 9.! 1, почти завершена. Сведение МПСП к ПСП было показано в теореме 9.17. В данном разделе приведена конструкция, позволяющая свести Е„к МПСП. Таким образом, для завершения доказательства неразрешимости ПСП покажем, что эта конструкция корректна, т.е. ° М допускает ге тогда и только тогда, когда построенный экземгшяр МПСП имеет решение. (Оеобходимослгь) Основную идею подсказывает пример 9.18. Если и принадлежит ЦМ), то можно проимитировать работу М со входом ге, начав с пары из правила 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
