Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

348 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

(0, 0, R)

(0, X, R)

(1, 1, R)

(0, 0, R)

(B, B, L)

(0, B, L)

(X, X, R)

(X, 0, R)

(0, 0, L)

(1, 1, L)

(0, 0, L)

q 0

q 1 q 2 q 3

q 4

q 6 q 5

(1, 0, L)

Fig. 12.22

(0,0,R)

(0,0,R)

(1,1,R) (B,B,L)

(0,X,R) (0,B,L)

(X,X,R) (0,0,L)

(1,1,L)

(1,1,R)

(1,0,L)

(0,0,L)

(X,0,R)

(B,B,L)

(0,0,R) (1,0,L)

HALT

(0,B,L)

q 1

q 0

q 7

q 8 q^6

q 5

q 4

q 2 q 3

Fig. 12.23

Example 12.5 Construct the Turing machine for the natural function (f : Nk → N) which evalu-
ates the multiplication of two numbers, i.e., for numbers x and y, f(x, y) = x y.
Sol. Since the meaning of multiplication of x y is the successive addition of x, y times. This is
one of the computation logic which to determine the multiplication of two numbers. Initially