![[Previous]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsleft.gif)
![[Up]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsupar.gif)
Although the above Turing machine works, it is too simple to be a good test of our ability to implement arbitrary Turing machines in DNA. Until we have considered how to implement a universal Turing machine, a suspicion will remain that our methods might be restricted to a non-universal subclass of Turing machines. Therefore, we decided to find a universal Turing machine and study how to implement that particular machine in DNA. In order to maximize the possibility that the resulting DNA system would be simple enough for us to test in the lab, we decided to use the smallest universal Turing machine known. To our knowledge, the record is held by Minsky for the 4-symbol, 7-state universal machine described in [Minsky-67].
The transition table for Minsky's machine is given below. The symbol
alphabet is y, 0, 1, A. (A being
a logical symbol here, not a DNA base.) Each entry in the table gives
the new symbol, new state number, and direction of motion of the tape
head (Left or Right, or Halt). The operation of Minsky's machine is
complex and we will not discuss the details here.
Tape Head State
q1 q2 q3 q4 q5 q6 q7
----- ----- ----- ----- ----- ----- -----
Symbol y 0,1,L 0,1,L y,3,L y,4,L y,5,R y,6,R 0,7,R
being 0 0,1,L y,2,R 0,3,H y,5,R y,3,L A,3,L y,6,R
read 1 1,2,L A,2,R A,3,L 1,7,L A,5,R A,6,R 1,7,R
A 1,1,L y,6,R 1,4,L 1,4,L 1,5,R 1,6,R 0,2,R
When considering the rewrite rules for this machine we discovered a
serious problem with our technique of randomly walking forwards and
backwards along the Turing machine computation, namely that in general
(and for Minsky's machine in particular), a given configuration of a
Turing machine could have been reached from more than one possible
preceding configuration. This means that overall, there are more ways
for the computation to go backwards than forwards, and so on average,
it will go backwards. In this sort of reverse-biased random walk, the
expected time required to go a given distance forward from the initial
state is exponentially large. (In an unbiased random walk, the
expected time is only quadratic in the distance.) Fortunately, we can
eliminate this problem, and even reverse it, introducing a forward
bias which causes the machine to progress forwards linearly.
First, we can eliminate the problem of multiple possible previous states by simply converting Minsky's machine into an equivalent reversible machine. This is done by recording a history of the previous states as the computation progresses. (This is based on an idea from Bennett.) The execution of Turing machine steps is coupled with the production of history information, so that a step can only be reversed by erasing the corresponding piece of history information. To implement this history mechanism, we imagine a tape with two tracks, one for the normal tape contents, and one for the history information. The information on both tracks at a given position is represented by a single symbol encoded on the DNA strand. While the tape head places new information on the history track, simultaneously, other rewrite rules move old pieces or "particles" of history information out of the way (to the right of the tape head, say).
There is a fortunate side effect to this approach which actually forces the computation to go forwards. First, note that because of the limitations on oligo systems mentioned earlier, the rewrite rules that move history particles rightward along the tape are actually bidirectional rewrite rules, and so the history particles randomly walk in both directions. At first this might seem to be a problem, because we might think on average the particles would get nowhere. However, random-walking suffices to eventually "diffuse" the particles far enough away from the tape head (assuming there is enough room) to make room for more. Even better, because the position of history particles in uncertain, the entropy of the strand is greater when more history particles are produced. Therefore, producing more history particles is statistically favored. Another way to understand this effect is to note that there are simply exponentially more states the farther forwards we go, and since we are just doing a random walk through the state space, we are unlikely to remain for very long in the relatively small part of the space that lies towards the beginning of the computation.
____... Illustration of state space
____/ with exponential increase in
____/ \____... number of possible states as
/ \__ ... ___ computation progresses. A
____/ ____/ random walk in this tree
\ ____/ \___ will spend almost all its time
\____/ \____... towards the right (near the leaves).
\__ ...
Progress through computation --->
This emergent feature of forward progress has been verified by a
high-level simulation of a system of bidirectional string-rewrite
rules that randomly go either forwards or backwards, moving the tape
head and the history particles for Minsky's machine. The simulation
ignores the details of the particular DNA operations that would be to
traverse a rewrite rule. We determined that for Minsky's machine
there are at most 4 possible predecessors to any possible
configuration, and so we have 4 different history particles used to
record the history of logically-irreversible tape changes. For
simplicity, we restricted ourselves to 2-place rewrite rules with no
symbol insertions or deletions. The restriction makes it impossible
for the tape head to read the symbol on its right and swap places with
the symbol on its left in a single rewrite, but leftward tape-head
movements can still be accomplished in two steps: (1) reading the
symbol to the right and changing to a special state for moving left,
and (2) swapping places with the symbol to the left and changing back
to a normal state. The resulting string-rewriting system (below)
consists of 39 symbols and 139 2-place rewrite rules:
(4) y 0 1 A Tape symbols
(7) q1 q2 q3 q4 q5 q6 q7 Tape head state symbols
(5) Q1 Q2 Q3 Q4 Q7 Leftward-motion tape head state symbols
(16) 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
y 0 1 A y 0 1 A y 0 1 A y 0 1 A
(7) 1 2 2 2 2 3 4 Symbols for tape symbols and
q5 q2 q5 q6 q7 q6 q6 state symbols having history
particles on the parallel
history track "above" them.
Transition table rewrite rules (27):
q1 y q2 y q3 y q4 y q5 y q6 y q7 y
----- ----- ----- ----- ----- ----- -----
1 3 1 2 3 2
Q1 0 Q1 0 Q3 y Q4 y y q5 y q6 0 q7
q1 0 q2 0 q4 0 q5 0 q6 0 q7 0
----- ----- ----- ----- ----- -----
2 2 1 2 2 4
Q1 0 y q2 y q5 Q3 y Q3 A y q6
q1 1 q2 1 q3 1 q4 1 q5 1 q6 1 q7 1
----- ----- ----- ----- ----- ----- -----
2 1 2
Q2 1 A q2 Q3 A Q7 1 A q5 A q6 1 q7
q1 A q2 A q3 A q4 A q5 A q6 A q7 A
----- ----- ----- ----- ----- ----- -----
2 1 2 2
Q1 1 y q6 Q4 1 Q4 1 1 q5 1 q6 0 q2
Rules for leftward motion of tape head (20):
y Q1 y Q2 y Q3 y Q4 y Q7
---- ---- ---- ---- ----
Q1 y Q2 y Q3 y Q4 y Q7 y
0 Q1 0 Q2 0 Q3 0 Q4 0 Q7
---- ---- ---- ---- ----
Q1 0 Q2 0 Q3 0 Q4 0 Q7 0
1 Q1 1 Q2 1 Q3 1 Q4 1 Q7
---- ---- ---- ---- ----
Q1 1 Q2 1 Q3 1 Q4 1 Q7 1
A Q1 A Q2 A Q3 A Q4 A Q7
---- ---- ---- ---- ----
Q1 A Q2 A Q3 A Q4 A Q7 A
Rules for moving history particles away from the tape head (28):
2 2 1 2 3 2 4
q2 y q6 y q5 y q5 y q6 y q7 y q6 y
----- ----- ----- ----- ----- ----- -----
2 2 1 2 3 2 4
q2 y q6 y q5 y q5 y q6 y q7 y q6 y
2 2 1 2 3 2 4
q2 0 q6 0 q5 0 q5 0 q6 0 q7 0 q6 0
----- ----- ----- ----- ----- ----- -----
2 2 1 2 3 2 4
q2 0 q6 0 q5 0 q5 0 q6 0 q7 0 q6 0
2 2 1 2 3 2 4
q2 1 q6 1 q5 1 q5 1 q6 1 q7 1 q6 1
----- ----- ----- ----- ----- ----- -----
2 2 1 2 3 2 4
q2 1 q6 1 q5 1 q5 1 q6 1 q7 1 q6 1
2 2 1 2 3 2 4
q2 A q6 A q5 A q5 A q6 A q7 A q6 A
----- ----- ----- ----- ----- ----- -----
2 2 1 2 3 2 4
q2 A q6 A q5 A q5 A q6 A q7 A q6 A
Rules for moving history particles around freely on the tape (64)
For each particle p = {1, 2, 3, 4},
For each symbol a1 = {y, 0, 1, A},
For each symbol a2 = {y, 0, 1, A},
Include the following rule:
p
a1 a2
-----
p
a1 a2
In mixture mutagenesis, each of these rules could be encoded by a
series of several oligos that encode a path between source and result
substrings. There are also a large number of alternative flanking
sequences for these oligos that must be accounted for, because of the
issues mentioned in the previous section, but this is fairly
straightforward. Thus, it ought to be possible to design a mixture of
oligonucleotides implementing this machine. We can translate any
computer program into the language translated by Minsky's machine,
encode it on a DNA strand, and replicate it in the presence of this
oligo mixture, and the line of descendant DNA strands will, on average
over many steps, progress forwards in the execution of the given
program.
There is one more important point about this forward-progress issue, which is that it is actually not strictly necessary to record the history of execution and make the machine logically reversible to force it to go forward. All that is really required is that there be, on average, at least as many forward steps as backwards steps, so that the entropy of the system increases as the computation progresses. For example, suppose that typical machine configurations have 3 possible transitions that progress the computation forwards and 2 that take it back (see this figure). Such a machine is not logically irreversible, since it is impossible to tell which previous state it came from, but it will progress forward on average. Thus, it would suffice for us to write random particles of information on the tape instead of history particles, as long as this involves a large enough rate of information production to make up for the information lost when irreversible tape-head transitions are made.
Figure 3 : Illustration of a state in a logically irreverible computer that still spontaneously makes net forward progress.