Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 79
Текст из файла (страница 79)
Теорема 8.!О. Время, необходимое одноленточной МТ Ф для имитации и переходов lс-ленточной МТ М, есть О(п~). Доказательство. После и переходов машины А7 головочные маркеры не могут быть разделены более, чем 2п клетками. Таким образом, если У стартует на крайнем слева маркере, ей нужно сдвинуться не более, чем на 2п клеток вправо, чтобы найти все головочные маркеры. Затем ей нужно совершить проход влево, изменяя содержимое лент М и сдвигая головочные маркеры вправо или влево, если необходимо.
Выполнение этого требует не более 2п сдвигов влево, плюс не более 2)г переходов для изменения направления движения и записи маркера Х в клетку справа (когда головка М сдвигается вправо). Таким образом, число переходов Ф, необходимых для имитации одного из первых п переходов, не более 4п + 27с Поскольку )г — константа, не зависящая от числа имитируемых переходов, это чийло переходов есть 0(п).
Имитация а переходов требует времени не более, чем в и рвз больше, т.е. 0(п ). 350 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА ~' 8.4.4. Недетерминированные машины Тьюринга Недемерминираванная машина Тьюринга (НМТ) отличается от изученных нами детерминированных тем, что ее д(г/, Х) для каждого состояния г/ и ленточного символа Х представляет собой множество троек ((/и Ун 1),), (/,, У,, В,), ..., (/и Кн /3„) ), гле /г — натуральное число.
НМТ может выбирать на каждом шаге любую из троек для следующего перехода. Она не может, однако, выбрать состояние из одной тройки, ленточный символ из другой, а направление из какой-нибудь еще. Язык, допускаемый НМТ М, определяется по аналогии с другими недетерминированными устройствами, вроде НКА или МП-автоматов.
Таким образом, М допускает вход и, если существует некоторая последовательность выборов переходов, ведущая из начального МО с и ва входе в МО с допускающим состоянием, Существование других выборов, которые не ведунг в допускающее состояние, не имеет значения, как и для НКА или МП-автоматов, Недетерминированные МТ допускают те же языки, что и детерминированные (или ДМТ, если нам нужно подчеркнуть их детерминированность).
Доказательство основано на том, что для любой НМТ Мн можно построить ДМТ Мд, которая исследует конфигурации, достигаемые Мн с помощью любой последовательности переходов. Если Ма находит хотя бы одно МО с допускающим состоянием, то сама переходит в допускающее состояние. Ма должна помешать новые МО в очередь, а не в магазин, чтобы после некоторого конечного времени были проимитнрованы все последовательности длиной до /г (/г = 1, 2, ...). Теорема 8.11. Если Мн — недетерминированная машина Тьюринга, то существует детерминированная машина Тьюринга Мгн у которой /(Мо) = ь(Мн). Доказательство.
Построим Ма в виде многоленточной МТ, общий вид которой представлен на рис. 8.18. Первая лента Мр хранит последовательность МО Мн, включая состояние Мн. Одно МО Мн отмечено как "текущее"; следующие за ним МО должны быть исследованы после него. На рис. 8.18 третье МО отмечено символом х вместе с разделителем МΠ— символом ~. Все МО слева от текущего уже исследованы, и в дальнейшем их можно игнорировать. Для обработки текущего МО машина Ма совергпает следующие действия. 1. Мп проверяет состояние и обозреваемый символ текущего МО.
Информация о том, какие выборы перехода есть у Мн лля каждого состояния и символа, хранится в конечном управлении Мо. Если состояние в текущем МО является допускающим, то Мн допускает и прекращает имитацию. 2, Если состояние в текущем МО не допускающее, а пара состояние-символ имеет /г переходов, то Мн использует свою вторую ленту для копирования МО и создания 1 копий этого МО в конце очереди МО на ленте 1. 3. Мп изменяет каждое из этих /г МО в соответствии с /г различными выборами переходов, которые есть у Мн из текущего МО. 8нй РАСШИРЕНИЯ БАЗОВОЙ МАШИНЫ ТЬЮРИНГА 851 4. М> возвращается к отмеченному (текутцему) МО, удаляет отметку и перемешает ее на следующее МО справа.
Цикл повторяется с шага !. Очередь МО Рабочая лента Рис 8.!В. Илиоиоиил гглтТ о помощею ДМТ Очевидно, что имитация точна в том смысле, что Л(о допускает только тогда, когда находит, что Л(п может перейти в допускающее МО. Однако нужно обосновать, что если !то попадает в допускающее МО после и переходов, то Лто в конце концов породит это МО в качестве текущего и допустит.
Предположим, что тп есть максимальное число выборов у Лтп в любой конфигурации. Тогда существует одно начальное МО М,т не более пт МО, достижимых за 1 шаг„не более и МО, достижимых за 2 шага, и т.д. Таким образом, после п переходов Мп может 2 достичь не более ! ч- т ч- и' ч- ...ч. пт" МО, что не превышает юп".
Порядок, в котором Мо исследует МО Лтм называется "поиск в ширину" ("Ьгеабйт йга"), т.е. она исследует все МО, достижимые за О переходов (начальное МО), затем все МО, достижимые за ! переход, за 2 перехода, и т.д. В частности, Лто сделает текущими все МО, достижимые не более, чем за и переходов, и создаст все следующие за ними МО, перед тем, как делать текущими МО, достижимые более, чем за и переходов.
Как следствие, допускающее МО Мп рассматривается Лто в числе первых пт" МО. Нам нужно знать лишь то, что т)оо рассматривает это МО через некоторое конечное время, н этой границы достаточно, чтобы убедиться, что допускающее МО в конце концов действительно рассматривается. Таким образом, если Ми допускает, то лто также допускает. Поскольку по построению Мо допускает только потому, что допускает Мя, можно заключить, что Т,(Л(п) = ЦМп). со Отметим, что построенная детерминированная МТ может потребовать времени, экспоненциально большего, чем время работы недетерминированной МТ.
Неизвестно, является ли это экспоненциальное соотношение необходимым. Этому вопросу и некоторым его производным, связанным с поисками лучшего способа детерминированной имитации НМТ, посвящена глава !О. ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 352 8.4.5. Чпражнения к разделу 8.4 Опишите неформаяьно, но четко и ясно многоленточные машины Тьюринга, допускаюшие один из языков, приведенных в упражнении 8.2.2. Постарайтесь построить каждую машину так, чтобы время ее работы было прямо пропорцио- нально длине входа. 8.4.1. Покажите, какие МО достижимы из начального МО, если входом является сле- дующая цепочка: а) (*) 01; б) 001.
(1) Опишите неформально, но четко и ясно недетерминнрованные машины Тьюринга, возможно, многоленточные, которые допускают следующие языки. Постарайтесь использовать преимущества недетерминизма, чтобы избежать итераций и сократить время работы в недетерминированном смысле, т.е. лучше, чтобы ваша машина имела много разветвлений, но ветви были короткими: 8.4.3. а) (*) язык всех цепочек из символов 0 и 1, содержаших некоторую подцепочку длиной 100, которая повторяется, причем не обязательно подряд. Формально, данный язык есть множество цепочек из 0 и 1 вида ихух-, где 1х! = 100, а зг, у и х имеют произвольную длину; б) язык всех цепочек вида н,УУи з)1...УУн;, для произвольного н, где каждая из н, есть цепочка из символов 0 и 1, причем для некоторого у цепочка и, является двоичной записью числау'; в) язык всех цепочек того же вида, что и в п.
б, но хотя бы для двух значений у цепочки я, представляют собой двоичную записьу', 8.4.4. (!) Рассмотрим недетерминированную машину Тьюринга М = игу„гуь гуь цу), уО, 1), (О, 1, В), В, гу, В, ~Оу)). Неформально, но ясно опишите язык ЦМ), если б состоит из следующих множеств правил: 4гур, О) = ((гуж 1, у!), (В, 1, уу)), Жу~ 1) = )(Чь 0 В)) 4Чъ 1) = 11.,2„1, УУ) ), Ж~ь В) = П уу, В, УУ) ). 8.4. РАСШИРЕНИЯ БАЗОВОЙ МАШИНЫ ТЬЮРИНГА 353 8А.2.
Недетерминированная МТ М= (!гуж дь гу ), (О, ! ), (О, 1, В), б, гуо, В 1у2)) представлена следующей функций переходов. (~) Рассмотрим недетерминированную МТ, лента которой бесконечна в обоих направлениях. В некоторый момент времени вся лента пуста, за исключением одной клетки, в которой записан символ 3. Головка находится в некоторой пус- той клетке, а состоянием является д: 8.4.5. а) напишите переходы, позволяющие НМТ перейти в состояние р, обозревая 3; б) (!) предположим, что МТ детерминирована. Как бы вы позволили ей найти 3 и перейти в состояниер? Постройте следующую 2-ленточную МТ, допускающую язык всех цепочек из 0 и 1, в которых этих символов поровну.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
