[Colloquium] Seminar Announcement: A Computer with Exponentially Increasing Speed: Implementing a Universal Nondeterministic Turing Machine Using DNA

[Ninfa Mayorga]

~Reminder~

Computation Institute Presentation 

Speaker:  Ross King, University of Manchester
Host:  Andrey Rzhetsky
Date:  January 20, 2015
Time: 12:00 PM - 1:00 PM
Location: University of Chicago, Searle 240A, 5735 S. Ellis Ave.

A Computer with Exponentially Increasing Speed: Implementing a Universal Nondeterministic Turing Machine Using DNA  

Abstract: 
All existing computers have a fixed constant speed.  I present a new computational paradigm in which the computer’s speed increases exponential as it solves a problem.  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.  The NP time complexity class is the most significant class of problems in computer science, and a tractable/efficient (polynomial) way to solve them would be of great economic and social importance.  Nondeterministic UTMs (NUTMs) can, by definition, solve nondeterministic polynomial (NP) complete problems in polynomial time.  However, NUTMs have previously been considered to be a purely mathematical concept, and physically impossible to construct.  Here I describe a NUTM that can be physically engineered using DNA and standard molecular biology techniques.  The NUTM uses DNA’s ability to replicate to encode 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 works through ‘wet’ implementation of NUTM rules.  The current design has limitations, e.g. limited error-correction.  However, it opens up the prospect of engineering NUTM based computer, which for certain classes of problem, can outperform all standard computers. 

 
Information: Lunch will be provided



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150116/51958987/attachment.htm