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

UptoLike

ВУЗ: 

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

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

Рубрика: 

98
ся, начиная с самой короткой. Среди последовательностей одинаковой длины
они генерируются в числовом порядке.
Для каждой последовательности, сгенерированной на ленте 2, машина T
2
копирует вход на ленту 3 и затем моделирует машину T
1
на ленте 3, используя
последовательность ленты 2 для того, чтобы диктовать движения машине T
1
.
Если машина T
1
входит в принимающее состояние, то машина T
2
также
принимает. Если имеется последовательность вариантов, ведущая к приёму, то
она в конце концов будет сгенерирована на ленте 2. Будучи смоделирована,
машина T
2
будет принимать входную цепочку. Но если никакая последователь-
ность вариантов движений машины T
1
не ведет к приёму входной цепочки, то
машина T
2
тоже
не примет её.
Заметим, что это доказательство можно обобщить, чтобы показать, как
моделировать недетерминированную многоленточную машину Тьюринга
обычной моделью машины Тьюринга.
6.4.4. Двумерная машина Тьюринга является ещё одной
модификацией машины Тьюринга, которая не увеличивает её мощности. Это
устройство состоит из обычного конечного управления, но лента разбита на
бесконечное число ячеек, расположенных в двух измерениях. В зависимости от
состояния и сканируемого символа устройство изменяет состояние, печатает
новый символ и передвигает ленточную головку в одном из четырех
направлений. Первоначально входная цепочка находится на одной строке, а
головка находится на её левом конце.
В любое время только конечное число строк имеет какие-нибудь непустые
символы на них, и каждая из этих строк содежит только конечное число
непустых символов.
Рассмотрим, например, конфигурацию ленты, показанную на рис. 6.6, a.
Мы можем очертить прямоугольник вокруг непустых символов, как показано
на этом рисунке, и этот прямоугольник можно записать строка за строкой на
одномерной ленте, как показано на рис. 6.6, б.
а
B B B a
1
B B B
B B a
2
a
3
a
4
a
5
B
a
6
a
7
a
8
a
9
B a
10
B
B a
11
a
12
a
13
B a
14
a
15
B B a
16
a
17
B B B
б
*BBBa
1
BBB*BBa
2
a
3
a
4
a
5
B*a
6
a
7
a
8
a
9
Ba
10
B*Ba
11
a
12
a
13
Ba
14
a
15
*BBa
16
a
17
BBB*
Рис. 6.6.
Символы * разделяют строки. Один из символов помечается как скани-
руемый головкой. Для пометки можно использовать дополнительную дорожку
ленты. Если при данном движении головка остаётся в пределах представлен-
ного прямоугольника, то подогнать положение головки нетрудно. Если голов-
ка выходит за границу прямоугольника при движении в вертикальном направ-

Страницы