A Computer that Grows: Implementing a Universal Nondeterministic Turing Machine Using DNA
- Speaker: Professor Ross King (University of Manchester)
- Host: Robert Stevens
- 5th November 2014 at 14:00 in Kilburn L.T. 1.4
I present a new computational paradigm in which the computer grows at an exponential rate to solve problems. All previous computers have had a fixed constant size, which fundamentally limits how fast they can solve problems. The theory of computer science is based around Universal Turing Machines (UTMs). Every UTM can compute every computable function, and every modern digital computer is in essence a UTM. Nondeterministic UTMs (NUTMs) are a type of UTM that can (by definition) solve nondeterministic polynomial (NP) complete problems in polynomial (P) time. The NP time complexity class is the most significant class of problems in computer science, and a tractable/efficient (P) way to solve them would be of great economic and social importance. However, NUTMs have previously been considered to be a purely mathematical concept, and as such physically impossible to construct. I will describe a NUTM that can be physically engineered using DNA and standard molecular biology techniques. It uses DNA?s ability to replicate to program an exponentially growing process that explores all possible computational paths, each represented by a different DNA sequence. Site-directed mutagenesis is used to implement a Thue string rewriting system (computationally equivalent to a UTM), and polymerase chain reactions (PCRs) to implement the exponentially replicating process. I present evidence that the design will work through modelling, and evidence that the NUTM rules can be physical implemented. The current design has many limitations, e.g. limited error-correction. However, it opens up the prospect of engineering NUTM based computers that grow to outperform all existing computers.