1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 96
Текст из файла (страница 96)
Д о к а з а т е л ь с т в о. Допустим противное, т. е. что нашлась ДМТ М, с памятью, ограниченной функцией д(А„п), которая вы- ясняет, пусто ли множество, представленное расширенным регу- лярным выражением. По теореме 11.1 существует язык („ допу- скаемый некоторой ДМТ М с памятью, ограниченной функцией а(й,+1, и), ио не допускаемый никакой ДМТ с памятью, не боль- шей д(й,+1, и)!и. Предположив, что М, существует, можно по- строить ДМТ М„распознающую язык Ь следующим образом. 1. По данной входной цепочке в=а,а,...а„длины и машина М, строит расширенное регулярное выражение Р, длины й,п' (где й, — постоянная, не зависящая от и), представляющее измеритель с длиной, не меньшей а(й,+1, и).
Для построения Р, используется лемма 11.6. 2. Далее М, строит расширенное регулярное выражение Р„ представляющее правильные вычисления с измерителем Р, для ДМТ М, которая допускает !. и требует для этого не более й(й,+1, и) клеток памяти. По лемме 11.5 можно добиться, чтобы было Щ(й,~Р,( для некоторой постояниойй,. 3. Затем М, строит расширенное регулярное выражение Р,„ представляющее правильные вычисления машины М с измерителем Р, и начальным МО С,=(у,а,)а,...
а„ЬЬ..., где д, — начальное состояние машины М, а именно Р, = Р, () й-' ((у,а !а,... а„Ь' г(ь) (й, х Л,)', где й, — гомоморфизм из леммы 11.5 и Л,хб, — алфавит выражения Р,. По лемме 11.3 (Рь1~Яь(+йьп для некоторой постоянной й,~О. Поэтому ! Р, ! (й,й,п'+йэп. (11.4) 4. Наконец, М, кодирует Р, в фиксированном алфавите, как в теореме 11.2, и использует М, для проверки пустоты множества, представленного расширенным регулярным выражением Р,.
Если оио пусто, что М, отвергает вход ш, а если нет, то допускает его. Таким образом, М, допускает !.. Теперь нетрудно видеть, что наибольшей памяти требует шаг 4. На этом шаге машине М, нужна память й(й„)Р,!1ойЯ,0, чтобы выяснить, пусто ли множество, представленное выражением Р,. лгв УПРАЖНЕНИЯ Следовательно, и машине М, нужно столько же памяти. Учитывая границу (11.4) для (И,(, заключаем, что М, имеет емкостную сложность 5(п)=й,й(й„й,л'!ой и) для некоторых постоянных й, и й„ поскольку для всех, кроме конечного числа, значений п первое слагаемое в правой части (11.4), а именно й,й,п', больше второго, т.
е. й,л. Однако, рассуждая, как в приведенном доказательстве теоремы 11.2, можно показать, что емкостная сложность машины М, должна быть больше д(й,+1, и)/п для бесконечно многих л. Таким образом, если существует М„то у(/г, +1, л)ул с. й,д(й„й,л'1оап) (11.5) для бесконечно многих л. Но независимо от выбора й, и й, лишь для конечного числа значений и справедливо (11.5) (это легко проверить). Итак, машины М, не существует, и, значит, не существует М,. Поэтому проблема пустоты для расширенных регулярных выражений неразрешима никакой машиной Тьюринга с емкостной сложностью, ограниченной элементарной функцией. П УПРАЖНЕНИЯ 11.1. Функцию Т(п) иазгявают конструируемой ло времени, если некоторая ДМТ М при данном входе длины и делает ровно Т(п) шагов до своей остановки.
Покажите, что функции (а) п', (б) 2", (в) п( конструируемы по времени. "11.2. Покажите, что всякая функция, конструируемая по времени, конструируема по памяти, и если функция Я(п) конструируема по памяти, то сз'"' конструируема по времени для некоторого целого числа с. "11.3. Покажите, что если язык Ь допускается за время Т(п) какой-нибудь й-ленточной ДМТ (НМТ), то он допускается некоторой однолеиточной ДМТ (НМТ) с временной сложностью 0(Т'(л)). *11.4. (Иераркия повремени для ДМТ) Покажите, что если функции Т,(п) и Т,(п) конструируемы по времени и Т, (н) „Те (в) )п( — = О, то некоторый язык допускается ДМТ за время Т,(п), но не Т,(п).
Указание: В силу упр. 11.3 достаточно диагонализировать по одиоленточным ДМТ с временной сложностью не выше Т,(п). Саму диагонализацию можно выполнить с помощью многоленточной ДМТ. ап ГЛ. 1Е НЕКОТОРЫЕ ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ В следующих двух упражнениях сформулированы слабые варианты результатов об иерархиях для недетерминированных машин Тьюринга.
*'"11.5. Покажите, что для каждого целого числа й)1 существует язык, допускаемый некоторой НМТ с емкостной сложностью и"", но не допускаемый никакой НМТ с емкостной сложностью пл. *"11.6. Докажите тот же результат, что и в упр. 11.5, для временной сложности. В следующих двух упражнениях иерархия повремени для ДМТ уплотняется. **11.7. Покажите, что всякий язык Е, допускаемый некоторой Ьленточной ДМТ с временной сложностью Т(п), допускается двух- ленточной ДМТ с временной сложностью 0(Т(п) 1од Т(п)). 11.8. С помощью результата упр. 11.7 докажите, что если функции Т,(п) и Т,(п) конструируемы по времени и 1 Т1(л) )ОЯТ~ (л) Т, (л) то некоторый язык допускается ДМТ за время Т,(п), но не Т, (и). *11.9.
Покажите, что если 1. допускается ДМТ (НМТ) М с емкостной сложностью 5(п) и временной сложностью Т(п), а с)0— произвольная постоянная, то 1. допускается некоторой ДМТ (НМТ) М' с емкостной сложностью МАХ(с5 (и), п+1) и временной сложностью МАХ(сТ(п), 2п). Указание: М' должна начинать свою работу с сжимания блоков клеток машины М так, чтобы каждый такой блок помещался в одну клетку машины М'. 11.10.
Покажите, что если 1. допускается НМТ с временной сложностью Т (и), то найдется такая постоянная с, что 7. допускается ДМТ с временной сложностью ст<л>. "11.1!. Пусть Т, и Т, — такие функции, что 1п1 — = О. Т, (л) Т, (л) Покажите, что существует язык, допускаемый РАМ за время Т, (и), но не Т,(п) (время определяется по логарифмическому весовому критерию). 11.12. Закончите доказательство леммы 11.2.
*11.13. По данному расширенному регулярному выражению Я, для множества ЦИКЛ(кте) постройте расширенное регулярное 411 УПРАЖНБННя выРажение )ча длЯ ЦИКЛ((к?р)о) '). Длина выражения )? з должна быть не больше длины выражения )?„умноженной на постоянную. **11.14. Постройте недетерминированный алгоритм с емкостной сложностью О (и), выясняющий, пусто ли множество, представленное произвольным полурасширенным регулярным выражением, Почему ваш алгоритм не срабатывает, когда вы пытаетесь узнать, представляет ли данное регулярное выражение все цепочки? Почему он должен не срабатывать? 11.15.
Постройте детерминированный алгоритм, решающий за экспоненциальное время задачу пустоты дополнения для полурасширенных регулярных выражений. 11.16. Напишите регулярное выражение для "нарушений структуры" в доказательстве леммы 11.4. 11.17. Элементарна ли функция, определяемая равенствами Р(0)=! и Р(п)=2"'н-" для и)1? (Эта функция введена в разделе 4.7.) *11.18. Постройте алгоритм, выясняющий, представляет ли произвольное расширенное регулярное выражение пустое множество.
Какова временная и емкостная сложности вашего алгоритма? а*11.19. Покажите, что задача пустоты для расширенных регулярных выражений, использующих только знаки операций +, ° и -1, неэлементарна. Проблемы для исследования 11.20. Естественная область исследований, подсказываемая материалом этой главы,— поиск практически важных задач, про которые можно доказать, что они трудно разрешимые.
Работу в этом направлении проделали Фишер, Рабин !1974), исследовавшие сложность задач с элементарными арифметическими операциями, Кук, Рекхау (1974), изучившие процедуры доказательства теорем '), Хант !1974), рассмотревший ряд задач из теории языков, и некоторые другие авторы, упомянутые в замечаниях по литературе. ! 1.21. Интересен также вопрос о том, насколько плотнее могут быть иерархия по времени для ДМТ и иерархии по времени и емкости для НМТ по сравнению с иерархиями, указанными в упр. 1!.5, !1.6 и 11.8.
Например, существуют ли конструируемые по времени функции Т(п), для которых нет языков, распознаваемых за время Т(п)!ой Т(п), но не Т(п)? Читателю советуем обратиться к работе Сайфераса, Фишера, Мейера [!973), где приводится самая плотная из известных иерархий для НМТ. ') Результатом применення операции ЦИКЛ к множеству цепочек служит объединение ее значений на каждой отдельной цепочке из етого множества.
а) здесь уместно сослаться ензе на статью Цейтина !1968!.— прим. иеран. 1а А. Аао, Дж. Ховнрофт, дж. Унанан 473 Л. !!. НЕКОТОРЫЕ ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ Замвчаиия по лмтературв Первое обширное исследование иерархий по емкости и времени для машин Тьюринга выполнили Хартманис, Стирнз [!965) и Хартманис, Льюис, Стирнз [1965]. Статья Рабина [1963] была одной из первых работ о временной сложности, н она заслуживает изучения. Улучшения иерархии по времени, данные в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
