dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 90
Текст из файла (страница 90)
9.3.4. Ïðîáëåìû, ñâÿçàííûå ñ îïèñàíèÿìè ÿçûêîâ â âèäåìàøèí ÒüþðèíãàСогласно теореме 9.11 все проблемы, связанные только с языками машин Тьюринга,неразрешимы. Некоторые из них интересны сами по себе. Например, неразрешимы следующие вопросы.1.Пуст ли язык, допускаемый МТ (ответ дают теоремы 9.9 и 9.3)?2.Конечен ли язык МТ?3.Регулярен ли язык, допускаемый МТ?4.Является ли язык МТ контекстно-свободным?Вместе с тем, теорема Райса не означает, что любая проблема, связанная с МТ, неразрешима. Например, вопросы о состояниях МТ, в отличие от вопросов о языке, могутбыть разрешимыми.Пример 9.12.
Вопрос о том, имеет ли МТ пять состояний, разрешим. Алгоритм, решающий его, просматривает код МТ и подсчитывает число состояний, встреченных в егопереходах.Еще один пример разрешимого вопроса — существует ли вход, при обработке которого МТ совершает более пяти переходов? Алгоритм решения становится очевидным,9.3.
ÍÅÐÀÇÐÅØÈÌÛÅ ÏÐÎÁËÅÌÛ, ÑÂßÇÀÍÍÛÅ Ñ ÌÀØÈÍÀÌÈ ÒÜÞÐÈÍÃÀСтр. 399399если заметить, что, когда МТ делает пять переходов, она обозревает не более девяти клеток вокруг начальной позиции головки. Поэтому можно проимитировать пять переходовМТ на любом из конечного числа входов, длина которых не более девяти. Если все этиимитации не достигают останова, то делается вывод, что на любом входе данная МТ совершает более пяти переходов. 9.3.5. Óïðàæíåíèÿ ê ðàçäåëó 9.39.3.1.(∗) Покажите, что множество кодов машин Тьюринга, допускающих все входы,которые являются палиндромами (возможно, наряду с другими входами), неразрешимо.9.3.2.Большая Компьютерная Корпорация для увеличения сократившегося объемапродаж решила выпустить высокотехнологичную модель машины Тьюринга подназванием МТЗС, оснащенную звонками и свистками.
В основном МТЗС совпадает с обычной МТ, за исключением того, что каждое состояние этой машиныотмечено либо как “состояние-звонок”, либо как “состояние-свисток”. Как только МТЗС попадает в новое состояние, то, в зависимости от его типа, она либозвенит, либо свистит. Докажите, что проблема определения, свистнет ли когданибудь данная МТЗС M при данном входе w, неразрешима.9.3.3.Покажите, что язык кодов МТ, которые, начиная с пустой ленты, в конце концовзаписывают где-либо на ней символ 1, неразрешим.9.3.4.(!) В соответствии с теоремой Райса известно, что каждый из следующих вопросов неразрешим:а) содержит ли L(M) хотя бы две цепочки?б) бесконечен ли L(M)?в) является ли язык L(M) контекстно-свободным?г) (∗) верно ли, что L(M) = (L(M))R?Являются ли они рекурсивно перечислимыми или не-РП?9.3.5.(!) Пусть язык L состоит из троек (M1, M2, k), образованных парой кодов МТ ицелым числом, для которых L(M1) I L(M2) содержит не менее, чем k цепочек.Покажите, что L является РП, но не рекурсивным.9.3.6.Покажите, что следующие вопросы разрешимы:а) (∗) множество кодов МТ M, которые, имея в начальный момент пустуюленту, в конце концов записывают на ней некоторый непустой символ.Указание.
Если M имеет m состояний, рассмотрите первые m + 1 совершаемых ею переходов;б) (!) множество кодов МТ, которые никогда не совершают сдвиг влево;400Стр. 400ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜв) (!) множество пар (M, w), для которых МТ M при обработке входа w не обозревает никакую клетку на ленте более одного раза.9.3.7.(!) Покажите, что следующие проблемы не являются рекурсивно-перечислимыми:а) (∗) множество пар (M, w), для которых МТ M при обработке входа w не останавливается;б) множество пар (M1, M2), для которых L(M1) I L(M2) = ∅;в) множество троек (M1, M2, M3), для которых L(M1) = L(M2) L(M3), т.е. языкпервой машины — это конкатенация языков двух других МТ.9.3.8.(!!) Ответьте, является ли каждое из следующих множеств рекурсивным, РП, ноне рекурсивным, или не-РП:а) (∗) множество кодов всех МТ, останавливающихся на любом входе;б) множество кодов всех МТ, которые не останавливаются ни на каком входе;в) множество кодов всех МТ, останавливающихся хотя бы на одном входе;г) (∗) множество кодов всех МТ, которые не останавливаются хотя бы на одном входе.9.4.
Ïðîáëåìà ñîîòâåòñòâèé ÏîñòàВ этом разделе начнется сведение неразрешимых вопросов о машинах Тьюринга кнеразрешимым вопросам о “реальных вещах”, т.е. обычных предметах, не имеющих отношения к абстрактным машинам Тьюринга. Начнем с проблемы, которая называется“проблемой соответствий Поста” (ПСП). Эта проблема по-прежнему довольно абстрактна, но она связана уже не с машинами Тьюринга, а с цепочками. Наша цель — доказатьнеразрешимость этой проблемы, чтобы затем доказывать неразрешимость других проблем путем сведения ПСП к ним.Докажем неразрешимость ПСП сведением Lu к ней.
Чтобы облегчить доказательство,рассмотрим вначале “модифицированную” версию ПСП, а потом сведем ее к исходнойПСП. Затем сведем Lu к модифицированной ПСП. Цепь этих сведений представлена нарис. 9.11. Поскольку известно, что исходная проблема Lu неразрешима, можно сделатьвывод, что ПСП также неразрешима.АлгоритмМПСПАлгоритмПСПРис. 9.11. Цепь сведений в доказательстве неразрешимостипроблемы соответствий Поста9.4. ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀСтр. 4014019.4.1.
Îïðåäåëåíèå ïðîáëåìû ñîîòâåòñòâèé ÏîñòàЭкземпляр проблемы соответствий Поста (ПСП) состоит из двух списков равнойдлины в некотором алфавите Σ. Как правило, мы будем называть их списками A и B, иписать A = w1, w2, …, wk и B = x1, x2, …, xk при некотором целом k.
Для каждого i пара(wi, xi) называется парой соответствующих цепочек.Мы говорим, что экземпляр ПСП имеет решение, если существует последовательность из одного или нескольких целых чисел i1, i2, …, im, которая, если считать эти числаиндексами цепочек и выбрать соответствующие цепочки из списков A и B, дает одну и туже цепочку, т.е.
wi1 wi2 … wim = xi1 xi2 … xim. В таком случае последовательность i1, i2, …, imназывается решающей последовательностью, или просто решением, данного экземпляраПСП. Проблема соответствий Поста состоит в следующем.• Выяснить, имеет ли решение данный экземпляр ПСП.Пример 9.13. Пусть Σ = {0, 1}, A и B — списки (рис. 9.12). Данный экземпляр ПСПимеет решение. Пусть, например, m = 4, i1 = 2, i2 = 1, i3 = 1 и i4 = 3, т.е. решающая последовательность имеет вид 2, 1, 1, 3.
Для проверки записываются конкатенации соответствующих цепочек каждого из списков в порядке, задаваемом данной последовательностью, т.е. w2w1w1w3 = x2x1x1x3 = 101111110. Отметим, что это решение — не единственное. Например, 2, 1, 1, 3, 2, 1, 1, 3 также является решением. Список AСписок Biwixi11111210111103100Рис. 9.12. Экземпляр ПСПÏÑÏ êàê ÿçûêРечь идет о вопросе, существует ли решение у экземпляра ПСП, поэтому даннуюпроблему нужно представить в виде языка. Поскольку экземпляры ПСП могут иметьпроизвольные алфавиты, язык ПСП на самом деле есть множество цепочек над некоторым фиксированным алфавитом, которыми кодируются экземпляры ПСП.
Эти коды во многом напоминают коды машин Тьюринга с произвольными множествами состояний и ленточных символов, рассмотренные в разделе 9.1.2. Например, если экземпляр ПСП имеет алфавит, содержащий до 2k символов, то для каждого из этихсимволов можно использовать k-битный двоичный код.Поскольку каждый экземпляр ПСП имеет конечный алфавит, то некоторое k можнонайти для каждого экземпляра. Следовательно, все экземпляры проблемы можно за402Стр. 402ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜкодировать с помощью алфавита из 3-х символов: 0, 1 и “запятой”, разделяющей цепочки.
Код начинается двоичной записью числа k и запятой за ней. Затем записывается каждая из пар цепочек, в которых цепочки разделены запятыми, а символы закодированы k-битными двоичными числами.Пример 9.14. Пусть, как и раньше, Σ = {0, 1}, но теперь экземпляр проблемы представлен списками, как на рис. 9.13.Список AСписок Biwixi1101012011113101011Рис. 9.13. Еще один экземпляр ПСПВ этом примере решения нет. Допустим, что экземпляр ПСП, представленный нарис. 9.13, имеет решение, скажем, i1, i2, …, im при некотором m ≥ 1. Утверждаем, чтоi1 = 1. При i1 = 2 цепочка, начинающаяся с w2 = 011, должна равняться цепочке, котораяначинается с x2 = 11.
Но это равенство невозможно, поскольку их первые символы — 0 и1, соответственно. Точно так же невозможно, чтобы i1 = 3, поскольку тогда цепочка, начинающаяся с w3 = 101, равнялась бы цепочке, которая начинается с x3 = 011.Если i1 = 1, то две соответствующие цепочки из списков A и B должны начинаться так:A: 10…B: 101…Рассмотрим теперь, каким может быть i2.1.Вариант i2 = 1 невозможен, поскольку никакая цепочка, начинающаяся с w1w1 = 1010,не может соответствовать цепочке, которая начинается с x1x1 = 101101; эти цепочкиразличаются в четвертой позиции.2.Вариант i2 = 2 также невозможен, поскольку никакая цепочка, начинающаяся сw1w2 = 10011, не может соответствовать цепочке, которая начинается с x1x2 = 10111;они различаются в третьей позиции.3.Возможен лишь вариант i2 = 3.При i2 = 3 цепочки, соответствующие списку чисел 1, 3, имеют следующий вид.A: 10101…B: 101011…Пока не видно, что последовательность 1, 3 невозможно продолжить до решения.
Однако обосновать это несложно. Действительно, мы находимся в тех же условиях, в которых9.4. ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀСтр. 403403были после выбора i1 = 1. Цепочка из списка B отличается от цепочки из списка A лишним символом 1 на конце. Чтобы избежать несовпадения, мы вынуждены выбиратьi3 = 3, i4 = 3 и так далее.
Таким образом, цепочка из списка A никогда не догонит цепочкуиз списка B, и решение никогда не будет получено. 9.4.2. “Ìîäèôèöèðîâàííàÿ” ÏÑÏСвести Lu к ПСП легче, если рассмотреть вначале промежуточную версию ПСП, которая называется модифицированной проблемой соответствий Поста, или МПСП. В модифицированной ПСП на решение накладывается дополнительное требование, чтобы первойпарой в решении была пара первых элементов списков A и B. Более формально, экземплярМПСП состоит из двух списков A = w1, w2, …, wk и B = x1, x2, …, xk, и решением являетсяпоследовательность из 0 или нескольких целых чисел i1, i2, …, im, при которойw1wi1wi2…wim = x1xi1xi2…xim.Отметим, что цепочки обязательно начинаются парой (w1, x1), хотя индекс 1 даже неуказан в качестве начального элемента решения.
Кроме того, в отличие от ПСП, решениекоторой содержит хотя бы один элемент, решением МПСП может быть и пустая последовательность (когда w1 = x1). Однако такие экземпляры не представляют никакого интереса и далее не рассматриваются.×àñòè÷íûå ðåøåíèÿВ примере 9.14 для анализа экземпляров ПСП используется широко распространенный метод. Рассматривается, какими могут быть частичные решения, т.е.
последовательности индексов i1, i2, …, ir, для которых одна из цепочек wi1wi2…wir и xi1xi2…xir является префиксом другой, хотя сами цепочки не равны. Заметим, что если последовательность целых чисел является решением, то всякий префикс этой последовательности должен быть частичным решением. Поэтому понимание того, как выглядят частичные решения проблемы, позволяет определить, какими могут быть полные решения.Отметим, однако, что, поскольку ПСП неразрешима, не существует и алгоритма, позволяющего вычислять все частичные решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
