A Caltech Library Service

A DNA and restriction enzyme implementation of Turing Machines

Rothemund, Paul W. K. (1996) A DNA and restriction enzyme implementation of Turing Machines. In: DNA based computers. DIMACS series in discrete mathematics and theoretical computer science. No.27. American Mathematical Society , Providence, RI, pp. 75-120. ISBN 0821805185.

PDF - Published Version
See Usage Policy.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Bacteria employ restriction enzymes to cut or restrict DNA at or near specific words in a unique way. Many restriction enzymes cut the two strands of double-stranded DNA at different positions leaving overhangs of single-stranded DNA. Two pieces of DNA may be rejoined or ligated if their terminal overhangs are complementary. Using these operations fragments of DNA, or oligonucleotides, may be inserted and deleted from a circular piece of plasmid DNA. We propose an encoding for the transition table of a Turing machine in DNA oligonucleotides and a corresponding series of restrictions and ligations of those oligonucleotides that, when performed on circular DNA encoding an instantaneous description of a Turing machine, simulate the operation of the Turing machine encoded in those oligonucleotides. DNA based Turing machines have been proposed by Charles Bennett but they invoke imaginary enzymes to perform the state-symbol transitions. Our approach differs in that every operation can be performed using commercially available restriction enzymes and ligases.

Item Type:Book Section
Rothemund, Paul W. K.0000-0002-1653-3202
Additional Information:© 1996 American Mathematical Society. I would like to thank Max and Judith Rothemund for the generous grant that made my studies at the California Institute of Technology possible. Yaser Abu-Mostafa (dept of electrical engineering California of Technology) provided great enthusiasm, encouragement, and input for what was an unusual project. Erik Winfree (CNS Caltech) has kept me working and without him, I never would have attended DIMACS. I would like to thank Kai Zinn (dept of Biology California Institute of Technology) for letting me use DNA Strider early on; Greg Fu (dept of chemistry Massachusetts Institute of Technology) and Randy Lee (dept of Chemistry University of Houston) for encouraging my interest in chemistry; Sam Roweis and Len Adleman for their stimulating discussion; Nadrian Seeman for discussion on error correction; and Aditi Dhagat, Barun Chandra, and Amitabh Shah for introducing me to CS. Finally, I would like to dedicate this paper to the late J .L.A. van de Snepscheut, (Dept of Computer Science California Institute of Technology) for introducing me to the idea of a DNA Turing machine [34]. He would have been excited and pleased by the development of DNA computation.
Subject Keywords:Turing machines; Universal Turing machines; recombinant DNA; nonpalindromic endonucleases; class IIS nucleases; biological computation; molecular computation; chemical computation, DNA computation
Series Name:DIMACS series in discrete mathematics and theoretical computer science
Issue or Number:27
Record Number:CaltechAUTHORS:20111024-134806267
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27384
Deposited By: Tony Diaz
Deposited On:26 Oct 2011 16:39
Last Modified:03 Oct 2019 03:23

Repository Staff Only: item control page