Chapter 9: Turing Machines and Linear Bounded Automata ~ 279
Notes: (1) The acceptability of a string is decided by the reachability from the
initial state to some final state. So the final states are also called the accepting
states.
(2) (5 may not be defined for some elements of Q x r.
9.2 REPRESENTATION OF TURING MACHINES
We can describe a Turing machine employing (i) instantaneous descriptions
using move-relations. (ii) transition table. and (iii) transition diagram (transition
graph).
9.2.1 REPRESENTATION BY INSTANTANEOUS DESCRIPTIONS
.Snapshots' of a Turing machine in action can be used to describe a Turing
machine. These give 'instantaneous descriptions' of a Turing machine. We have
defined instantaneous descriptions of a pda in terms of the cUITent state. the
input string to be processed, and the topmost symbol of the pushdown store.
But the input string to be processed is not sufficient to be defined as the ill of
a Turing machine, for the R1\V head can move to the left as well. So an ill of a
Turing machine is defined in terms of the entire input string and the current
state.
Defmition 9.2 An ill of a Turing machine M is a string af3y, where f3 is the
present state of M, the entire input string is split as (Xl, the first symbol of y is
the current symbol (l under the RJW head and y has all the subsequent symbols
of the input string, and the string ex is the substring of the input string formed
by all the symbols to the left of a.
EXAMPLE 9.1
A snapshot of Turing machine is shown in Fig. 9.2. Obtain the instantaneous
descliption.
~~
.LI_b----,--I_84----,FGJ;J 821 82 ~ bib I
~?
dj
IWhead
State
q3
Fig. 9.2 A snapshot of Turing machine.
Solution
The present symbol under the RJW head is al' The present state is Q3' So al
is written to the right of Q3' The nonblank symbols to the left of al form the
string a4(lj(l2(lja2L72, which is written to the left of Q3' The sequence of nonblank
symbols to the right of (ll is (14(12. Thus the ill is as given in Fig. 9.3.
Notes: (1) The acceptability of a string is decided by the reachability from the
initial state to some final state. So the final states are also called the accepting
states.
(2) (5 may not be defined for some elements of Q x r.
9.2 REPRESENTATION OF TURING MACHINES
We can describe a Turing machine employing (i) instantaneous descriptions
using move-relations. (ii) transition table. and (iii) transition diagram (transition
graph).
9.2.1 REPRESENTATION BY INSTANTANEOUS DESCRIPTIONS
.Snapshots' of a Turing machine in action can be used to describe a Turing
machine. These give 'instantaneous descriptions' of a Turing machine. We have
defined instantaneous descriptions of a pda in terms of the cUITent state. the
input string to be processed, and the topmost symbol of the pushdown store.
But the input string to be processed is not sufficient to be defined as the ill of
a Turing machine, for the R1\V head can move to the left as well. So an ill of a
Turing machine is defined in terms of the entire input string and the current
state.
Defmition 9.2 An ill of a Turing machine M is a string af3y, where f3 is the
present state of M, the entire input string is split as (Xl, the first symbol of y is
the current symbol (l under the RJW head and y has all the subsequent symbols
of the input string, and the string ex is the substring of the input string formed
by all the symbols to the left of a.
EXAMPLE 9.1
A snapshot of Turing machine is shown in Fig. 9.2. Obtain the instantaneous
descliption.
~~
.LI_b----,--I_84----,FGJ;J 821 82 ~ bib I
~?
dj
IWhead
State
q3
Fig. 9.2 A snapshot of Turing machine.
Solution
The present symbol under the RJW head is al' The present state is Q3' So al
is written to the right of Q3' The nonblank symbols to the left of al form the
string a4(lj(l2(lja2L72, which is written to the left of Q3' The sequence of nonblank
symbols to the right of (ll is (14(12. Thus the ill is as given in Fig. 9.3.