Programming in biomolecular computation

Publikation: Bidrag til tidsskriftKonferenceartikelForskningfagfællebedømt

Dokumenter

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.

OriginalsprogEngelsk
TidsskriftElectronical Notes in Theoretical Computer Science
Vol/bind268
Sider (fra-til)97-114
Antal sider18
ISSN1571-0661
DOI
StatusUdgivet - 2010
Begivenhed1st International Workshop on Interactions between Computer Science and Biology - Amsterdam, Holland
Varighed: 10 jun. 201010 jun. 2010
Konferencens nummer: 1

Konference

Konference1st International Workshop on Interactions between Computer Science and Biology
Nummer1
LandHolland
ByAmsterdam
Periode10/06/201010/06/2010

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 16411659