Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 91
Текст из файла (страница 91)
Предположим, что нам дана цепочка М, представляющая МТ с пустым языком. Проверяя различные входы М, мы можем никогда не найти такого„который М допускает, но при этом не сможем и быть уверенными в том, что такого входа нет среди еше непроверенных. Поэтому М никогда не сможет быть допущена, даже если и должна. Свойство называется н~ривиадьным, если оно либо пустое (т.е. никакой язык вообще ему не удовлетворяет), либо содержит все РП-языки.
В противном случае свойство назы- вается негнривиальным. 9.3. НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ, СВЯЗАННЫЕ С МАШИНАМИ ТЬЮРИНГА 397 ° Отметим, что пустое свойство З и свойство быть пустым языком — не одно и то же. Мы не можем распознать множество языков так, как сами эти языки. Причина в том, что обычный бесконечный язык нельзя записать в виде цепочки конечной длины, кото- рая может быть входом некоторой МТ.
Вместо этого мы должны распознавать машины Тьюринга, которые допускают эти языки. Код самой МТ конечен, даже если язык, который она допускает, бесконечен. Таким образом, если Р— это свойство РП-языков, то л,р — множество кодов машин Тьюринга М, языки ЦМ) которых принадлежат Р.
Говоря о разрешимости свойства Р, мы имеем в виду разрешимость языка (.~. Теорема 9.11 (теорема Райса). Всякое нетривиальное свойство РП-языков нераз- решимо. Доказательство. Пусть Р— нетривиальное свойство РП-языков. Вначале допустим, что пустой язык Я не принадлежит Р; противоположный случай рассмотрим позже. Поскольку Р— нетривиально, должен существовать непустой язык А, принадлежащий Р. Пусть Ме обозначает МТ, допускающую Л. Сведем Ь„к(.т и этим докажем, что язык Т, неразрешим, поскольку Т., неразрешим. Алгоритм сведения получает на вход пару (М, и ) и выдает некоторую МТ М'.
Структура М'представлена на рис. 9.10. Если М не допускает те, то (,(М') есть Я, и ЦМ') = („если М допускает и. Допустить Рис. 9,/Ц Схема М' для доказательства теоремы Ройса М' — двухленточная МТ, Одна лента используется для моделирования работы М со входом те. Напомним, что алгоритм сведения получает на вход пару (М, и) и может использовать ее для построения переходов М( Таким образом, имитация М со входом и "встроена" в М; которой не нужно считывать с ленты переходы М.
Вторая лента М' используется для моделирования работы Мс с цепочкой х, входной для М'. Еще раз отметим, что переходы Ме известны алгоритму сведения и могут быть "встроены" в переходы М'. По построению МТ М' должна выполнять сле- дующие операции. 1. Имитировать работу Мсо входом и. Отметим, что в не является входом М( М'записывает Ми и на одну из своих лент и имитирует МТ Сна этой паре, как в доказательстве теоремы 9.8. 398 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ 2. Если М не допускает и, то М'больше ничего не делает, т.е.
не допускает любой свой вход х, поэтому Е(М') = Я. Мы предположили, что О не содержится в свойстве Р, поэтому код М'не принадлежит Е 3. Если М допускает зг„то М' начинает имитацию Мс на своем собственном входе х. Таким образом, М'допускает именно язык 2,. Поскольку 1. принадлежит Р, то код М' принадлежит 1 . Как видим, построение М' по М и н можно провести в соответствии с некоторым алгоритмом. Поскольку этот алгоритм преврашает (М, н) в М; которая принадлежит 2 то- гда н только тогда, когда (М, и ) принадлежит 2„, этот алгоритм представляет собой све- дение 2., к 2.~ и доказывает неразрешимость свойства Р. Для завершения доказательства нужно еше рассмотреть вариант, когда О принадлежит Р.
Для этого рассмотрим дополнение Р свойства Р, т.е. множество РП-языков, не обладающих свойством Р. Из описанных выше рассуждений следует, что свойство Р неразрешимо. Однако поскольку всякая МТ допускает некоторый РП-язык, то 1р, т.е. множество (кодов) машин Тьюринга, не допускаюших языки из Р, совпадает с 1 р множеством МТ, допускаюших языки из Р. Предположим, что язык 2, разрешим. Тогда 2 также должен быть разрешимым, поскольку дополнение рекурсивного языка рекурсивно (теорема 9.3). П 9.3.4. Проблемы, связанные с описаниями языков в виде машин Тьюринга Согласно теореме 9.11 все проблемы, связанные только с языками машин Тьюринга, неразрешимы.
Некоторые из них интересны сами по себе. Например, неразрешимы сле- дуюшие вопросы, !. Пуст ли язык, допускаемый МТ (ответ дают теоремы 9.9 и 9.3)? 2. Конечен ли язык МТ? 3. Регулярен ли язык, допускаемый МТ? 4. Является ли язык МТ контекстно-свободным? Вместе с тем, теорема Райса не означает, что любая проблема, связанная с МТ, неразрешима. Например, вопросы о состояниях МТ, в отличие от вопросов о языке, могут быть разрешимыми.
Пример 9.12. Вопрос о том, имеет ли МТ пять состояний, разрешим. Алгоритм, решаюший его, просматривает код МТ и подсчитывает число состояний, встреченных в его переходах. Еше один пример разрешимого вопроса — сушествует ли вход, при обработке которого МТ совершает более пяти переходов? Алгоритм решения становится очевидным, 9.3. НЕРАЗРЕШИМЫЕ ПРОБЛЕМЪ1, СВЯЗАННЫЕ С МАШИНАМИ ТЬЮРИНГА 399 если заметить, что, когда МТ делает пять переходов, оиа обозревает не более девяти клеток вокруг начальной позиции головки. Поэтому можно проимитнровать пять переходов МТ на любом из конечного числа входов, длина которых не более девяти. Если все эти имитации не достигают останова, то делается вывод, что на любом входе данная МТ совершает более пяти переходов.
СЗ 9.3.5. Упражнения к разделу 9.3 9.3.1. (в) Покажите, что множество кодов машин Тьюринга, допускающих все входы, которые являются палиндромами (возможно, наряду с другими входами), нераз- решимо. 9.3.2. Большая Компьютерная Корпорация для увеличения сократившегося объема продаж решила выпустить высокотехнологичную модель машины Тьюринга под названием МТЗС, оснащенную зввлкаии и свистками. В основном МТЗС совпадает с обычной МТ, за исключением того, что каждое состояние этой машины отмечено либо как "состояние-звонок", либо как "состояние-свисток". Как только МТЗС попадает в новое состояние, то, в зависимости от его типа, она либо звенит, либо свистит.
Докажите, что проблема определения, свистнет ли когданибудь данная МТЗС М при данном входе ю, неразрешима. 9.3.3. Покажите„что язык кодов МТ, которые, начиная с пустой ленты, в конце концов записывают где-либо на ней символ 1, неразрешим. 9.3.4. (!) В соответствии с теоремой Райса известно, что каждый из следующих вопросов неразрешим: а) содержит ли ЦМ) хотя бы две цепочки? б) бесконечен ли ЦМ)? в) является ли язык ЦМ) контекстно-свободным? г) (в) верно ли, что ЦМ) = (Б(М)) ? Являются ли онн рекурсивно перечислимыми или не-РП? 9.3.5. (!) Пусть язык Б состоит из троек (Мь Мл к), образованных парой кодов МТ и целым числом, для которых ЦМ,)П ЦМз) содержит не менее, чем к цепочек. Покажите, что Б является РП, но не рекурсивным.
9.3.6. Покажите, что следующие вопросы разрешимы: а) (в) множество кодов МТ М, которые, имея в начальный момент пустую ленту, в конце концов записывают на ней некоторый непустой символ. Указание. Если М имеет т состояний, рассмотрите первые т + 1 совершае- мых ею переходов; б) (!) множество кодов МТ, которые никогда не совершают сдвиг влево; ГЛАВА 9.
НЕРАЗРЕШИМОСТЬ 400 в) (1) множество пар (М, и), для которых МТ М при обработке входа и ие обо- зревает никакую клетку на ленте более одного раза. 9.3.7. (1) Покажите, что следующие проблемы не являются рекурсивно-перечислимыми; а) (ь) множество пар (М, зо), для которых МТ М при обработке входа зе не оста- навливается; б) множество пар (Мн М,), для которых ЦМ1) 1) ЦМ ) = И; в) множество троек (Мь Ми Мз), для которых ЦМ|) = ЦМз) ЦМз), т.е. язык первой машины — это конкатенация языков двух других МТ.
9.3.8. (11) Ответьте, является ли каждое из следующих множеств рекурсивным, РП, но не рекурсивным, или не-РП: а) (и) множество кодов всех МТ, останавливающихся на любом входе; б) множество кодов всех МТ, которые не останавливаются ни на каком входе; в) множество кодов всех МТ, останавливающихся хотя бы на одном входе; г) (в) множество кодов всех МТ, которые ие останавливаются хотя бы на од- ном входе. 9.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
