Information Technology Reference
In-Depth Information
also called automaton , which in its etymological sense means just “autonomously
evolving system”. If the system can input a program, as part of its data, by behaving
according to it, we say that the system is universal with respect to the class of pro-
grams it can input. If at each step the computation rule provides only one applicable
operation, then the resulting computation is deterministic as opposed to the more
general case of a nondeterministic computation. More general kinds of computa-
tions may assume the presence of interactions , that is, of exchanges of data during
the computation. In this case, the behavior of a system depends on the sequence
of data exchanged during these interactions. For example, in some state the system
can require a value from outside. This means that the system stops its computation,
by waiting for a value, and when it is provided (by means of an input device), the
computation continues, possibly providing output values during the computation.
A fundamental model of computation was elaborated by Alan Mathison Turing
in a famous paper published in 1936. It describes a general kind of computation
processes based on a very intuitive basis. This kind of computation develops by
transforming the contents of cells linearly arranged on a tape unbounded in the
two directions (see Fig. 6.6). One symbol is contained in each cell which belongs
to an alphabet A including a special symbol, say it B , called the blank symbol. A
system can assume internal states of a finite set Q and in each state can read the
symbol put in one cell (the current cell). A program, consisting of a finite sequence
of instructions , defines the action that the system can perform at any step of its
evolution. Any instruction has a pre-condition and a post-condition. A pre-condition
is given by a pair
. If the precondition of an instruction corresponds to the
current situation of the system, that is, q is the internal state of the system and a is
the symbol in the current cell, then the instruction can be applied according to its
post-condition, which is a tern
(
q
,
a
)
q ,
where b is the symbol which replaces the
symbol a in the current cell. The state q is the state which replaces q and m indicates
the current cell at the next step of computation. If m
(
b
,
m
)
=
L the (new) current cell is
located on the left of previous one, while if m
R on the right.
Any computation starts with an initial state (usually indicated by q 0 ), with a se-
quence of symbols over the alphabet A arranged in a contiguous portion of the tape,
and with the blank symbol B in all the cells outside this portion. At the beginning,
the system reads on the first cell on the left where a symbol different from B is writ-
ten (this is the initial current cell). When the machine stops, because no instructions
are applicable, the output is the string put on the tape between the two most extreme
symbols on the tape which are different from B .
The formal definition of A Turing machine follows.
=
Definition 6.7. A Turing machine M is given by the following structure:
M
=(
A
,
Q
,
q 0 ,
I
)
where A is the alphabet of its symbols , including the special blank symbol B , Q is
the finite set of its states , q 0
Q is its initial state ,and I the set of its instructions ,
that is, quintuples
(
q
,
a
,
b
,
p
,
m
)
where q
,
p
Q , a
,
b
A and m
∈{
L
,
R
}
.Theset I of
 
Search WWH ::




Custom Search