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

author: Ross D. King, School of Computer Science, University of Manchester
published: Nov. 22, 2016,   recorded: March 2016,   views: 1898


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


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.

See Also:

Download slides icon Download slides: solomon_king_turing_machine_01.pdf (1.7 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: