Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

INTRODUCTION TO TURNING MACHINE 337

This situation is shown in Fig. 12.3.

X 1 ............ XK XK+2 ............ XN B B .........

M

p

Last non blank

symbol

Y

T

Fig. 12.3

The limitations of this move are:

• If tape head points to the rightmost nonblank cell that is XK = XN then next to its
  right is blank. Thus,
  X 1 X 2 ......Xn–1 q Xn X 1 X 2 .........Xn–1 Y p B and no more ID.


• If tape head point to the Ist cell and Y = B, that is symbol X 1 is replaced by B. That
  causes infinite sequence of leading blanks and not appears in the next ID. So,
  q X 1 X 2 ...........Xn p X 2 ...........Xn
  Suppose ∂∂∂∂∂ (q, XK+1) = (p, Y, L) i.e. tape head move leftward then,
  X 1 X 2 ......XK q XK+1 XK+2 ..........Xn X 1 X 2 .........XK–1 p XK Y XK+2 ...Xn,
  This situation is shown in Fig. 12.4.

X 1 ............ XK–1 XK+2 ............ XN B B .........

M

p

Last non blank

symbol

XK Y

Fig. 12.4

12.2.4 Representation of a Turing Machine................................................................

We can represent the moves of the Turing machine by state diagram or by transition table. For

example the move

∂(q, a) = (p, X, R)

is represented by the state diagram shown in Fig. 12.5

qp

( , X, R)a

Fig. 12.5
It tells that machine is in state q reading the input symbol a and it perform the operation
to replace the symbol a by X and the head moves right of the current cell and ready to read the
next symbol, these situation are clearly smalised in Fig. 12.6(a) & (b).