[Solomonov Seminar] 273. Solomonov seminar

[Marko Grobelnik]

V ponedeljek 21. marca 2016 bo ob 15:00 v MPS predavalnici IJS 273. 
Solomonov seminar. MPS predavalnica je v drugem nadstropju stavbe 
Mednarodne podiplomske sole na Jamovi 39. Posnetki preteklih seminarjev 
so na http://videolectures.net/solomon/

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Lecturer:
Ross King, School of Computer Science, University of Manchester

Title:
Computing Exponentially Faster -
Implementing a Nondeterministic Universal Turing Machine using DNA

Abstract:
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 an efficient (i.e. 
polynomial P) way to solve such problems 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.  Thue string 
rewriting systems are computationally equivalent to UTMs, and are 
naturally nondeterministic.  Here we describe the physical design for a 
NUTM that implements a universal Thue system using DNA computing.  The 
NUTM uses a novel combination of polymerase chain reaction (PCR), and 
site-directed mutagenesis, to execute an exponential number of 
computational paths in P time – each computational step being embodied 
in a DNA edit.  We demonstrate that this physical design works using 
both computational modelling and molecular biology experimentation.  The 
current design has limitations, for example restricted error-correction. 
  However, it opens up the prospect of engineering NUTM based computers 
able to outperform all standard computers on important practical problems.