11.4. НЕЭЛЕМЕНТАРНАЯ ЗАДАЧА

Исследуем весь класс расширенных регулярных выражений. Поскольку теперь у нас есть операция дополнения, достаточно рассматривать задачу пустоты, а именно: пусто ли множество, представленное данным регулярным выражением? Мы увидим, что, располагая операцией дополнения, можно представлять регулярные множества еще более короткими выражениями и задача пустоты для расширенных регулярных выражений значительно труднее задачи пустоты дополнения для полурасширенных регулярных выражений.

Определим функцию равенствами

Тогда и

где справа стоит башня из двоек и последняя возводится в степень Функция называется элементарной, если для некоторого та она ограничена сверху функцией для всех, кроме конечного числа, значений

С помощью техники разд. 11.3 можно доказать, что задача пустоты для всего класса расширенных регулярных выражений не может иметь емкостную сложность ни для какой элементарной

Рис. 11.2. Новая форма правильных вычислений с измерителем.

функции Прежде чем приступить к доказательству, изменим немного определение правильного вычисления машины Тьюринга с измерителем Удалим первый маркер и заменим последний маркер новым символом (рис. 11.2). Обозначим через (дополненные, если надо, пустыми символами, чтобы их длина стала равной длине цепочки как и раньше, за один шаг машины для начальное МО и содержит состояние

Будем использовать следующие обозначения (предполагаем, что

Лемма 11.5. Пусть расширенное регулярное выражение для множества Можно построить такое расширенное регулярное выражение представляющее множество циклических перестановок правильных вычислений машины Тьюринга с измерителем что есть где постоянная зависит только от

Доказательство. Цепочка является циклической перестановкой правильного вычисления с измерителем тогда и только тогда, когда

1) нижняя дорожка — циклическая перестановка цепочки вида

2) верхняя дорожка — циклическая перестановка правильного вычисления машины и

3) верхняя и нижняя дорожки циклически переставлены одинаково.

Пусть это выражение в котором вместо стоит символ

Цепочки, удовлетворяющие условию 1, можно представить выражением где

Подвыражение представляет две цепочки Поэтому представляет Выражение содержит цепочки с ровно одним вхождением Поэтому всякая цепочка из имеет вид

где некоторые цепочки из 2. Выражение приводит к тому, что откуда легко следует, что для цепочек из Таким образом, представляет нижнюю дорожку всех цепочек, удовлетворяющих условию 1.

Что касается условия 2, то в лемме 11.4 мы видели, как паписать полурасширенное регулярное выражение для неправильных вычислений машины с измерителем Эта техника легко переносится на форму, показанную на рис. 11.2, и мы предлагаем читателю самому построить выражение представляющее циклические перестановки неправильных вычислений машины с корректным измерителем на нижней дорожке. Применение операции дополнения к дает расширенное регулярное выражение Это единственное место, где применяется дополнение. Должно быть ясно, что все цепочки, представленные выражением удовлетворяют обоим условиям 1 и 2.

Выражение для условия 3 в предположении, что условия 1 и 2 выполнены, строится без особого труда. Надо лишь проверить, что один символ имеет на обеих дорожках. Пересекая это выражение с , получаем требуемое.

Теперь покажем, как с помощью леммы 11.5 выражать все более и более длинные измерители, не слишком увеличивая длины задающих их выражений.

Интуитивно мы строим регулярное выражение для какого-то измерителя с небольшой длиной, скажем с длиной Затем используем его, чтобы построить новое регулярное выражение для всех циклических перестановок правильных вычислений с этим измерителем для некоторой машины Тьюринга, допускающей в точности одну цепочку длины Машина Тьюринга специально выбирается так, чтобы на входе длины она делала по меньшей мере шагов, поэтому множество циклических перестановок ее правильных вычислений само будет измерителем с длиной или более. Повторяя этот процесс с новым измерителем, получаем измерители все с большими и большими длинами, но не меньшими и т. д.

Пусть конкретная одноленточная машина Тьюринга, которая ведет себя так:

1) проверяет, что ее входная лента начинается с последовательности символов а, для чего просматривает эту ленту до первого пустого символа,

2) если входная лента содержит цепочку из символов а, за которыми стоит пустой символ, считает в двоичной системе

от до на части своей ленты, которая была занята символами а и следующим за ними пустым символом,

3) досчитав до останавливается и допускает свой вход.

Итак, обладает следующими свойствами. Для каждого она допускает в точности одну цепочку длины а именно Она делает это, выполняя единственное правильное вычисление, состоящее не менее чем из шагов, поскольку половина ее шагов добавляет биты, а другая половина осуществляет переносы. Наконец, М просматривает только клеток ленты, когда ей подан вход длины

