Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

336 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Note: It is always remember that

1.Machine crashes if δ is not define or tape head crosses left most boundary.

For example, δ (q 0 , a) = (p, a, L) (from Fig. 12.1(a)) is not possible.

2.Machine is deterministic and without ∈-transitions.

12.2.3 Instantaneous Description (ID) of a Turing Machine

In this section we will describe instantaneous description of the Turing machine. Instantaneous

Description (ID) shows the sequence of moves and its configuration from one instant to next.

As we see that the status of the Turing machine (at any moment) is given by the contents

of the cell/s that already scanned, the present state, and the remaining nonblank cells entry

including the current tape head entry.

Fig. 12.2 shows the configuration of Turing machine at any time t, where M is in state q

and the tape cell entries are shown below,

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

a 1 a 2

M

q

Last non blank
symbol
Fig. 12.2
So, ID is given as, α 1 q α 2
where, α 1 and α 2 are the strings of nonblank symbols.
In general, ID is given by as, Γ Q Γ (because α 1 ∈ Γ, q ∈ Q and α 2 ∈ Γ)
We describe the moves of the Turing machine by notation that is called move relation.
And the meaning of is as usual, zero/one/more (finite) moves of Turing Machine M.
Hence, the meaning of I 1 I 2 tells that Turing machine M reaches from one instant (1)
to next (2) in exactly one step.
Further we see that the nature of is reflexive† and transitive‡ closure of ‘ ’.
From Fig. 12.2 the ID of TM M is,
α 1 q α 2
where, string α 1 = X 1 X 2 X 3 ...........XK and α 2 = XK+1 XK+2 ...........Xn (by assuming that X 1 X 2
X 3 ...........Xn is the portion of tape between left most and right most non blanks, i.e.
X 1 X 2 ......XK q XK+1 XK+2 ...........Xn X 1 X 2 .........XK Y p XK+2 ...........Xn,
if and only if ∂∂∂∂∂ (q, XK+1) = (p, Y, R) i.e. tape head move rightward.

† Suppose Turing machine presently in ID – I and it remains to ID – I in no move i.e.

IDI 0 IDI ; hence ‘ ’ is reflexive.

‡ Let TM M reaches from ID – I to J in one step and from J to K in some finite steps i.e.

IDI 1 IDJ and IDJ * IDK then M reaches ID – I to K in some fine steps.

i.e. IDI * IDK ; hence ‘ ’ is transitive.