Transition function is taken as
δ(q 0 , 0) = (q 0 , 0, R)
δ(q 0 , o) = (q 1 , o,R).
The head will move to the right, as long as 0 appears under the read-write
head. If any time a 1 is read, the machine will halt in the nonfinal state q 0 , since
δ( , )
q 0 1 is undefined.
Ì Exam ple 4.1.3: Design a Turing machine that accepts
L a b n
n n
=
≥
{
|
}.
0
Solu tion
Assume that q 1 is the “final state”.
q 4 (which has no available moves at all) serves as an “error state”.
Cur rent
state
Sym bol
read
Sym bol
writ ten
Direc tion
Next
state
Find the left end of the input
q 0
a
a
L
q 0
q 0
b
b
L
q 0
q 0
#
#
R
q 1
If leftmost sym bol is “a”, erase it, if “b”, fail
q 1
a
#
R
q 2
q 1
b
#
R
q 4
Find the right end of the input
q 2
a
a
R
q 2
q 2
b
b
R
q 2
q 2
#
#
L
q 3
Erase the “b” at the left end of the input
q 3
b
#
L
q 0
The basic operation of this machine is a loop:
q 0 : Move all the way to the left
q 1 : Erase an ‘a’.
Turing Machines
191