[Previous] [Up] [Next]
Go backward to Example String Machines  
Go up to Progress Report on Work to Date  
Go forward to Arbitrary Nondeterministic Turing Machines  

Discussion of Universal Machine  

The machine outlined above, assuming it works in simulation, suffices to establish the universality of DNA replication in the presence of oligonucleotide mixtures. It is intended to demonstrate the generality of computational oligo systems, and not as a realistic way to do any real computation, because of a number of inefficiencies:

  1. Many PCR cycles (which themselves take many minutes) will be required on average to execute each atomic transition of the Turing machine, due to the random walk along the rewrite-rule transition path.
  2. Numerous backwards and forwards Turing-machine transitions will be required for every step of net forward progress, due to the fact that old history particles will take a while to diffuse out of the way.
  3. Minsky's machine is extraordinarily inefficient, requiring thousands of steps to interpret the simplest of programs.
  4. Turing machines in general are somewhat inefficient due to their serial nature.
However, now that we know that universal computation in DNA is indeed possible, we can go on to consider ways of improving it. We are in the process of looking for simpler universal string-rewriting systems, perhaps not involving Turing machines at all, which would utilize the basic operation of mutagenesis to do computation in a more direct way. Systems based on cellular automata, for example, might process information in many parts of a string simultanously, adding the digits of large numbers in parallel, and so forth. We are also considering schemes for random access of information. (Those paricular directions, however, are still rather speculative.)

- Michael P. Frank, September 12, 1995. Formatted using HyperLaTeX-1.3.

[Previous] [Up] [Next]