Information Technology Reference
In-Depth Information
Σ
,
We construct a guided recombination system
R
=
(
∼
,A)
and a sequence
π ∈ Σ
∗
with the required properties. The alphabet is
Σ
=
S
∪Σ∪{
#
}∪{
$
i
|
0
≤
i
. The axiom, i.e., the target string to be achieved at the end of the
computation, consists of the final state of the TM bounded by markers:
≤
m
+
1
}
#
n
+
2
s
f
#
n
+
2
$
0
$
1
...
$
m
$
m
+
1
,
where
n
is the maximum length of the left-side or right-side words of any of
the rules of the TM.
The sequence
=
A
consists of the catenation of the right-hand sides of the TM
rules bounded by markers, as follows:
π
π =
$
0
$
1
e
1
v
1
f
1
$
1
$
2
e
2
v
2
f
2
$
2
...
$
m
e
m
v
m
f
m
$
m
$
m
+
1
,
where
i
:
u
i
−→
v
i
,1
.
If a word
w
∈
T
∗
is accepted by the TM, a computation starts then from a
strand of the form #
n
+
2
s
0
w
#
n
+
2
≤
i
≤
m
+
1 are the rules of TM and
e
i
,v
i
∈ Σ ∪{
#
}
, where we will refer to the subsequence start-
ing with $
0
as the “program” and to the subsequence at the left of $
0
as the “data.”
We construct the relation
π
defining the contexts guiding the computations
so that (1) the right-hand sides of rules of TM can be excised from the program
as circular strands which then interact with the data; and (2) When the left-hand
side of a TM rule appears in the data, the application of the rule can be simulated
by the insertion of the circular strand encoding the right-hand side, followed
by the deletion of the left-hand side.
With the help of these contexts, we can prove theorem 3—namely, that we
can simulate the computation of any given TM by a series of contextual inter-
and intramolecular recombinations.
Theorem 3 also implies that if a word
w
∈
T
∗
is in
L(TM)
, then #
6
s
0
w
#
6
∼
π
belongs to
L
a
(R)
for some
k
, and therefore it belongs to
L
i
a
(R)
for any
i
≥
k
.
This means that, to simulate a computation of the TM on
w
, any sufficiently large
number of copies of the initial strand will do. The assumption that sufficiently
many copies of the input strand are present at the beginning of the computation
is in accordance with the fact that there are multiple copies of each strand
available during the (polytene chromosome) stage where unscrambling occurs.
Note that the preceding result is valid even if we allow interactions of operation
3 between circular strands or within a circular strand.
The proof that a guided recombination system can simulate a TM and thus
any computation suggests that a functional macronuclear gene can be viewed
as the output of a computation performed on the micronuclear sequence.
CONCLUSIONS
We have described a model for the process of gene rearrangement in spirotrich
ciliates. Although the model is consistent with our limited knowledge of this
