Programming in Biomolecular Computation
Our goal is to provide a top-down approach to biomolecular computation.
In spite of widespread discussion about connections
between biology and computation, one question seems notable by its absence:
Where are the programs? We introduce a model of computation that is evidently programmable,
by programs reminiscent of low-level computer machine code; and at the same time biologically plausible: its
functioning is defined by a single and relatively small set of chemical-like reaction rules.
Further properties: the model is stored-program: programs are the same as data, so programs are not only executable,
but are also compilable and interpretable. It is universal: all computable functions can be computed
(in natural ways and without arcane encodings of data and algorithm); it is also uniform: new "hardware"
is not needed to solve new problems; and (last but not least) it is Turing complete in a strong
sense: a universal algorithm exists, that is able to execute any program,
and is not asymptotically inefficient.