ВУЗ:
Составители:
Рис. 2.1.
Ситуацией называется пара
ji
xq ; Qq
i
∈
, Xx
j
∈
. Очевидно, начальная
ситуация МТ, указанная на рис. 2.1, есть
10
xq . Выражением будем называть
конечную последовательность символов в алфавите
},,,,...,,,,...,,{
1010
srlqqqxxx
mn
.
Командой называется выражение одного из следующих типов:
jlki
qxxq ;
jki
rqxq ;
jki
lqxq ;
jki
sqxq .
Конечная последовательность команд, задающая функционирование
МТ, называется таблицей Тьюринга. Если в этой таблице все команды имеют
попарно различные ситуации, то соответствующая ей МТ называется
детерминированной. Кроме того, функционирование МТ можно задать с
помощью таблиц Айзермана, определяющих отображения
δ
: XQ × в Q,
μ
:
XQ × в Х и
ν
: XQ × в I и называемых соответственно таблицей
преобразования сигнала записи ленты и таблицей преобразования
перемещения ленты. Эти три таблицы можно объединить в одну
обобщенную таблицу.
Конфигурацией называется выражение вида
lkji
xxxq ... , в котором q
i
не
может занимать крайней правой позиции. Конфигурация однозначно
определяет работу МТ. Пусть
α
,
β
- конфигурация некоторой МТ Z, а Р, R -
произвольные последовательности символов на ленте. МТ переходит из
α
в
β
)(
β
α
→ в одном из трех случаев:
1) по команде
jlki
qxxq
. В этом случае символ x
k
в рабочей ячейке
меняется на x
l
, состояние q
i
заменяется состоянием q
j
, а лента остается без
движения:
lRPq
i
=
α
, RxPq
lj
=
β
;
В
х
α
х
β
х
γ
х
δ
х
λ
В
управляющее
устройство
головка
r
l
р
абочая ячейка
r
l
лента
Страницы
- « первая
- ‹ предыдущая
- …
- 25
- 26
- 27
- 28
- 29
- …
- следующая ›
- последняя »
