Problem Solving in Automata, Languages, and Complexity

4.2 Examples of Turing Machines 169

l/O, R

B/O,R

/

B/O,R

$/B, L^6 O/B, l/B, L L k? O/O, l/O, R R

Figure 4.5: DTM of Example 4.5.

l/l, R

Figure 4.6:

B/B, L B/B, R

DTM computing the function rz.

(s, BllBlllB) - b (ql,BllBlll) t- (qz,BllBl1) c (q:,BllBll) -

I- (q3, Blllll) I- (s, BlBlll) c (sJlBlllI3) t-* (s, BBlllB) -

I- (ql,BBlll) t- (q2,BBlL) p (q2,BBll) I- (43,B111) l- (!?4,B111) -

c (q4,B111E3) t- (q5,BlllBB) t- (h,BlllB). -

(s, BllBF3) t- (~1, BllB) t- (43, BU) I- (s, BlBB) I- (h BIB) I- (Q39B1)

b (s,BBB) t- (ql,BB) I- (43,B) t- (q4,Ni) t- (as+@) t- hBB)- Cl

Example 4.7 Find a Turing machine that computes the function

sub(n, m) =

1

n-m ifn>m>O, - -

0 ifm>n>O. -