[Solomonov Seminar] 273. Solomonov seminar
marko.grobelnik at ijs.si
Thu Mar 17 13:24:13 CET 2016
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/
Ross King, School of Computer Science, University of Manchester
Computing Exponentially Faster -
Implementing a Nondeterministic Universal Turing Machine using DNA
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.
More information about the Solomonov-seminar