Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

INTRODUCTION TO TURNING MACHINE 345

State Diagram

(B, B, R)

p

(B, B, R)

(X, , L)a

(Y, , L)b

(, ,R)aa

(, ,R)bb

(B, B, R)

(B, B, L)

(L)a, a,

(L)b, b,

(L)a, a,

(L)b, b,

(X,R)a,

(B, B, L)

q

(B, B, R)

(Y,R)b,

(, ,R)aa

(, ,R)bb

(, ,R)aa

(, ,R)bb

(B, , L)

b

(B, , L)

a

(, ,R)bb

(, ,R)aa

(X, X, R)

(Y, Y, R)

Fig. 12.17

12.5 Turing Machine is the Computer of Natural Functions...............................................

Let f be a function defined on natural numbers N such that
f : Nk = N (for arbitrary k)
Alternatively, we can represent the function f(x 1 , x 2 , ........ xk) = y. Reader must remind
that functions can be classified into total functions and partial functions. Total functions are
those functions which are defined for all input parameters. Conversely, if the functions are not
defined for all input parameters then those functions are called partial functions. For exam-
ple, the function
f(x 1 , x 2 , ........ xk) = x 1 /x 2 ; if x 2 ≠ 0
is an partial function. Natural functions can be evaluated by the Turing machine. For, total
functions we always construct a recursive Turing machine while for the partial functions we
can construct a Turing machine which never stop.

Procedure for Computation of Natural functions

Consider an natural function f(u, v) = w, i.e., u, v and w ∈ N, where u and v are two inputs and
w is the output of the function these are all decimal numbers. We make assumption that
decimal numbers are represented by a stream of zeros, for example,