Abstract
How can molecules compute? In his early studies of reversible computation, Bennett imagined an enzymatic Turing Machine which modified a hetero-polymer (such as DNA) to perform computation with asymptotically low energy expenditures. Adleman�s recent experimental demonstration of a DNA computation, using an entirely different approach, has led to a wealth of ideas for how to build DNA-based computers in the laboratory, whose energy efficiency, information density, and parallelism may have potential to surpass conventional electronic computers for some purposes. In this thesis, I examine one mechanism used in all designs for DNA-based computer � the self-assembly of DNA by hybridization and formation of the double helix � and show that this mechanism alone in theory can perform universal computation. To do so, I borrow an important result in the mathematical theory of tiling: Wang showed how jigsaw-shaped tiles can be designed to simulate the operation of any Turing Machine. I propose constructing molecular Wang tiles using the branched DNA constructions of Seeman, thereby producing self-assembled and algorithmically patterned two-dimensional lattices of DNA. Simulations of plausible self-assembly kinetics suggest that low error rates can be obtained near the melting temperature of the lattice; under these conditions, self-assembly is performing reversible computation with asymptotically low energy expenditures. Thus encouraged, I have begun an experimental investigation of algorithmic self-assembly. A competition experiment suggests that an individual logical step can proceed correctly by self-assembly, while a companion experiment demonstrates that unpatterned two dimensional lattices of DNA will self-assemble and can be visualized. We have reason to hope, therefore, that this experimental system will prove fruitful for investigating issues in the physics of computation by self-assembly. It may also lead to interesting new materials.
|
