168 TURING MACHINES
Figure 4.4: DTM of Example 4.4.Example 4.5 Show thut {wwR ] w E {O,l}*} is Turing-decidable.
Solution. This time, we need to output 1 for z of the form wwR and output 0
for IX: not of this form. We recall that if MA of Example 4.3 finds ~~+l-i = 0
and x; = 1 for some i, then it will enter the infinite loop at state qs, and if
it finds xn+l-i = 1 and xi = 0, then it will enter the infinite loop at state
q5. So, we only need to add new states in which the machine can erase all
unprocessed symbols and output 0 from these configurations. The complete
new machine is shown in Figure 4.5. Note that we replace each xi by $ after
it is successfully matched with xn+l-+ This allows us to locate the leftmost
blank B and to put the output value 0 or 1 in the second cell. cl
Let N be the set of natural numbers. A natural number n E N can
be represented by string In. Based on this representation, we say a partial
function f : Nk + N is Turing-computable if the function f” : ({l})” --+ {l},
defined by J(P, P2,... , l”“> = lf@l)***>Q, is Turing-computable.
Example 4.6 Show that the function $(nl, nz) = n2, for nl, n2 E N, is
Turing-computable.
Solution. The idea of the machine is to create a loop, each iteration of which
moves the block ln2 one square to its left and reduces 1”’ to P-l so that
the configuration changes from (s, BP1Bln2B) to (s, Bln1-1Bln2B). We show
the complete DTM in Figure 4.6, and its computation on inputs (2,3) and
(2,O) as follows: