
\blankpage

\chapter{Machines and Motifs}
\label{ch04}

In this chapter, we show how to build up a clocked programming system
based on the transitions introduced in Chapter~\ref{ch02}.
We start by looking at larger scale transitions called motifs and
then describe an instruction
stack, loops, conditionals
and finally an example application.
Because this builds substantially on earlier research,
we begin with a brief review in which we describe
previous construction techniques using our simple language of states
and transitions.

\section{A Brief Review of DNA Construction Motifs}

\subsection{Tape Motif}

Many machines use a motif that selectively
attaches and detaches two segments end to end.
The motif makes use of three labels, along with their complements.
The segments to be attached to one another
will be labeled $a$ and $b$; the additional
third label $t$ will serve as a ``tab''
specific to the operation of the motif.
While there may be several different segments
labeled $a$ and $b$, the motif attaches
any un-hybridized instance of $a$ to any
un-hybridized instance of $b$ arbitrarily.
Although this non-deterministic behavior
may suffice in some circumstances,
it is usually better to constrain
the un-hybridized instances of $a$ and $b$
so as to avoid ambiguity.

In addition to the $a$ and $b$ labels
already present in the target machine,
the motif also makes use of two additional
strands, which are complements of one another.
We might refer to these as $tape_{ab}$ and $untape_{ab}$.
\index{tape}%
\index{untape}%

In the example shown in Figure~\ref{fig:tape},
we have $ tape_{ab} = [\overline t \overline b \overline
a]$, and thus $untape_{ab} = [a b t]$.
The strand $tape_{ab}$ will hybridize to
both $a$ and $b$, thus attaching them
end to end and leaving an unhybridized tab $\overline t$.
The strand $untape_{ab} = \overline{tape_{ab}}$
is the complement of
$tape_{ab}$. 
Thus, by pouring in $untape_{ab}$,
the tab is hybridized, and $tape_{ab}$ is displaced because
the sequence of hybridized pairs is longer\citep{yurke, zhangseelig}.

This leaves $a$ and $b$ again unhybridized,
along with an absolutely stable duplex
component formed by the hybridized tape and untape strands.
This stable duplex 
will not react with any other components,
so it can safely be ignored and we will consider it simply as $waste$.
\index{waste}%
The stabilization process of both the
untaping and the taping are demonstrated
in Figure~\ref{fig:tape_stab} and Figure~\ref{fig:untape_stab},
respectively.

\begin{figure}[hbt]
	\centering
	\includegraphics{ch4-fig01.eps}
\caption[The tape motif]{The complete
stabilization diagram for the tape motif.
The hats in the 
figure are represented as carets.}
	\label{fig:tape_stab}
\end{figure}

\begin{figure}[hbt]
	\centering
	\includegraphics{ch4-fig02.eps}
\caption[The untape motif]{The complete
stabilization diagram for the untape motif.
Note that the displace transitions are
separating, thus guaranteeing that the
stabilization is unidirectional, and the
resulting components are stable and not merely semistable.}
	\label{fig:untape_stab}
\end{figure}

Because these transitions are strongly unidirectional,
we don't need to concern ourselves
with the details of the stabilization
diagram. A user can view the situation as: add
various fuel strands as inputs and see the stabilized complexes as a result.
To reflect this simplified viewpoint, we introduce a state
diagram for the machine 
in Figure~\ref{fig:tape}.
This will be a simple two state machine
with inputs and outputs. 


\begin{figure}[hbt]
	\centering
	\includegraphics{ch4-fig03.eps}
\caption[A user level state diagram for
the tape motif]{ A simplified state diagram
for the tape motif, in which the segments
$a$ and $b$ are taped together. 
Transitions are listed with $input/output$ notation.
Note that $tape_{ab} = [ \overline t^0 \overline
b^0 \overline a^0 ]$ and $untape_{ab} = [ a b t ]$.
Also, in this case we have $waste = [
\overline t^0 \overline b^0 \overline a^0 | a^0 b^0 t^0
]$. Because the waste is hybridized, it is stable, so
plays no further role in any reaction. }
	\label{fig:tape}
\end{figure}


\subsection{Walkers and Gears}

By using a repeated tape motif, we can
selectively cause feet to ``walk'' alternately
across a track of footholds. The tape motif can also cause the teeth
of gears to mesh with one another.
\index{walker}%
This concept has been used to develop
walkers with a standard alternating
bipedal gait\citep{walker} and walkers having 
a staggered gait in which they keep one ``foot''
constantly forward\citep{walker_nonalt}.
In order to impose directionality, there
must be at least three differently labeled
footholds on the track, such that stepping
forward with a leg would necessitate a
different tape than stepping backwards.
So consider the feet to be labeled by $x$ and $y$ and
consider the track footholds to be labeled by $a$, $b$, and $c$.

Because each step requires a tape strand
to place the foot and an untape strand
to lift it, there will a total of 12 different fuel strands.
Thus, 
the walker is effectively a cyclical 12-state
machine. During each cycle,
the walker progresses six steps along the track.
Of course, this is only one among many variants.

\begin{figure}[p]
	\centering
	\includegraphics{ch4-fig04.eps}
\caption[A cyclical walker]{The cyclical walker motif.
Only one direction is annotated, but by
following the arrows backwards and substituting
$tape$ for the corresponding $untape$
and vice-versa, the walker could easily
move the other direction along the track.
Waste produced by the $untape$ steps is
omitted for clarity, as waste strands play no further role.
Note that the toehold label alternates to avoid unwanted interactions.
Also, note that $untape_{bx}$ will essentially
transition from the last state to the
first---albeit with a 6-step shift---thus completing the cycle.}
	\label{fig:walker}
\end{figure}

\subsection{Polymer Growth}

Another example of a machine motif 
is the growing polymer machine\citep{polymer}.
\index{growing polymer}%
The polymer consists of double stranded
DNA, one of whose endpoints will
be called an anchor and the other a payload. 
Both endpoints remain attached to the
same unique polymer throughout the operation
of the machine. Growth of the polymer occurs from the middle.
This machine operates
spontaneously and asynchronously
in solution, growing as long as there is fuel in solution.
Two types of hairpins are used to fuel
the device.
Each hairpin fuel will first hybridize onto the polymer,
and then insert itself into the polymer
by way of a double branch migration.

An application of this machine might be to separate two payloads.
By combining several such mechanisms to
a single pair of payloads, much larger
payloads could be moved; however, at a
certain distance, the stiffness of duplex DNA may be overwhelmed.
By using appropriately modified fuels,
it is also possible to leave single stranded
sticky ends at regular intervals along the polymer.
Thus, such a machine could be modified
to grow tracks for walkers. 
For that purpose, more
fuel types would be needed in order to
provide the pattern of three distinct
footholds necessary to impose directionality.
Alternatively, when multiple polymers
are used in parallel, such sticky ends
might be used to anchor lateral support
structures in the manner of a truss.


\section{A Clocked Stored Program DNA Machine}

The machines that have been
described make use of a single primary
component interacting with simple fuel
strands or hairpins. 
For example, we might describe the earlier
tape-untape machine as in Figure~\ref{fig:tape}.
This concept can be naturally extended
to multiple state machines with interacting inputs (in the
form of fuel strands) and outputs (waste strands).
One can anchor such state machines
to some easily manipulated
substrate, such as 7 kilobase DNA origami\citep{origami}.
\index{origami}%
The anchors would consist of  ``tabs'' similar to those
\index{tab}%
used in the walker motif and can be attached to the substrate
via hybridization,  ligation, or
proteins with sequence specific binding
sites. By releasing a tab, a user might remove an entire
programmatic ``module'' if needed.
\index{module}%
This setup would thus allow for the removal or addition
of large numbers of possibly heterogeneous components at will.

One intriguing application of such a module
would consist of a stack motif
that releases precisely programmable output
patterns with support for flow control,
looping, variable iteration, and more.
This simple new mechanism allows clocked stored program DNA computing.
\index{clock}%


\subsection{Clocked Instruction Stack}

As we've seen,
many machines require specific sequences
of fuel strands or fuel hairpins to be
added to the reaction vessel in a specific
sequence; for our purposes, we will refer
to such strands or hairpins as \textit{instructions}.
Here we propose a mechanism for
storing a sequence of such instructions
in a stack and then releasing them in a controlled way based on a clock.
Our clocking mechanism requires
two distinct fuel strands
that we call \textit{tick} and \textit{tock}.
\index{tick}%
\index{tock}%

Assuming the stack is already built, it will operate as follows.
First, \textit{tick} is added to solution,
which partially hybridizes to a corresponding
exposed sticky end of the stack.
The remaining end of the tick strand proceeds
to displace the remainder of the strand
to which it is hybridized by way of a single branch migration.
This produces a waste component of duplex
DNA consisting of the tick strand and
its complement, leaving an exposed sticky end on the stack.
Second, \textit{tock} is added to solution,
which likewise partially hybridizes to this sticky end.
Once again, a single branch migration
displaces tock's complement and ligates to the instruction payload.
This releases the instruction payload 
from the stack and ligates the payload to a duplex of tock and its complement.

In addition to operating as a sequence of instructions, the stack can 
operate 
as a standard stack data structure.
The two stage cycle of \textit{tick} and
\textit{tock} can be thought of as a single \textit{pop} operation.
Similarly, the two stage cycle of adding
the desired instruction, along with an
additional ``taping'' strand---namely,
tick's complement---implements the \textit{push}
operation. Repeated pushing can be used to synthesize such stacks.
\index{push}%
\index{pop}%
\index{stack}%
(Pushing instructions onto data stacks is one classic way in which
malicious hackers gain control of other people's machines.
Hacking DNA machines in the same way could eventually be a problem.)

\subsection{Linear (Straight Line) Program}

The actual mechanism operates in a similar
manner to the tape motif, except that 
tabs are staggered and overlap with one another.
For simplicity, we will refer to
every instruction payload as a single
segment $p$, regardless of hairpin topology
or instruction individuality, because
this does not affect the functioning of
the instruction stack, provided payload segments
have sequences that prevent them from binding inappropriately to tick
or tock.
\index{program, straight line}%

The basic alphabet required to make the clock work consists of two strands
denoted by the labels $\alpha$ and $\beta$,
along with their complements $\overline \alpha$, $\overline \beta$.
Pairs of these 
basic units will then be concatenated to form four distinct connected
strands: $[ p \alpha \beta]$ and $[ \overline
\alpha \overline \beta ]$ make up
the stack component; $[ \overline \beta \overline \alpha ]$ 
and $[ \beta \alpha ]$ play the role of
\textit{tick} and \textit{tock}, respectively.
A stack component, consisting of three instructions,
\index{instruction}%
\index{stack}%
could then be constructed as shown in
Figure~\ref{fig:stack}. 

\begin{figure}[hbt]
	\centering
	\includegraphics{ch4-fig05.eps}
	\caption[The stabilization of the $tick$]{The
stabilization diagram for the $tick$ motif of the stack consists
of a hybridization followed by a separating displace.}
	\label{fig:tick_stab}
\end{figure}

\begin{figure}[hbt]
	\centering
	\includegraphics{ch4-fig06.eps}
	\caption[The stabilization of $tock$]{The
stabilization diagram for the $tock$ motif of the stack.
Tock stabilization is essentially identical
to the $tick$ stabilization, except that
the released ``waste'' double strand is linked
to the desired instruction payload, here denoted by $p$.}
	\label{fig:tock_stab}
\end{figure}

The operation
of the machine will be as follows.
In the initial state of the machine,
the un-hybridized $\overline \alpha$ segment acts
as a toehold. The ligated $\overline \beta$ segment
\index{toehold}%
serves to block the release of the first instruction.
The addition of the first \textit{tick}
strand ($[ \overline \beta \overline \alpha ]$ )
in the proper stoichiometry serves
to displace this strand from the right and ready the first instruction.
\index{displace}%
The addition of \textit{tock} 
($[ \beta \alpha ]$)
then displaces
and releases the first instruction from
the stack, thus returning the stack to
a state analogous to the initial state but with one
less instruction on the right.

This process can be repeated as long as
there are instructions available on the stack.
We can utilize the $x$ segment in the
``last'' (leftmost) strand to anchor the stack to
other components or protein structures with appropriate binding sites.
Several variations 
of such motifs are possible. 
These will be discussed in 
Section~\ref{sec:considerations}.

\begin{figure}[p] 
	\centering
	\includegraphics[height=40pc]{ch4-fig07.eps}
	\caption[The operation of a stack]{The
operation of a stack from the user's perspective.
This stack contains three instruction
payloads, each of which consists of simply the label $p$.
The label $x$ may be used to anchor the
stack to some substrate such as DNA origami
or some protein with binding specificity.}
	\label{fig:stack}
\end{figure}

While we can describe the state of a stack
using the formalized component syntax, this quickly becomes cumbersome.
For that reason, it is useful to use a more streamlined stack notation.
So, for example, we might show the stack of Figure~\ref{fig:stack} 
as

\begin{center}
	\begin{tabular}{ | r@{/}l | }
		\hline
		$tick$ & \\
		$tock$ & payload \\
		$tick$ & \\
		$tock$ & payload \\
		$tick$ & \\
		$tock$ & payload\\
		\hline
	\end{tabular}
\end{center}


\subsection{Gating and flow control}

The previous example showed a straight line program.
We can introduce branching
behavior by using a strand-controlled gating mechanism.
Attaching an initial \textit{gate}
strand $[ \overline \alpha \overline \mu ]$ to the
toehold in the initial state stops the stack from operating.
However, upon addition of the strand $[ \mu
\alpha ]$---which we might deem $unlock_{\mu}$---the
gating strand will be displaced. 
Unlocking places the stack in a ready state, so
subsequent additions of \textit{tick}
and \textit{tock} release instruction strands as usual.
\index{program, branching}%
\index{flow control}%
\index{gate}%

This motif allows a compiler to support branching and other
program control functionality by building
multiple stack groups, each having a different gate strand.
Depending on the sequence of some particular unlocking
$\mu$, 
a stack from one group or another would be unlocked.
For example, there may be one stack keyed
to the label $\mu$, another stack keyed
to the label $\nu$. Both still
operate using the same clock strands once unlocked.
This allows for zero, one, or both of
these instruction blocks to be executed
depending on the presence of zero, one, or
both of $[ \mu \alpha ]$ and $[ \nu \alpha ]$.
This permits a kind of trigger-based programming in which 
\index{trigger-based programming}%
unknown inputs cause a DNA program to ``branch'' to one stack or another,
because the inputs unlock a particular strand.


\begin{figure}[hbt]
	\centering
	\includegraphics{ch4-fig08.eps}
	\caption[unlocking stack]{The stabilization diagram for a gated stack.
First there is a hybridization and then a displacement.
Unlocking is thus similar to a $tock$.}
	\label{fig:stack_lock_stab}
\end{figure}

The resulting program snippet begins with an unlock operation
\index{gate}%
\index{unlock}%
and then clocks through an arbitrary number of payload
instructions as shown in the box below.

\begin{center}
	\begin{tabular}{ | r@{/}l | }
		\hline
		$unlock_{\mu}$ & \\
		$tick$ & \\
		$tock$ & payload \\
		$tick$ & \\
		$tock$ & payload \\
		$tick$ & \\
		$tock$ & payload\\
		\hline
	\end{tabular}
\end{center}



\subsection{Looping}

