Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 92
Текст из файла (страница 92)
Проблема соответствий Поста В этом разделе начнется сведение неразрешимых вопросов о машинах Тьюринга к неразрешимым вопросам о "реальных вещах'*, т.е, обычных предметах, не имеющих отношения к абстрактным машинам Тьюринга. Начнем с проблемы, которая называется "проблемой соответствий Поста" (ПСП). Эта проблема по-прежнему довольно абстрактна, но она связана уже не с машинами Тьюринга, а с цепочками.
Наша цель — доказать неразрешимость этой проблемы, чтобы затем доказывать неразрешимость других проблем путем сведения ПСП к иим. Докажем неразрешимость'ПСП сведением Т.„к ней. Чтобы облегчить доказательство, рассмотрим вначале "модифицированную" версию ПСП, а потом сведем ее к исходной ПСП. Затем сведем Л„к модифицированной ПСП. Цепь этих сведений представлена на рис. 9.11. Поскольку известно, что исходная проблема 1,„неразрешима, можно сделать вывод, что ПСП также неразрешима. Рис.
9.!1. Цепь сведений в доказательстве неразрешимости проблемы соотееп1ствий Поста 9.4. ПРОВЛЕМА СООТВКТСТВИЙ ПОСТА 401 9.4.1. Определение проблемы соответствий Поста Экземпляр праблелгы соответствий Поста (ПСП) состоит из двух списков равной длины в некотором алфавите Х. Как правило, мы будем называть их списками А и В, и писать А = эгь ш„..., нз и В = хь хз, ..., хк при некотором целом к.
Для каждого э пара (н „х,) называется парой соответствующих эгепочек. Мы говорим, что экземпляр ПСП имеет решение, если существует последователь- ность из одного или нескольких целых чисел эн 1э, ..., 1, которая, если считать зти числа индексами цепочек и выбрать соответствующие цепочки из списков А и В, дает одну и ту же цепочку, те. или „... н, = ха ха ... х, . В таком случае последовательностын эи ..., 1 называется решающей последовательностью, или просто решением, данного экземпляра ПСП. Проблема соответствий Поста состоит в следующем. ° Выяснить, имеет ли решение данный экземпляр ПСП. Пример 9.13. Пусть Х = (О, 1), А и  — списки (рис.
9.12). Данный экземпляр ПСП имеет решение. Пусть, например, т =4, 1, = 2, !э = 1, 1э =! и 1э = 3, т.е, решающая последовательность имеет вид 2, 1, 1, 3. Для проверки записываются конкатенации соответствующих цепочек каждого из списков в порядке, задаваемом данной последовательностью, т.е. шли~ге~из = х,х~х,хэ = !01111!10. Отметим, что это решение — не единственное. Например, 2, 1, 1, 3,2, 1, 1, 3 также является решением. (:3 Рис. 9.12 Экэемпэлр!1СВ ПСП как язык Речь идет о вопросе, существует ли решение у экземпляра ПСП, поэтому данную проблему нужно представить в виде языка. Поскольку экземпляры ПСП могут иметь произвольные алфавиты, язык ПСП на самом деле есть множество цепочек над некоторым фиксированным алфавитом, которыми кодируются экземпляры ПСП.
Эти коды во многом напоминают коды машин Тьюринга с произвольными множествами состояний и ленточных символов, рассмотренные в разделе 9.!.2. Например, если экземпляр ПСП имеет алфавит, содержащий до 2 символов, то для каждого из этих символов можно использовать к-битный двоичный код. Поскольку каждый экземпляр ПСП имеет конечный алфавит, то некоторое к мо кно найти для каждого экземпляра. Следовательно, все экземпляры проблемы можно за- ГЛАВА 9. НБРАЗРЕШИМОСТЬ 402 кодировать с помощью алфавита из 3-х символов: О, 1 и "запятой", разделяющей цепочки.
Код начинается двоичной записью числа 1л и запятой за ней. Затем записывает- ся каждая из пар цепочек, в которых цепочки разделены запятыми, а символы закодированы 1-битнымн двоичными числами. Пример 9.14. Пусть, как и раньше, Х = !О, 1!, но теперь экземпляр проблемы представлен списками, как на рис. 9. 13.
Рис. 9.!3. Еще один экземлпяр ПСП В этом примере решения нет. Допустим, что экземпляр ПСП, представленный на ркс. 9.13, имеет решение, скажем, !н 1в ..., ! при некотором т > 1. Утверждаем, что б =!. При й = 2 цепочка, начинающаяся с и з = 011, должна равняться цепочке, которая начинается с х, = ! 1. Но это равенство невозможно, поскольку их первые символы — 0 и 1, соответственно. Точно так же невозможно, чтобы г, = 3, поскольку тогда цепочка, начинающаяся с и з = 101, равнялась бы цепочке, которая начинается с х, = 011.
Если 1, = 1, то две соответствующие цепочки из списков А и В должны начинаться так: А: 10... В: 101... Рассмотрим теперь, каким может бытыв Вариант Г, = 1 невозможен, поскольку никакая цепочка, начинающаяся с инли, =- 1010, не может соответствовать цепочке, которая начинается с х,х, = !01101; эти цепочки различаются в четвертой позиции. Вариант 1,=2 также невозможен, поскольку никакая цепочка, начинающаяся с ил,ю, = 10011, не может соответствовать цепочке, которая начинается с х~хз = 10111; они различаются в третьей позиции. 3. Возможен лишь вариант 1з = 3. При !з = 3 цепочки, соответствующие списку чисел 1, 3, имеют следующий вид. А: 10101... В: 10101! ...
Пока не видно, что последовательность 1, 3 невозможно продолжить до решения. Однако обосновать это несложно. Действительно, мы находимся в тех же условиях, в которых 9,4. ПРОВЛЕМА СООТВЕТСТВИЙ ПОСТА 403 были после выбора (, = 1. Цепочка нз списка В отличается от цепочки из списка А лишним символом 1 на конце. Чтобы избежать несовпадения, мы вынуждены выбирать б = 3, 14 = 3 и так далее.
Таким образом, цепочка нз списка А никогда не догонит цепочку из списка В, и решение никогда не будет получено. П 9.4.2. „Модифицированная" ПСП Свести А„к ПСП легче, если рассмотреть вначале промежуточную версию ПСП, которая называется модифицированной лробченой соответствий Поста, или МПСП. В модифицированной ПСП на решение накладывается дополнительное требование, чтобы первой парой в решении бьша пара первых элементов списков А и В.
Более формально, экземпляр МПСП состоит из двух списков А = н ь нь ..., нз и В =хь хь ..., хь и решением является последовательность из О или нескольких целых чисел гь 1ь ..., 1, при которой и'1илщг..зг, =х~хлхч...х, . Отметим, что цепочки обязательно начинаются парой (н ь х1), хотя индекс 1 даже не указан в качестве начального элемента решения. Кроме того, в отличие от ПСП, решение которой содержит хотя бы один элемент, решением МПСП может быть и пустая последовательность (когда и1 = х,). Однако такие экземпляры не представляют никакого нн- тереса и далее не рассматриваются.
~Хаотичные решения В примере 9.14 для анализа экземпляров ПСП используется широко распространенный метод. Рассматривается, какими могут быть часгличные решения, т.е. последова- тельности индексов 1ь 1„...„1„, для которых одна из цепочек н лзго...згь н х„х„...х„является префиксом другой, хотя сами цепочки не равны. Заметим, что если последовательность целых чисел является решением, то всякий префикс этой последовательности должен быть частичным решением. Поэтому понимание того, как выглядят частичные решения проблемы, позволяет определить, какими могут быть пол- ные решения.
Отметим, однако, что, поскольку ПСП неразрешима, не существует и алгоритма, позволяющего вычислять все частичные решения. Их может быть бесконечно много, а также, что гораздо хуже, если даже частичные решения ичиа...ич и хлх„...х„ведут к решению, разница их длин может быть сколь угодно большой. Пример 9.15. Списки, представленные на рнс.
9.12, можно рассматривать как экземпляр МПСП. Однако этот экземпляр МПСП не имеет решения. Для доказательства заметим, что всякое его частичное решение начинается с индекса 1, поэтому цепочки, образующие решение, должны начинаться следующим образом. А: 1... В; 111... 404 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ Следующим целым в решении не может быть 2 или 3, поскольку и згв и згз начинаются с 10, и поэтому при таком выборе возникнет несоответствие в третьей позиции. Таким образом, следующий индекс должен быть 1, и получаются такие цепочки. А: 11...
В: 111111... Эти рассуждения можно продолжать бесконечно. Только еше одно число 1 позволяет избежать несоответствия в решении. Но если все время выбирается индекс 1, то цепочка В остается втрое длиннее А, и цепочки никогда не сравняются. П Важным шагом в доказательстве неразрешимости ПСП является сведение МПСП к ПСП. Далее будет показано, что МПСП неразрешима, путем сведения Т„к МПСП. Тем самым будет доказана неразрешимость ПСП. Действительно, если бы она была разрешима, то можно было бы решить МПСП, а следовательно, и Е„. По данному экземпляру МПСП с алфавитом Х соответствукнций экземпляр ПСП строится следующим образом.
Вначале вводится новый символ ~, который помешается между символами цепочек экземпляра МПСП. При этом в цепочках списка А он следует за символами алфавита Х, а в цепочках списка  — предшествует им. Исключением является новая пара, которая строится по первой паре экземпляра МПСП; в этой паре есть дополнительный символ * в начале ив поэтому она может служить началом решения ПСП. К экземпляру ПСП добавляется также заключительная пара (э, ьэ). Она служит последней парой в решении ПСП, имитирукнцем решение экземпляра МПСП. Формализуем описанную конструкцию. Пусть дан экземпляр МПСП со списками А = и ь и в ..., иэ и В = хь хв ..., хь Предполагается, что символы * и 3 отсутствуют в алфавите Х данного экземпляра МПСП. Строится экземпляр ПСП со списками С =ум уь ..., уг,~ и 0 = зо зь ., ави следующим образом. 1. Для! = 1, 2, ..., /г положим у, равной в, с символом ь после каждого ее символа, а ; — равной х, с символом ь перед каждым ес символом.
2. ур = ~у, и св = -, т.е. нулевая пара выглядит так же, как первая, с той лишь разницей, что в начале цепочки из первого списка есть еще символ в. Отметим, что нулевая пара будет единственной парой экземпляра ПСП, в которой обе цепочки начинаются одним и тем же символом, поэтому всякое решение данного экземпляра ПСП должно начинаться с индекса О. 3. уы, = $ и хм, = ь9. Пример 9.1б.
Пусть рис. 9.12 изображает экземпляр МПСП. Тогда экземпляр ПСП, построенный с помощью описанных выше действий, представлен на рис. 9.14. П Теорема 9.17. МПСП сводится к ПСП. Доказательство. В основе доказательства лежит описанная выше конструкция. Допустим, что 1ь („..., 1„— решение данного экземпляра МПСП со списками А и В; тогда в1жчи;л...иг, = х,хчхи.,,х, . Если заменить каждую цепочку и соответствующей у и каж- 9.4.
ПРОБЛЕМА СООТВЕТСТВИИ ПОСТА 405 ДУЮ Х вЂ” СООтВЕтСтВУЮЩЕй г, тО ПОЛУЧатСЯ ДВЕ ПОЧТИ ОДИНаКОВЫЕ ЦЕПОЧКИ Угу,Уи...Уь, И г гига...г; . Разница между ними в том, что у первой не хватает " в начале, а у второй — в конце, т.е. "УСУсуа...У,„= г гага."гм" Рис. 9.14. Построение экземняяра ПСП но экземгмяру 'з4ПСП Однако Уе = *У, и ге = гь поэтомУ можно "РаспРавитьсЯ" с е в начале, изменив пеРвый индекс на О: УиЗ',~ям..т, = го чги.,.г, Для учета е в конце добавим индекс /с+ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
