Языки и трансляции. Мартыненко Б.К. - 100 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

99
лении, добавляют ещё одну строку пробелов к левому или правому концу
линейного представления. Если головка покидаёт прямоугольник через правую
или левую границу, длина каждой представленной строки должна быть
увеличена на единицу. При этом может пригодиться метод “сдвига”.
Описанный подход легко обобщить на n-мерные ленты.
6.4.5. Машина Тьюринга с входной лентой только для чтения и
одной или несколькими лентами памяти для записи/чтения
также
заслуживает упоминания. Её движение зависит от сканируемого входного
символа, но она не может печатать на входной ленте. Обычно считается, что
входная лента имеет концевые маркеры с тем, чтобы её головка всегда
оставалась на входной цепочке, границы которой она сама не может
переносить.
Если входная головка может двигаться в двух направлениях, то устройство
называется машиной Тьюринга типа off-line. Если входная головка никогда не
движется влево, то это машина Тьюринга типа on-line. Ясно, что машины этих
двух типов являются вариантами многоленточных машин Тьюринга. Они
могут моделировать любую многоленточную машину Тьюринга.
§ 6.5. Ограниченные машины Тьюринга,
эквивалентные основной модели
До сих пор рассматривались обобщения основной модели машины
Тьюринга. Как мы видели, эти обобщения не увеличивают вычислительную
мощность этой модели.
Данную главу заключим обсуждением некоторых моделей, которые с
первого взгляда могут показаться менее мощными, чем обычные машины
Тьюринга, но на самом деле имеют точно такую же мощность. По большей
части эти модели будут вариациями базисного магазинного автомата,
рассмотренного в гл. 5. Попутно отметим, что магазинный автомат можно
рассматривать как недетерминированную машину Тьюринга с двумя лентами:
одной только для чтения, причём её входная головка не может двигаться влево,
и другой — лентой памяти с весьма специфическим ограничением для её
ленточной головки. Всякий раз, как головка ленты памяти движется влево, она
должна печатать пробел. Таким образом, лента памяти справа от головки —
всегда пустая. Строго говоря, машине Тьюринга запрещено печатать
настоящий пробел. Взамен можно было бы ввести другой специальный символ
с теми же самыми правилами, какие имеются для пробела. Предоставим
читателю убедиться в том, что такая модель эквивалентна магазинному
автомату, введенному в гл. 5.
6.4.6. Детерминированная машина с двумя магазинными
лентами — это детерминированная машина Тьюринга с входной цепочкой
только для чтения и двумя магазинными лентами памяти. Если головка
магазинной ленты движется влево, то она печатает “пробел”.

Страницы