q 2 : Move all the way to the right
q 3 : Erase a “b”.
Repeat
If the string is not of the form {
|
}
a b n
n n
≥ 0 it will finally either
(a) see an ‘a’ in nonfinal state q 3 , and halt, or
(b) see a ‘b’ in final state q 1 , move to nonfinal state q 4 , and halt.
Ì Exam ple 4.1.4: What does the Turing Machine described by the
5-tuples ( , , , , ), ( , , , , )
q
q
R q q
R
0
0
0
1
0
0
1 0 , ( , , , , )
q B q B R
0
2
, ( , , , , )
q
q
R
1
1
0
0 ,
( , , , , )
q q R
1
0
1 1
and ( , , , , )
q B q B R
1
2
do when given a bit string as input?
Solu tion
If the tape contains at least one 1, the machine changes every other 1 to a 0
starting at the first 1, and halts when it reches the first blank symbol. If the tape
is blank initially the machine halts without changing the tape. If the nonblank
portion of the tape contains all 0s, the machine moves successively through
these 0s and halts.
Ì Exam ple 4.1.5: Let T be the Turing machine defined by the five tuples:
( , , , , )
q
q
R
0
1
0
1 , ( , , , , )
q
q
R
0
1
1
0 , ( , , , , )
q B q
R
0
1 0 , ( , , , , )
q
q
L
1
2
0
1 ,
( , , , , )
q
q
R
1
1
1
0 , ( , , , , )
q B q
L
1
2 0 . For each of the following initial tapes,
determine the final tape when T halts, assuming that T begins in initial
position.
(a)
(b)
Solu tion
(a) The nonblank portion of the tape contains the string 1111 when
the machine halts.
(b) The nonblank portion of the tape contains the string 00 when the
machine halts.
4.2 COMPLETE LANGUAGES AND FUNCTIONS
A Turing machine has an output function, the contents of the input tape after
processing, a given input string can be viewed as the result of computation.
Therefore a Turing machine is seen as a computer of functions, from integers
to integers.
192
Theory of Automata, Formal Languages and Computation
B
B
B
B
...
... ... ...
B
B
B
B
B
B
0
0
1 1
B
B
...
... ... ...