Problem Solving in Automata, Languages, and Complexity

170 TURING MACHINES

l/l1 R

B/B, L

l/B, R

B/ 1,L

B/B, L

l/B, L l/l, R

Figure 4.7: DTM computing the function sub.

Solution. This is a simple modification of the last example. At each iteration,
we reduce both n and m. by one. That is, the configuration changes as follows
in each iteration:

(41, BliBl j-‘l) - p (al, Bli-1Blj-21).

We show the DTM in Figure 4.7. The computation of this DTM on inputs
(3,2) and (2,3) are as follows:

(s, B111BllB) - i- (ql,BlllB1l) k (q2,Bl11B1) - k (q2,B111B1) -

k (q3,B11111) t- (q4,B11B11) p (q4,B11B1113) k (qs,B1lBll)

t- (ql, BllBL) p (91, BIB) t- (q8, BIB@ i- (h, BIB). - -

(s, BllBlllB) t- (ql,B1lB1ll) p (ql,BIB1l) t-* (ql,BB1) t- (q2,B13)

k (43, !!I) t- (q6, Bi) t- (q6,Blii) t- (q7, Bii) k (47, B) t- (h B!!)- cl

Designing a Turing machine is just like designing a computer program,
except that here the programming environment is more restrictive (so, it is
similar to programming in assembly languages). In most programming envi-
ronments, when we have a complicated program in which certain part of it
is repeated many times, we can create a separate procedure for it and write
its code only once. This technique of software design can also be used in the
design of Turing machines. We illustrate this idea in the following example.

Example 4.8 For 1 < i < le, show that function 7rF @1,1x=2, l = l , Q) = xi on
natural numbers is TukngLomputable.