Information Technology Reference
In-Depth Information
CLASSIC COMPUTATIONAL MODELS
In order to study the computational power of the bio-operations underlying
gene rearrangement in ciliates, we compare them with the existing models of
computation. In this section, we introduce two classic models of computation,
the finite automaton and the Turing machine. The finite automaton has very
restricted computational power, but the Turing machine models the computing
capability of a general-purpose computer.
The finite automaton is a mathematical model of a system with a finite
number of internal states and with discrete inputs and outputs. The behavior
of the system is dictated by a finite number of rules that, given a state of the
system and an input, dictate what the next state of the system will be.
To formalize the notions of finite automaton and Turing machine, let us first
introduce some notations. An alphabet
Σ
is a finite, nonempty set of symbols
or letters. A sequence of letters from
Σ
is called a string (word) over
Σ
. (If
Σ ={
A,C,G, T
}
can be interpreted as a linear DNA strand.)
The words are denoted by lowercase letters such as
u, v,
, a word over
Σ
α
i
,
x
ij
. A word with 0
letters in it is called an empty word and is denoted by
λ
. The set of all possible
Σ
∗
, and the set of all nonempty
words consisting of letters from
Σ
is denoted by
Σ
+
.
A finite automaton is a construct
A
words by
=
Σ
Σ
(S,
,P,s
0
,F)
, where
is the input
alphabet,
S
is a finite set of states,
s
0
∈
S
is the
set of final states, and
P
⊆
S
× Σ −→
S
is a set of transition rules. A transition
rule
sa
−→
S
is a designated start state,
F
⊆
s
,
s, s
∈
S
,
a
∈ Σ
says that, if the automaton is in state
s
and reads
the input letter
a
, then it changes its state to the new state
s
and continues scan-
ning the input word. The language accepted by the automaton
A
is defined as:
L(A)
={
w
∈ Σ
∗
|
s
0
w
⇒
∗
s
f
,s
f
∈
F
};
in other words, the set of all input words that can take the automaton from the
initial state to a final state by successive applications (denoted by
⇒
∗
)ofthe
transition rules in
P
. In the hierarchy of computational models, finite automata
are the weakest.
At the other end of the spectrum of computational power is the Turing ma-
chine (TM), the accepted formal model of what we call computation. In a
Turing machine, a read/write head scans an infinite tape composed of discrete
squares, one square at a time. The read/write head communicates with a control
mechanism under which it can read the symbol in the current square or replace
it by another. The read/write head is also able to move on the tape, one square at
a time, to the right and to the left. The set of words that make a Turing machine
finally halt is considered its language.
Formally [20], a rewriting system TM
=
(S,
Σ ∪{
#
}
,P)
is called a Turing
machine if and only if (iff):
