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

UptoLike

ВУЗ: 

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

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

Рубрика: 

108
108
B
m
Сост.
0 1
c L R B
0 1
c L R B
Пояснения
U
С
0
,
0
()
m
, L
С
1
,
1
()
m
, L
— — —
С
B
, ()
m
B
, L
Установить
маркер
V L L W, L L L —
W V, L V, L X
1
, R V, L V, L —
X
1
— — X
2
, R — — —
X
2
X
3
, R — — — — —
X
3
— — X
4
, R — — —
X
4
X
5
, R — —
—
— —
X
5
— — X
6
, R — — —
X
6
Y, R — — — — —
Проверить,
является ли
состояние, в
котором
случилась
остановка,
принимающим
Y — — — — — —
Принять
Примечание. Элементы таблицы имеют следующие значения. Тройка из состояния, ленточного символа и L или R
указывает следующее состояние, символ ленты, который печатать, и направление движения. Пара из состояния и L или R
указывает следующее состояние и направление движения, при этом ленточный символ остаётся неизменным. Символы L или
R и слова “Двигаться влево” или “Двигаться вправо” указывают, что машина Тьюринга движется влево или вправо, не
изменяя состояния и символа ленты. Прочерк обозначает ситуацию, которая никогда не случается. Состояние Y является
принимающим. Следовательно, никакое движение из состояния Y невозможно.

Страницы