title: Demonstration of a universal surface DNA computer.
abstract: A fundamental concept in computer science is that of the universal Turing machine, which is an abstract definition of a general purpose computer. A general purpose (universal) computer is defined as one which can compute anything that is computable. It has been shown that any computer which is able to simulate Boolean logic circuits of any complexity is such a general purpose computer. The field of DNA computing was founded in 1994 by Adleman's solution of a 7-bit instance of the Hamiltonian path problem. This work, as well as most of the subsequent experimental and theoretical investigations in the area, focused primarily upon the solution of NP-complete problems, which are a subset of the larger universal class of problems. In the present work a surface DNA computer capable of simulating Boolean logic circuits is demonstrated. This was done by constructing NOR and OR gates and combining them into a simple logic circuit. The NOR gate is one of the universal gates in Boolean logic, meaning that any other logic gate can be built from it alone. The circuit was solved using DNA-based operations, demonstrating the universal nature of this surface DNA computing model.
authors.affiliation: Department of Chemistry, University of Wisconsin-Madison, 1101 University Avenue, Madison, WI 53706, USA.
authors.forename: Xingping
authors.initials: X
authors.lastname: Su
authors.forename: Lloyd M
authors.initials: LM
authors.lastname: Smith
mesh_terms: D039301:Computers, Molecular; D004247:DNA / Q000096:biosynthesis / Q000235:genetics / Q000378:metabolism*; D004259:DNA-Directed DNA Polymerase / Q000378:metabolism; D008025:Ligases / Q000378:metabolism; D009691:Nucleic Acid Denaturation; D009841:Oligonucleotides; D016376:Oligonucleotides, Antisense / Q000096:biosynthesis / Q000235:genetics / Q000378:metabolism; D010766:Phosphorylation; D015203:Reproducibility of Results
chemical_list: D009841:Oligonucleotides; D016376:Oligonucleotides, Antisense; C477371:locked nucleic acid; D004247:DNA; D004259:DNA-Directed DNA Polymerase; D008025:Ligases