Programming in biomolecular computation
Research output: Contribution to journal › Conference article › Research › peer-review
Standard
Programming in biomolecular computation. / Hartmann, Lars Røeboe; Jones, Neil; Simonsen, Jakob Grue.
In: Electronical Notes in Theoretical Computer Science, Vol. 268, 2010, p. 97-114.Research output: Contribution to journal › Conference article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Programming in biomolecular computation
AU - Hartmann, Lars Røeboe
AU - Jones, Neil
AU - Simonsen, Jakob Grue
N1 - Conference code: 1
PY - 2010
Y1 - 2010
N2 - 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. A prototype model has been implemented (for now in silico on a conventional computer). This work opens new perspectives on just how computation may be specified at the biological level.
AB - 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. A prototype model has been implemented (for now in silico on a conventional computer). This work opens new perspectives on just how computation may be specified at the biological level.
U2 - 10.1016/j.entcs.2010.12.008
DO - 10.1016/j.entcs.2010.12.008
M3 - Conference article
VL - 268
SP - 97
EP - 114
JO - Electronic Notes in Theoretical Computer Science
JF - Electronic Notes in Theoretical Computer Science
SN - 1571-0661
T2 - 1st International Workshop on Interactions between Computer Science and Biology
Y2 - 10 June 2010 through 10 June 2010
ER -
ID: 16411659