Cтраница 1
Двусторонняя магазинная машина - это двусторонняя машина Тьюринга с тем ограничением, что машина печатает пустой символ перед каждым правым продвижением своей рабочей ленты. Принято рассматривать это продвижение вправо как вы борку информации, а продвижение влево - как запись. [1]
Двусторонние магазинные машины могут разрешать и контекстно-свободные и контекстные языки. [2]
Для двусторонней магазинной машины получаем следующий результат. [3]
Для двусторонних магазинных машин нам неизвестна возможность использовать диагонализационное доказательство, как было сделано для машин Тьюринга, но мы все-таки можем указать иерархию построением множеств, удовлетворяющих следующей лемме. [4]
Другой открытый вопрос относится к аналогичным результатам для двусторонних магазинных машин; какая функция L ( n) потребуется, чтобы на двусторонней машине Тьюринга промоделировать двустороннюю магазинную машину, производящую нерегулярное разрешение. Здесь результат, быть может, зависит от L ( n) для магазинной машины. [5]
Мы высказываем гипотезу, что совокупность множеств, разрешимых двусторонними магазинными машинами, строго включается в множество контекстных языков и не содержит всех контекстно-свободных языков. [6]
В этом разделе мы покажем, что двусторонние и односторонние машины Тьюринга и двусторонние магазинные машины определяют бесконечные иерархии контекстно-свободных языков. Как обсуждалось выше, односторонняя магазинная машина обладает только одним классом сложности L ( n) n и потому не определяет иерархию. Уже было показано, что машины Тьюринга включают все контекстно-свободные языки в свои иерархии. [7]
Язык L2 ( L ( п) - log log n) - разрешим на двусторонней магазинной машине. [8]
Из [1] следует, что как модели односторонней и двусторонней машин Тьюринга, так и модель двусторонней магазинной машины определяют иерархию различных классов сложности контекстных языков. [9]
Другой открытый вопрос относится к аналогичным результатам для двусторонних магазинных машин; какая функция L ( n) потребуется, чтобы на двусторонней машине Тьюринга промоделировать двустороннюю магазинную машину, производящую нерегулярное разрешение. Здесь результат, быть может, зависит от L ( n) для магазинной машины. [10]