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

UptoLike

ВУЗ: 

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

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

Рубрика: 

100
d
1
d
2
Лемма 6.1. Произвольная одноленточная машина Тьюринга может быть
смоделирована детерминированной машиной с двумя магазинными лентами.
Доказательство. Достаточно убедиться в том, что символы слева от
головки машины Тьюринга, которая моделируется, могут запоминаться на
одной магазинной ленте, а те, что справа, — на другой.
6.4.7. Машина со счетчиками есть машина Тьюринга, алфавиты лент
памяти которой содержат только два символа, например Z и B. Кроме того,
символ Z появляется в ячейке, первоначально сканируемой ленточной
головкой, и никогда не может появиться ни в какой другой. Число i можно
запомнить путём передвижения головки ленты на i ячеек вправо от Z.
Предполагается, что машины этого типа могут печатать пробел. Запомненное
число может быть увеличено или уменьшено передвижением головки ленты
вправо или влево.
Пример машины со счетчиком показан на рис. 6.7. Символы ¢ и $ обычно
используются в качестве концевых маркеров на входной ленте. Здесь Z —
непустой символ.
¢ Ввод $
Z B B
…
B B B
…
Z B B
…
B B B
…
Рис. 6.7.
Конфигурация машины со счётчиками может быть описана при помощи
состояния, положения входной головки и расстояний головок лент памяти от
символа Z (на рис. 6.7 они обозначены символами d
1
и d
2
). Назовем эти
расстояния отсчётами на лентах. Машина со счётчиками может фактически
только запоминать отсчёт на каждой ленте и указывать, является ли этот отсчёт
нулевым.
Лемма 6.2. Машина с четырьмя счётчиками может моделировать
произвольную машину Тьюринга.
Доказательство. Согласно лемме 6.1 достаточно показать, что две ленты
со счётчиками могут моделировать одну магазинную ленту.
Пусть магазинная лента имеет k–1 непустых ленточных символов Z
1
, Z
2
, ...,
Z
k –1
. Тогда мы можем однозначно представить магазинную ленту Z
i
1
Z
i
2
... Z
i
m
при
помощи “счетчика” j = i
m
+ k i
m – 1
+ k
2
i
m – 2
+ ... + k
m–1
i
1
. Предположим, что j
запоминается на одном счётчике, т.е. головка ленты находится на j ячеек
правее непустого символа. Пусть головка второго счётчика также находится на
непустом символе.
Конечное
управление

Страницы