A team of researchers from the University of Manchester, led by professor Ross D King, have demonstrated the first physical design of a NUTM (Non-deterministic Universal Turing Machine). Modern computers are based upon classical UTMs and Quantum mechanical UTMs (QUTMs), as the construction of NUTMs has been deemed impossible. However for "the most important class of problem in computer science… NUTMs are theoretically exponentially faster," explain the researchers in a paper published last week.
In the computer designed by the researchers the 'processors' are made of DNA rather than silicon chips. Even though the DNA processors might lack computational power compared to a traditional CPU thay have some key advantages. Firstly the DNA processors can self-replicate, growing to solve a problem faster and more accurately. Secondly that processing capacity allows many parallel paths to be explored for solutions. And thirdly, the DNA computer would use a tiny fraction of the energy of a classical computer or quantum computer.
DNA's self replication ability is of particular utility in a computer model. "Imagine a computer is searching a maze and comes to a choice point, one path leading left, the other right. Electronic computers need to choose which path to follow first," pondered Prof King, from Manchester's School of Computer Science. Quantum computers could follow both paths at that maze split point "but only if the maze has certain symmetries, which greatly limits their use," explained King. Meanwhile the DNA NUTM can replicate itself and follow both parts at the same time, and so on "thus finding the answer faster," asserted the professor.
Giving some background to the scalability of the DNA NUTM, the research paper states; "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".
Prof King's team reports that their DNA NUTM has been demonstrated to work using computational modelling and in vitro molecular biology experimentation. It is admitted that the current design has limitations in error correction but opens up a new computing model "able to outperform all standard computers on important practical problems".
The University of Manchester School of Computer Science research paper was published by the Journal of The Royal Society Interface.