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

UptoLike

ВУЗ: 

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

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

Рубрика: 

101
Предположим, что символ Z
r
печатается на вершине (правом конце)
магазинной ленты Z
i
1
Z
i
2
... Z
i
m
. Счетчик, связанный с Z
i
1
Z
i
2
... Z
i
m
Z
r
, равен k×j + r.
Чтобы
установить этот новый счётчик, машина со счётчиком повторно сдвигает
головку
первого счётчика на одну ячейку влево, а головку второго — на k
ячеек вправо. Когда головка первого счетчика достигнет непустого символа,
второй
счетчик будет представлять k×j. Добавить r к этому счетчику просто.
Наоборот, чтобы удалить верхний символ Z
i
m
магазина,
необходимо заменить
значение счётчика j на целую часть j / k. Для этого надо повторно продвигать
влево головку первого счётчика на k ячеек, и после каждого такого
продвижения головки второго счётчика продвигать влево только на одну
ячейку. Если в очередной раз окажется невозможно продвинуть головку
первого счётчика ровно на k ячеек влево из-за того, что непустая ячейка будет
достигнута раньше, чем закончится продвижение на k ячеек, то в этот момент
на втором счётчике образуется требуемое значение.
Чтобы закончить описание моделирования, остаётся рассказать, как узнать,
какой символ находится на вершине магазинной ленты, моделируемой двумя
счётчиками. Если установлено значение j на одном счётчике, то машина может
скопировать j в другой счётчик, вычисляя j по модулю k в своём конечном
управлении. Значение j по модулю k это и есть i
m
.
Теорема 6.4. Машина с двумя счётчиками может моделировать
произвольную машину Тьюринга.
Доказательство. Согласно лемме 6.2 достаточно показать, как
моделировать четыре счётчика двумя. Пусть четыре счётчика имеют отсчёты i,
j, k и m. Все четыре значения можно установить на одном счётчике в виде
числа n = 2
i
3
j
5
k
7
m
. Поскольку 2, 3, 5 и 7 — простые числа, то значения i, j, k и
m могут быть однозначно восстановлены из n.
Чтобы увеличить i, j, k или m на единицу, достаточно умножить n на 2, 3, 5
или 7 соответственно.
Если мы имеем второй счётчик, установленный на нуль, то можем сдвигать
головку этого счетчика на 2, 3, 5 или 7 ячеек вправо каждый раз, как головка
первого счётчика продвигается на одну ячейку влево. Когда первый счётчик
достигнет нулевого отсчета, второй будет содержать отсчеты 2n, 3n, 5n или 7n
соответственно.
Чтобы уменьшить i, j, k или m на единицу, достаточно при помощи
подобного процесса разделить n на 2, 3, 5 или 7 соответственно.
Мы должны также показать, как машина с двумя счётчиками может
определить следующее движение машины с четырьмя счётчиками. Входная
головка машины с двумя счётчиками будет всегда в той же самой точке на её
входной ленте, в какой была бы входная головка машины с четырьмя
счётчиками. Состояние машины с четырьмя счётчиками может быть запомнено
в конечном управлении двух-счётчиковой машины. Следовательно, чтобы
определить движение четырех-счётчиковой машины, двух-счётчиковая должна
только определить, какие отсчеты из i, j, k, m равны нулю. Передавая n из

Страницы