There is also the possibility of looping
\index{program, looping}%
behavior if stoichiometry is appropriately set.
Suppose there are $n$ target machines
and $m n$ copies of the stack.
By introducing $n$ unlock strands, $n$ stacks will be unlocked.
Subsequent tick and tock strands will execute the instructions
in those stacks.
This leaves $n(m-1)$ gated copies of the stack remaining.
If each copy of the stack then includes
a copy of the
unlock strand as its last instruction, another $n$ stacks will
be unlocked after the first set of $n$ stacks complete. 
That is, each execution of $n$ stacks corresponds to an iteration of the loop.

The looping program snippet begins with an unlock operation
and then clocks through an arbitrary number of payload
instructions ending in an unlock operation, as shown in the box below.

\begin{center}
	\begin{tabular}{ | r@{/}l | }
		\hline
		$unlock_{\mu}$ & \\
		$tick$ & \\
		$tock$ & payload \\
		$tick$ & \\
		$tock$ & payload \\
		$tick$ & \\
		$tock$ & payload \\
		$tick$ & \\
		$tock$ & $unlock_{\mu}$\\
		\hline
	\end{tabular}
\end{center}



\subsection{Iterated variables}
\label{sec:variables}

By combining this technique with other
gates, {\em for} and {\em while} statements are possible.
\index{program, iterated}%
\index{for statement}%
\index{while statement}%
For example, the $m n$ stacks might not 
all be identical.
To stage them, there  might be
$n$ copies having one kind of gate, another $n$ having a different kind
of gate and so on.
If the last instruction of each of the $n$ stacks 
from collection
$i$ has an unlock
for a stack from collection of $i+1$,
we can simulate an iteration variable.

Alternatively, we can use a separate \textit{variable
stack} which is operated by unique strands.

For example, consider the situation in
which the user would like to operate a
walker, but progress the walker forward
only one step per loop instance, releasing some
set of instructions after each step.
One could construct a stack consisting
of the standard walker-driver instructions,
\index{walker}%
but, instead of 
being fueled by the
general \textit{tick} and \textit{tock}
strands, it will be fueled by a different pair of strands.
We might refer to these strands as $call_0$
and $call_1$. These will be used to deploy
the \textit{tape} and \textit{untape}
strands (which must be called twice).
Thus, the primary loop stack will be:

\begin{center}
	\begin{tabular}{ | r@{/}l | }
		\hline
		$gate_{\mu}$ & \\
		$tick$ & \\
		$tock$ & $instruction_1$ \\
		$tick$ & \\
		$tock$ & $instruction_2$ \\
		$tick$ & \\
		$tock$ & $instruction_3$ \\
		$tick$ & \\
		$tock$ & $call_0$ \\
		$tick$ & \\
		$tock$ & $call_1$ \\
		$tick$ & \\
		$tock$ & $call_0$ \\
		$tick$ & \\
		$tock$ & $call_1$ \\
		$tick$ & \\
		$tock$ & $unlock_{\mu}$ \\
		\hline
	\end{tabular}
\end{center}

And the secondary variable stack will look like:

\begin{center}
	\begin{tabular}{ | r@{/}l | }
		\hline
		$call_0$ & \\
		$call_1$ & $tape_{ax}$ \\
		$call_0$ & \\
		$call_1$ & $untape_{cy}$ \\
		$call_0$ & \\
		$call_1$ & $tape_{by}$ \\
		$call_0$ & \\
		$call_1$ & $untape_{ax}$ \\
		$call_0$ & \\
		$call_1$ & $tape_{cx}$ \\
		$call_0$ & \\
		$call_1$ & $untape_{by}$ \\
		$call_0$ & \\
		$call_1$ & $tape_{ay}$ \\
		$call_0$ & \\
		\multicolumn{2}{|l|}{\text{continues\ldots}}\\
		\hline
	\end{tabular}
\end{center}

