ВУЗ:
Составители:
101
головки записи-считывания, находящейся в каждый момент в некото-
ром состоянии (из заданного конечного списка состояний),
управляющего устройства, которое может находиться в одном из со-
стояний, образующих конечное множество Q = {q
1
, ..., q
n
};
Среди состояний управляющего устройства выделены начальное со-
стояние q
1
и заключительное состояние q
z
. В начальном состоянии машина на-
ходится перед началом работы, попав в заключительное состояние, машина ос-
танавливается.
Таким образом, память машины Т – это конечное множество состояний
(внутренняя память) и лента (внешняя память). Лента бесконечна в обе сторо-
ны, однако в любой последующий момент времени лишь конечный отрезок
ленты будет заполнен символами
. Поэтому важна не фактическая (как говорят в
математике, актуальная) бесконечность ленты, а ее неограниченность, т. е. воз-
можность писать на ней сколь угодно длинные, но конечные слова. Данные ма-
шины Т – это слова в алфавите ленты; на ленте записываются и исходные дан-
ные, и окончательные результаты. Элементарные шаги машины – это
считыва-
ние и запись символов, сдвиг головки на ячейку влево и вправо, а также переход
управляющего устройства в следующее состояние. Детерминированность ма-
шины, т.е. последовательность ее шагов, определяется следующим образом: для
любого внутреннего состояния q
i
, и символа а
j
однозначно заданы: а) следую-
щее состояние q
i
б) символ а
j
, который нужно записать вместо а
j
, в ту же
ячейку (стирание символа будем понимается как запись пустого символа λ); в)
направление сдвига головки d
k
, обозначаемое одним из трех символов: L (вле-
во), R (вправо), E (на месте).
Задание машины Т может описываться либо системой правил (команд),
имеющих вид
q
i
a
j
→q
i
a
j
d
k
, (7.1)
либо таблицей, строкам которой соответствуют состояния, столбцам –
входные символы, а на пересечении строки q
i
и столбца a
j
записана тройка сим-
волов q
i
a
j
d
k
, и, наконец, блок-схемой, которая называется диаграммой пере-
ходов. В этой диаграмме состояниям соответствуют вершины, а правилу (7.1) –
ребро, ведущее из q
i
в q
i
, на котором написано a
j
→a
j
d
k
. Условие однознач-
ности требует, чтобы для любого j и любого i ≠ z в системе команд имелась одна
команда, аналогичная (7.1), с левой частью q
i
a
j
; состояние q
z
в левых частях ко-
манд не встречается. На диаграмме переходов это выражается условием, что из
каждой вершины, кроме q
z
, выходят ровно m ребер, причем на разных ребрах
левые части различны; в вершине q
z
нет выходящих ребер.
Полное состояние машины Т, по которому однозначно можно опреде-
лить ее дальнейшее поведение, определяется ее внутренним состоянием, со-
стоянием ленты и положением головки на ленте. Полное состояние будем назы-
вать конфигурацией, или машинным словом, и обозначать тройкой α
1
q
i
α
2
, где q
i
Страницы
- « первая
- ‹ предыдущая
- …
- 99
- 100
- 101
- 102
- 103
- …
- следующая ›
- последняя »
