Problem Solving in Automata, Languages, and Complexity

166 TURING MACHINES

4.2 Examples of Turing Machines

We present some examples of Turing-computable functions and Turing-
acceptable and Turing-decidable languages.

Example 4.3 Show that A = {wwR 1 w E (0, l}*} is Turing-acceptable.

Solution. The general idea is simple. For each input x = 21~2 l l l x~, where
each lxfi is a symbol 0 or 1, we compare ~1 with xn, x2 with x,+1, and so on.
To do such a comparison, the DTM reads x~, remembers it and then moves
to the cell containing x1 and compares them. (By remembering a symbol, we
mean that the DTM moves into a state, or a subset of states, associated with
this particular symbol and performs the necessary action within it.) Based
on this idea, we construct a DTM MA for A whose transition function S is as
follows:

ex .ample, we also include a detailed description of MA:

s

S

41

!I2

(23

q4

45

q6

0

q2, J4 L

q2,0, L

q6, B, R

q490, L

I q6,0, R

1

44, B, L

4271, L

!I41 1, L

q6, B, R

!/S, 1, R

B

QlJJ

h,B, R

q3, B, R

45, B, R

QlAL

We also present its transition diagram in Figure 4.3. Since this is our first

(1) At state s, it moves left to find X~ and enters state 41.

(2) It then enters a loop from state q1 through either q2, q3, q6 or through

, 45, q6 then back to ql.

Figure 4.3: Machine MA of Example 4.3.