Исследуем теперь правильные вычисления машины М с измерителем имеющие вид, показанный на рис. 11.2. Если то существует единственное правильное вычисление машины М с измерителем которого верхняя дорожка начинается с По лемме 11.5 для всех его циклических перестановок можно построить регулярное Оно будет представлять множество, состоящее из циклических перестановок фиксированной цепочки Цепочка будет правильным вычислением машины М на входе где, напомним, Так как М делает на входе не менее шагов, а можно взять в качестве измерителя с длиной не менее

Итак, пусть дан измеритель представленный выражением где Тогда по и описанной выше можно построить измеритель с длиной, не меньшей 211. По лемме 11.5 для него найдется регулярное выражение длины не более где постоянная зависит только от

Лемма 11.6. Для всех существует измеритель с длиной, не меньшей который можно представить расширенным регулярным выражением длины не более где постоянная, зависящая от М и введенная в предыдущем абзаце, постоянная из леммы 11.1.

Доказательство. Докажем индукцией по что найдется расширенное регулярное выражение представляющее для некоторого х, где Базис следует из леммы 11.1 при поскольку можно построить расширенное регулярное выражение длины представляющее

Для шага индукции допустим, что построено расширенное регулярное выражение длины представляющее где Тогда на основе проведенного выше анализа, касающегося заключаем, что можно

построить регулярное выражение длины не более представляющее где

Теорема 11.3. Пусть любая элементарная функция. Тогда не существует ДМТ с емкостной (и, следовательно, временной) сложностью, ограниченной сверху функцией которая могла бы установить, пусто ли множество, представленное произвольным расширенным регулярным выражением.

Доказательство. Допустим противное, т. е. что нашлась с памятью, ограниченной функцией которая выясняет, пусто ли множество, представленное расширенным регулярным выражением. По теореме 11.1 существует язык допускаемый некоторой ДМТ М с памятью, ограниченной функцией но не допускаемый никакой ДМТ с памятью, не большей Предположив, что существует, можно построить распознающую язык следующим образом.

1. По данной входной цепочке длины машина строит расширенное регулярное выражение длины постоянная, не зависящая от представляющее измеритель с длиной, не меньшей Для построения используется лемма 11.6.

2. Далее строит расширенное регулярное выражение представляющее правильные вычисления с измерителем для которая допускает и требует для этого не более клеток памяти. По лемме 11.5 можно добиться, чтобы было для некоторой постоянной .

3. Затем строит расширенное регулярное выражение представляющее правильные вычисления машины с измерителем и начальным где начальное состояние машины а именно

где гомоморфизм из леммы алфавит выражения По лемме 11.3 для некоторой постоянной Поэтому

4. Наконец, кодирует в фиксированном алфавите, как в теореме 11.2, и использует для проверки пустоты множества, представленного расширенным регулярным выражением Если оно пусто, что отвергает вход а если нет, то допускает его. Таким образом, допускает

Теперь нетрудно видеть, что наибольшей памяти требует шаг 4. На этом шаге машине нужна память чтобы выяснить, пусто ли множество, представленное выражением

Следовательно, и машине нужно столько же памяти. Учитывая границу (11.4) для заключаем, что имеет емкостную сложность для некоторых постоянных поскольку для всех, кроме конечного числа, значений первое слагаемое в правой части (11.4), а именно больше второго, Однако, рассуждая, как в приведенном доказательстве теоремы 11.2, можно показать, что емкостная сложность машины должна быть больше для бесконечно многих Таким образом, если существует то

для бесконечно многих Но независимо от выбора лишь для конечного числа значений справедливо (11.5) (это легко проверить). Итак, машины не существует, и, значит, не существует Поэтому проблема пустоты для расширенных регулярных выражений неразрешима никакой машиной Тьюринга с емкостной сложностью, ограниченной элементарной функцией.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

Замечания по литературе

Первое обширное исследование иерархий по емкости и времени для машин Тьюринга выполнили Хартманис, Стирнз [1965] и Хартманис, Льюис, Стирнз [1965]. Статья Рабина [1963] была одной из первых работ о временной сложности, и она заслуживает изучения. Улучшения иерархии по времени, данные в упр. 11.7, 11.8, заимствованы у Хенни, Стирнза [1966]. Что касается иерархий для НМТ, то упр. 11.5 (память) взято у Ибарры [1972], а 11.6 (время) — у Кука [1973]. Иерархия для РАМ в упр. 11.11 принадлежит Куку, Рекхау [1973], упр. 11.14 — Хопкрофту, упр. 11.19 — Мейеру, Стокмейеру [1973].

Установление экспоненциальных нижних оценок для «естественных» задач началось с работ Мейера [1972] и Мейера, Стокмейера [1972]. Теорема 11.2 о полурасширенных регулярных выражениях взята у Ханта [19736], теорема 11.3 о расширенных регулярных выражениях — у Мейера, Стокмейера [1973]. Другие результаты о трудно разрешимых задачах приводят Бук [1972], Хант [1973а, 1974], Стокмейер, Мейер [1973], Мейер [1972], Хаит, Розенкранц [1974], Раундз 11973] и Констейбл, Хант, Сахни [1974].