Chapter 9: Turing Machines and Linear Bounded Automata ~ 283
The change brought about by processing the symbol 0 can be represented as
-t
JbOOllb (O.x.R) > bxOllb
qj
q2
~b
Rrw head
Fig. 9.5 TM processing 0011.
The entire computation sequence reads as follows:
JbOOllb
(O.x.R!
bxOllb
(O.O.RI
bxOllb
)
~
ql
q2
q2
J(l.,\'.LI ) bxOylb (O.O.L) ) bxOylb
(x.x.R)
bxOvlb
)
qo,
q4
ql
JIO.x.R) 'b
b
--~) xxvI
q2
J(\'.\'.R)
,. ) bxxylb
q2
J(1.\'.L)
, ) bxxyyb
qj
(".\,LI
J(x ..t.R) b J,
(".".R)
J,
"
>bxxyyb
) xxyyb "
) bxxyyb
qo,
qs
qs
(\,. ,.R)
J, (b.b.R)
J,
"
) bxxyyb
) bxxyybb
qs
q6
9.3 LANGUAGE ACCEPTABILITY BY TURING
MACHINES
I F't us consider the Turing machine M = (Q. '2:, 1. (5, qo, b. F). A string w in
'2:* is said to be accepted by M if qoVl' r- (XIP(X2 for some P E F and (x], (X:c
E r*.
M does not accept VI' if the machine M either halts in a non accepting state
or does not halt.