Problem Solving in Automata, Languages, and Complexity

4.2 Examples of Turing Machines 167

(3) In the ith i eration t of the loop, A& reads a symbol 2,+1-i at state
41 and, depending on whether x,+1-i = 0 or 1, enters state q2 or 44, respec-
tively. Thus, state q2 remembers that zn+l-i = 0 and state q4 remembers
that zn+l-i = 1. Also, MA erases symbol xxt,+l-i after reading it.
(4) In state 42, it moves left until it finds the blank symbol B, then it moves
right to find pi and enters q3.

(5) In state q3, it checks whether xi = 0. If xi # 0, then it realizes that

Xi # Xn+l-i (since q3 remembers that xn+l-i = 0) and enters an infinite loop.
If A& finds that there is no symbol xi left (i.e., it sees B at state q3), then it
means the input length is odd, and MA also enters an infinite loop. If xi = 0,
then it erases it and goes to state q6, in which it moves right until it sees the
blank symbol B, and then changes back to state 41, ready to compare x,-i
with xi+l.

(6) Actions in states q4 and q5 are the same as those in q2 and 43, except

that they remember that xn+l-i = 1.

(7) When machine MA, at state 41, finds that no more symbol left to

compare, it halts in state h.

In the following, we show the computation of MA on input 0110:

(s, BOlIOB) l- (ql,BOllQ) I- (qz,BOli) k (qzr Boll) p (q2,BOll)

i- (qs,@U) k (q6,BBll) p (q6,BBl@) k (qdB11) k (q4,BBl)

k (($4, BI11) t- (qs,BB1) t- (q6,BB@i) i- (Q1,BBB) k (h,BBB!i!).^0

Example 4.4 Show thut the following function is Turing-computable:

f(x) = { ; ;;e;wzR for Some w E {o, 1)*,

Solution. This problem is similar to Example 4.3, except that it needs to
output w when input x is found equal to wwR. so, we modify 1 of Example
4.3 as follows:

After MA compares x:i with xn+l-i in the ith iteration, we do not

erase xxfi. Instead, we replace x; by xi (i.e., replace 0 by 0’ and 1 by

l’), where 0’ and 1’ are new auxiliary symbols. When all symbols

have been compared and x is found to be of the form wwR, we

have w’ left in the tape. We simply change it back to w and halt.

The complete machine is shown in Figure 4.4. The following is the trace
of this machine on input 0110:

(s, Bol1oB) I- (al, Bollo) t- (w Boll) I- (qa,BO11) p (qd!Oll)

k (qs,@ll) t- (@,BO’Ll) c (qs,BO’l@) t- (ql,Bo’lL) i- (qd0’1)

t- (q4, B&‘l) t- (45, BO’L) l- (q6, Bo’l’i!) l- (41, Bo’c) t- (q7, B0’1)

i- (47, @I) i- (q8,Bol) p (q8,BOl!!) t- (q9,BOlBB) t- (h, BolB)* - Cl