DHARM
N-COM\CMS12-1.PM5INTRODUCTION TO TURNING MACHINE 347
(x 1 + 1)0’s (x 2 + 1)0’s00001 BBBq 0 Breaker
Fig. 12.20
Turing machine starts the computation over input strings and at instance of state {q 2 } it
counts number of 0’s are (x 1 + 1 + x 2 + 1). Since it has an extra 0 so this extra 0 will be replaced
by symbol blank (B). Thus, at state {q 4 } numbers of 0’s counted are (x 1 + x 2 + 1). Finally,
machine stops at the state {q 5 } which is the left most end of the tape cells. Fig. 20.21 shows the
state diagram of the Turing machine for the function f.
(0,0,R)
(0,0,R)
(1,0,R) (B,B,L)(0,B,L)
(0,X,R)(X,X,R) (0,0,L)q 1 q (^2) q 3
q 0
q 5
Fig. 12.21
Example 12.4 Construct the Turing machine for the natural function (f : Nk → N) which
evaluates the proper subtraction, i.e., if x and y are two numbers then f(x, y) = x – y if x ≥ y, and
f(x, y) = 0, otherwise.
Sol. Assume Turing machine starts the computation from the starting state q 0. Since tape
cells contain a total of (x + 1) 0’s followed by (y + 1) 0’s and between them a breaker of symbol
- The machine computes the subtraction between numbers x and y using the following compu-
tation logic i.e.,- For the case if x ≥ y then (y + 1) 0’s must be crossed and they are all converted to
blanks with the corresponding 0’s of the string x which are converted to symbols X’s.
Fig. 12.22 shows the snapshots (from state q 0 to q 4 and returned to q 0 ) of the state
diagram for the discussed situation. Thus we have remaining 0’s of the string x in-
cluding a symbol 1. Symbol 1 is converted to 0 and since we have a lack of 0 so one
symbol X is also converted to 0. Thus machine will return a total of (x – y + 1) 0’s
hence it will stop at state q 6. The state diagram of the machine is shown in Fig. 12.22. - For the case if x < y then result should be 0. To implement this case, we will found
that in between the computation of crossing of 0’s of the string y corresponding to 0’s
of string x if there is no more 0’s left in the string x for the remaining 0’s of string y
then machine will search a new path. The state diagram of the Fig. 12.23 shows that
there is a new path from the state q 0 to q 8 and then halting state q 6 for this situation.
- For the case if x ≥ y then (y + 1) 0’s must be crossed and they are all converted to