11.2. ИЕРАРХИЯ ПО ЕМКОСТНОЙ СЛОЖНОСТИ ДЛЯ ДЕТЕРМИНИРОВАННЫХ МАШИН ТЬЮРИНГА

Здесь мы докажем теорему о иерархии по емкостной сложности (иерархии по памяти) для детерминированных машин Тьюринга. Можно доказать аналогичные результаты для времени и для недетерминированных машин Тьюринга, но поскольку для наших целей они не нужны, мы оставляем их в качестве упражнений. Вспомним, что в силу следствия 3 леммы 10.1, если язык допускается -ленточной ДМТ с емкостной сложностью он допускается и одноленточной ДМТ с емкостной сложностью Таким образом, можно ограничиться рассмотрением одноленточных ДМТ.

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

Не умаляя общности, можно принять следующие соглашения о способе представления одноленточных ДМТ.

1. Состояния имеют имена для некоторого причем начальное и допускающее состояния.

2. Входным алфавитом служит

3. Ленточным алфавитом служит для некоторого где

4. Функция переходов представляет собой список пятерок вида означающих, что где состояния, ленточные символы и направление сдвига головки: (влево), (вправо) (остается на месте) при и 2 соответственно. Считаем, что такая пятерка кодируется цепочкой

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

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

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

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

следствия 3 леммы 10.1 существует одноленточная эквивалентная и имеющая ту же емкостную сложность Поскольку сама машина М тоже представлена в таблице (скажем, это при некотором и она не может отличаться от себя, то можно заключить, что емкостная сложность машин не есть Фактическая конструкция М усложнена из-за нашего желания построить М так, чтобы она имела такую емкостную сложность что почти одинаковы.

Определение. Пусть произвольная функция. Обозначим через предел при наибольшей нижней грани последовательности

Пример 11.1. Так как монотонно убывает, то

В качестве второго примера рассмотрим если не есть степень числа 2, и в противном случае. Тогда поскольку наибольшая нижняя грань последовательности равна либо если не есть степень числа 2, либо если — степень числа

Теорема 11.1. Пусть две функции, конструируемые по памяти, причем

Тогда существует язык допускаемый некоторой ДМТ с емкостной сложностью но не допускаемый никакой ДМТ с емкостной сложностью

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

1. М отмечает клеток на каждой ленте. После этого всякий раз, когда любая ее головка пытается выйти за отмеченные клетки, останавливается, не допуская вход.

2. Если х не является кодом никакой одноленточной останавливается, не допуская вход.

3. В прочих случаях пусть код определяет число используемых машиной символов на ленте и число ее состояний. Третья лента машины может играть роль "промежуточной" памяти при вычислении Затем М разбивает свою вторую ленту на блоков по клеток в каждом, эти блоки отделяются друг от друга клетками, содержащими маркер таким образом, всего клеток если Каждый символ на ленте машины будет закодирован двоичным числом в соответствующем блоке на второй ленте машины Вначале М помещает свой вход в виде его двоичного кода в блоки ленты 2, а неиспользованные блоки заполняет кодом пустого символа.

4. На ленте образует блок из клеток и вначале записывает в них нули; здесь снова предполагается, что число требуемых клеток не превосходит Лента 3 играет роль счетчика, в который можно помещать числа вплоть до моделирует машину используя ленту 1 (т. е. свою входную ленту) для определения шагов машины и ленту 2 для моделирования ленты машины Номера шагов машины записываются в виде двоичных чисел в блок на ленте 3, а на ленте 4 хранится состояние машины Если допускает свой вход, то останавливается, не допуская свой. допускает вход, если останавливается, не допуская свой вход, или если для моделирования работы машина М0 пытается занять больше клеток на ленте 2, чем отведено, или если переполняется счетчик на ленте 3, т. е. число шагов, сделанное машиной превосходит

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

Равенство гарантирует, что такое можно найти.

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

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