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

UptoLike

ВУЗ: 

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

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

Рубрика: 

85
Машина входит в состояние q
3
, когда ни одного 0 не остаётся (см. п. 3б).
Машина должна продвигаться вправо (п. 5а) сквозь блок Y. Если встречается
пробел раньше, чем 1, то ни одной 1 не осталось (п. 5б). В этой ситуации
машина переходит в конечное состояние q
5
и останавливается, сигнализируя
тем самым приём входной цепочки.
6. Во всех случаях, кроме 1–5, функция δ не определена.
Рассмотрим действия машины Тьюринга на входной цепочке 000111.
Таблица 6.1
Шаг Конфигурация Шаг Конфигурация Шаг Конфигурация
1
0
0 1 1 1
q
0
10
X X 0 Y 1 1
q
1
19
X X X Y Y Y
q
2
2
X 0 0 1 1 1
q
1
11
X X 0 Y 1 1
q
1
20
X X X Y Y Y
q
2
3
X 0 0 1 1 1
q
1
12
X X 0 Y Y 1
q
2
21
X X X Y Y Y
q
2
4
X 0 0 1 1 1
q
1
13
X X 0 Y Y 1
q
2
22
X X X Y Y Y
q
3
5
X 0 0 Y 1 1
q
2
14
X X 0 Y Y 1
q
4
23
X X X Y Y Y
q
3
6
X 0 0 Y 1 1
q
4
15
X X 0 Y Y 1
q
0
24
X X X Y Y Y
q
3
7
X 0 0 Y 1 1
q
4
16
X X X Y Y 1
q
1
25
X X X Y Y Y
q
3
8
X 0 0 Y 1 1
q
0
17
X X X Y Y 1
q
1
26
X X X Y Y Y Y
q
5
9
X X 0 Y 1 1
q
1
18
X X X Y Y 1
q
1
В табл. 6.1 приведены конфигурации в виде цепочек символов ленты с
маркером состояния под сканируемым символом (в конфигурациях 25 и 26
маркер состояния находится под символом пробела в позиции 8).
§ 6.2. Методы построения
машин Тьюринга
Машина Тьюринга может “программироваться” во многом так же, как
программируются вычислительные машины. Роль программы играет функция
δ. В этом параграфе мы представим коллекцию приёмов программирования
машины Тьюринга, которые помогут лучше узнать ее возможности.
6.2.1. Конечное управление в роли запоминающего устройства.
Конечное управление может использоваться для запоминания конечного объёма

Страницы