Составители:
96
Конечное
управление
Доказательство того, что обе машины принимают один и тот же язык,
предоставляется читателю в качестве упражнения.
6.4.2. Многоленточная машина Тьюринга состоит из конечного
управления с k ленточными головками, по одной на каждой ленте (рис. 6.4).
Каждая лента бесконечна в обоих направлениях. При одном движении,
зависящем от состояния конечного управления и сканируемого символа
каждой из ленточных головок, машина может:
1) изменить состояние;
2) напечатать новый символ на каждой из сканируемых ячеек;
3) передвинуть каждую из её ленточных головок независимо друг от друга
на одну ячейку влево, вправо или оставить её на том же месте.
Сначала входная цепочка имеется только на первой ленте, а все другие
ленты пусты. Мы не будем определять это устройство более формально,
предоставляя это читателю.
Рис. 6.4.
Теорема 6.2. Если язык L принимается многоленточной машиной
Тьюринга, то он принимается одноленточной машиной Тьюринга.
Доказательство. Пусть язык L принимается машиной Тьюринга T
1
с k
лентами. Построим одноленточную машину Тьюринга T
2
с 2k дорожками, по
две для каждой из лент машины T
1
. На одной дорожке записывается
содержимое соответствующей ленты машины T
1
, а другая — пустая, за
исключением маркера в ячейке, содержащей символ и сканируемой
соответствующей головкой машины T
1
. Такое устройство для моделирования
трёх лент посредством одной иллюстрируется рис. 6.5.
Конечное управление машины T
2
запоминает, какие маркеры головок
машины T
1
находятся слева, а какие — справа от головки T
2
. Состояния
машины T
1
тоже запоминаются в конечном управлении машины T
2
.
Головка 1
×
Лента 1
A
1
A
2
… …
A
m
Головка 2
×
Лента 2
B
1
B
2
… …
B
m
Головка 3
×
Лента 3
C
1
C
2
… …
C
m
Рис. 6.5.
Страницы
- « первая
- ‹ предыдущая
- …
- 95
- 96
- 97
- 98
- 99
- …
- следующая ›
- последняя »
