Deprecated: Implicit conversion from float 209.6 to int loses precision in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 534
Deprecated: Implicit conversion from float 209.6 to int loses precision in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 534
Deprecated: Implicit conversion from float 209.6 to int loses precision in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 534
Deprecated: Implicit conversion from float 209.6 to int loses precision in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 534
Deprecated: Implicit conversion from float 209.6 to int loses precision in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 534
Deprecated: Implicit conversion from float 209.6 to int loses precision in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 534
Deprecated: Implicit conversion from float 209.6 to int loses precision in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 534
Deprecated: Implicit conversion from float 243.2 to int loses precision in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 534
Warning: imagejpeg(C:\Inetpub\vhosts\kidney.de\httpdocs\phplern\28250099
.jpg): Failed to open stream: No such file or directory in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 117 J+R+Soc+Interface
2017 ; 14
(128
): ä Nephropedia Template TP
gab.com Text
Twit Text FOAVip
Twit Text #
English Wikipedia
Computing exponentially faster: implementing a non-deterministic universal Turing
machine using DNA
#MMPMID28250099
Currin A
; Korovin K
; Ababi M
; Roper K
; Kell DB
; Day PJ
; King RD
J R Soc Interface
2017[Mar]; 14
(128
): ä PMID28250099
show ga
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 classical UTMs. For the most important
class of problem in computer science, non-deterministic polynomial complete
problems, non-deterministic UTMs (NUTMs) are theoretically exponentially faster
than both classical UTMs and quantum mechanical UTMs (QUTMs). However, no attempt
has previously been made to build an NUTM, and their construction has been
regarded as impossible. Here, we demonstrate the first physical design of an
NUTM. This design is based on Thue string rewriting systems, and thereby avoids
the limitations of most previous DNA computing schemes: all the computation is
local (simple edits to strings) so there is no need for communication, and there
is no need to order operations. The design exploits DNA's ability to replicate to
execute an exponential number of computational paths in P time. Each Thue
rewriting step is embodied in a DNA edit implemented using a novel combination of
polymerase chain reactions and site-directed mutagenesis. We demonstrate that the
design works using both computational modelling and in vitro molecular biology
experimentation: the design is thermodynamically favourable, microprogramming can
be used to encode arbitrary Thue rules, all classes of Thue rule can be
implemented, and non-deterministic rule implementation. In an NUTM, the resource
limitation is space, which contrasts with classical UTMs and QUTMs where it is
time. This fundamental difference enables an NUTM to trade space for time, which
is significant for both theoretical computer science and physics. It is also of
practical importance, for to quote Richard Feynman 'there's plenty of room at the
bottom'. This means that a desktop DNA NUTM could potentially utilize more
processors than all the electronic computers in the world combined, and thereby
outperform the world's current fastest supercomputer, while consuming a tiny
fraction of its energy.
free
free
free