\begin{center}
	\begin{tabular}{ | r@{/}l | }
		\hline
		\multicolumn{2}{|l|}{\text{continued\ldots}}\\
		$call_1$ & $untape_{cx}$ \\
		$call_0$ & \\
		$call_1$ & $tape_{bx}$ \\
		$call_0$ & \\
		$call_1$ & $untape_{ay}$ \\
		$call_0$ & \\
		$call_1$ & $tape_{cy}$ \\
		$call_0$ & \\
		$call_1$ & $untape_{bx}$ \\
		\hline
	\end{tabular}
\end{center}



The strategy is to have the instruction in the loop
``call'' the variable by way of issuing
a ``pop'' instruction specific to the
\index{call}%
\index{pop}%
variable stack which stores the values of each interaction.



\subsection{Considerations}
\label{sec:considerations}

Instructions will interact with some DNA target in the course
of executing the DNA program. One challenge is to prevent
this interaction from happening too early before the relevant
instruction is released.
One mechanism may simply rely on physical
distance, perhaps by attaching the stack
and the target to different rigid
substrates, with enough separation so as
to avoid interaction as long as both remain attached.
When tock releases an instruction strand from the stack,
it will be free to travel though the solution
to its target machine in order to do its work.
\index{anchoring}%

Another method may be to rely on extrinsic knotting and linking topology.
Instructions may be attached by both endpoints
to the stack, thus requiring two clock
cycles to fully release an instruction.
This would prevent the instruction segment
from binding prematurely, because the helical structure of duplex DNA
would prevent it from
wrapping around its target complement.

Fortunately, utilizing hairpin instructions,
\index{hairpin}%
rather than linear strands would provide
\index{linear strands}%
the same safeguards, while only requiring
a single end to be bound to the stack.
A large class of
machines can be constructed using only
hairpin-type fuels\citep{hairpin_system}.
That is the approach we take in our experimental section.

An additional challenge is to avoid race conditions.
\index{race condition}%
If tick and/or tock strands are not completely consumed
in the time they have to stabilize,
some
copies of the stack may release instructions too soon. 
For example, suppose tick strands remain when tock strands are added.
As usual, an instruction will be released by a stack after the tock
is added. But then, as a result of the
leftover tick strands,  a tick may hybridize to the same stack.
If there are also leftover tock strands, 
then an additional instruction may be released.
We call such a stack a {\em runahead} stack.
\index{runahead stack}%

The basic approach to solving this problem is to remove
excess unreacted strands.
This might be accomplished by binding
the tick/tock strands to a more easily manipulated
substrate, such as a protein which can then be flushed
In this approach, the tick and tock strands
could be engineered to include sequences
recognized by the binding sites of some
protein, which can then be flushed from solution.
\index{flushing}%

An alternative possibility is to bind the
complement of the clock strands 
to some substrate, perhaps even collectively to a single large origami.
\index{origami}%
After pouring tick into solution, for
example, and allowing for sufficient time
to stabilize, the perfect complement to tick would be added.
While the complement of tick does contain
a segment that can hybridize to the open toehold
of a stack, the longer match with tick
should dominate and displace any such hybridizations.
This approach also has the advantage that
once a clock strand has hybridized to its
perfect complement, the resulting component
will be completely stable, having no toeholds
with which to react with another component.

Perhaps the simplest approach is to coat iron balls with complements
\index{iron balls}%
to tick strands and to put those iron balls into the solution
when it is time to flush away  excess ticks.
Another set of iron balls coated with tocks could also be used
to flush away tocks.
It is an experimental question to determine the best
way to flush away extra tick/tocks.

\subsection{Example Applications}

\subsubsection{Signal Amplification}

A simple application of such stacks is
to use them for signal amplification.
\index{signal amplification}%
This application uses a gated stack whose instructions are all the same.
The gate-unlock strand opens the stack and
the ticks and tocks cause more and more copies of the instructions
to be produced.
Several different types of gates and amplified instructions may be used.
Because the same instruction is repeated
for the entire lifetime of the stack,
runahead stacks are acceptable.

\subsubsection{A Stack Controlled Walker}

In the case of a cycled walker, a repeating
sequence of 12 strands is required to operate the machine.
\index{walker}%
This can become cumbersome and makes automation,
such as by robotic pipettes, a complex proposition.
By utilizing a looping stack module, such
a walker may be driven by the simple alternating
addition of tick and tock.
This has the cost of requiring twice as
many \textit{pour} operations, because
releasing one fuel strand requires the application of tick and tock.
However, the fact that there are only
two fuel types required to drive the walker
greatly simplifies lab procedures, reduces
the possibility of user error, and simplifies automation.

These instruction stacks may be either attached to
the same substrate as the walker, providing
a self-contained system, or attached to
a different substrate as a unique ``driver module.''
The driver module can determine
the direction the walker takes along the track
by reversing the order of the tape-untape
strands required to move the walker's feet.
\index{driver module}%
Thus, one module can be constructed for
the ``forward'' direction, and another
module---identical but for the reversal
of instructions on the stack---can be
constructed for the ``backward'' direction.
By adding or removing these modules, the
direction of the walker can be controlled
while nonetheless using the same general tick and tock strands.

\begin{figure}[hbt]
	\centering
	\includegraphics[width=.6\textwidth]{ch4-fig09.eps}
	\caption{Operation of a clocked walker by way of a programmed stack}
	\label{fig:stack_walker}
\end{figure}

Alternately, we might control a walker's
directionality by using gated stacks.
\index{gate}%
This is analogous to controlling the direction
of the walker ``at runtime'' rather than ``at compile time''.
Rather than using the looped module, we would use two
types of gated stacks. 
One stack will have a gate for the ``forward''
direction, followed by a 12 instruction cycle.
The other stack will have
a gate for the ``backward'' direction
and a similar 12 instruction cycle for moving the walker backwards.
Initially, one of the two gate-unlock
strands will be introduced into solution,
and thereby unlock the appropriate stack.
After 12 clock cycles, the desired direction
will have to be chosen again by introducing
another gate-unlock strand signifying the direction.
\index{unlock}%

This idea can be extended to that of precisely
controlling a walker on a two-dimensional grid.
\index{walker, two-dimensional}%
This requires two types of tracks: a ``north-south''
track and an ``east-west'' track.
These two sets of tracks will intersect at
every 6 footholds---12 instruction steps---in order to form a grid.
By now utilizing 4 types of gated stacks,
one for each of the cardinal directions,
a clocked DNA computer can control
a walker's movement about such a grid precisely.
At each grid intersection, 
one of the 4 cardinal directions can be chosen
by introducing the appropriate unlock strand.

\section{Future Theoretical Work}


Here is a summary of what we have accomplished so far:
\begin{enumerate}
\item
A simple language to describe strands, their hybridization, ligation, strand
loops,
and so on.
\item 
A language describing the main transitions that are possible 
(e.g., hybridize, displace, 
exchange). 
\item
A method to combine
elementary transitions with known motifs to support ``stacks,'' each
of which contains a sequence of transition instructions.
\item
A further method based on gates on stacks to support
conditionals, program looping and subroutines.
\end{enumerate}

With these steps, we have shown how to store programs inside DNA.
The execution of these programs will require only clock ticks and tocks
and some means to flush them.
That is the good news.
But it's just a beginning.

The primary benefit of the stored program computing concept is that
instructions, data, and a problem input can all lie inside the computer.
We have already seen how instructions can lie in a DNA soup as 
instruction stacks.
Input DNA can simply be poured in.
We have not yet discussed data structures.
Data structures that store information basically have the structure
of a key-value pair.
\index{data structure}%
\index{key-value pair}%
Such structures support the query ``what is the
value associated with key k?''
We can construct a DNA key-value data
structure as follows: each key is implemented as a gate
and an associated value is implemented as a stack of strands that willb
be released with ticks and tocks.
There are many variant ways to do this.

This framework implies that programming can begin.
While the system we offer has instructions, conditionals, loops
and elementary subroutines, vastly different programming
paradigms might be possible.
We revisit this question after validating our ability
to build clocked DNA stacks.

\clearpage

