4.3. Правила работы машины

 

Машина работает дискретно (пошагово). На каждом шаге происходит переход от одной конфигурации к другой. Перед началом работы машина находится в начальной конфигурации: СЗУ обозревает первую букву слова, а машина находится в начальном состоянии q1. СЗУ считывает букву, находящуюся в обозреваемой ячейке. УУ обращается к программе машины: находит клетку, соответствующую считанной букве и состоянию машины. Пусть в этой клетке находится тройка (а, q, s),  тогда буква а заносится в обозреваемую ячейку, машина переводится в состояние q, а СЗУ совершает сдвиг на одну ячейку влево, если s=-1, на одну ячейку вправо, если s=+1,  и остается на месте, если s=0. На этом завершена работа машины на первом шаге, и она готова к выполнению следующего аналогичного шага и т. д.

Работа машины продолжается до тех пор пока, на каком-то шаге машина не придет в состояние q0. Устройство  управления в этом случае останавливает машину. Возникшая конфигурация называется заключительной, а полученное слово – результатом применения машины к исходному слову.