Solving Problems Exponentially Faster: Implementing a Nondeterministic Universal Turing Machine Using DNA

Talk by Ross D. King

Location: APB 1004
Start: 28. September 2015 at 1:30 pm
End: 28. September 2015 at 3:00 pm
Research group: Computational Logic
Research group: Knowledge-Based Systems
Event series: KBS Seminar
iCal

The theory of computer science is based around Universal Turing Machines (UTMs), abstract machines able to execute all possible algorithms. Modern digital computers are physical embodiments of UTMs. The nondeterministic polynomial (NP) time complexity class of problems is the most significant in computer science, and a tractable/efficient (i.e. polynomial P) way to solve them would be of great economic and social importance. By definition nondeterministic UTMs (NUTMs) solve NP complete problems in P time. However, NUTMs have previously been believed to be physically impossible to construct. I will describe the physical design of a NUTM based on implementing a Thue string rewriting system in DNA. It uses polymerase chain reactions (PCRs), and site-directed mutagenesis, to execute an exponential number of computational paths in P time - each path represented by a different sequence of DNA. I will show evidence that this design works: computational modelling, and wet molecular biology implementation of Thue rules. The current design has many limitations, e.g. restricted error-correction. However, it opens up the prospect of engineering NUTM based computers able to outperform all standard computers on significant practical problems.

Ross D. King is Professor of Machine Intelligence at the University of Manchester, UK. His main research interests are in the interface between computer science and biology/chemistry. The research achievement he is most proud of is originating the idea of a "Robot Scientist": using laboratory robotics to physically implement a closed-loop scientific discovery system. His Robot Scientist "Adam" was the first machine to hypothesise and experimentally confirm scientific knowledge. His new robot "Eve" is searching for drugs against neglected tropical diseases. His work on this subject has been published in the top scientific journals, Science and Nature, and has received wide publicity. He is also very interested in NP problems, computational economics, and computational aesthetics.