Computing exponentially faster: implementing a non-deterministic universal Turing machine using DNA
Journal: Journal of the Royal Society Interface
Publication Date: 01 March, 2017
New super-fast form of computer that grows as it computes
Researchers at The University of Manchester have for the first time demonstrated the feasibility of building a nondeterministic universal Turing machine (NUTM). The construction of NUTMs was previously regarded as impossible. Engineering NUTMs is important because, for the most important computational problems, NUTMs are exponentially faster than both electronic computers (universal Turing machines – UTMS), and quantum computers (QUTMs). The Manchester design exploits DNA’s ability to replicate, and as all the computation is local (simple edits to strings) there is no need for communication between processors, and no need to order operations. The DNA string edits are implemented using molecular biology, and have been proved to work. In an NUTM the resource limitation is space, which contrasts with 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 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.
- Exponential Increase: A qualitative difference: if K is a constant and X a variable, an exponential function has the form KX rather than XK which is a polynomial; so as x increases an exponential function always becomes larger than a polynomial, no matter what K is.
- Universal Turing Machine: The celebrated Manchester Computer Scientist Alan Turing’s greatest achievement was inventing the concept of a universal Turing machine – a computer that can be programmed to compute anything any other computer can compute. All modern electronic computers are Universal Turing Machines.
- DNA Computing: The use of DNA molecules to implement computing.
- Quantum Computing: The use of quantum mechanical effects to implement computing. For a limited set of problems quantum computers are exponentially faster than electronic computers.