Molecular Turing Machines
The goal of building a molecular scale UTM has been pursued for over thirty years. The most common molecule suggested for a molecular UTM is DNA. In DNA computing data are encoded in sequences of DNA bases, and molecular biology methods used to execute computations. The main technological motivation for building DNA UTMs has been their potential advantages in speed, energy efficiency and information storage: the number of operations for a desktop DNA computer could plausibly be ~10^20 s (~10^3 times faster than the fastest current supercomputer); it could execute ~2 ?? 10^19 operations per Joule (~10^10 more than current computers); and utilise an information density of ~1 bit per nm3 (~10^12 more dense than current memory).
The foundational work on DNA computing was that of Leonard Adleman. He demonstrated the solution of a seven-point Hamiltonian path by generating a set of random DNA sequences (possible solutions), and selecting a solution from the set. The significance of the choice of the Hamilton path problem is that it is NP-complete. The work therefore opened up the prospect of applying the advantages of molecular computing to NP problems.
The proposal is to investigate novel ways of implementing Turing machines using DNA.