Abstract:

   
   The living cell, viewed from a computer science perspective, contains
   molecular machines that perform efficient and sophisticated string
   manipulation over several alphabets.  While most machines are best
   characterized as finite-state transducers, their basic set of operations is
   certainly computationally complete.  In the talk we review a conceptual
   design of a Turing machine based on this basic set of operations as well as a
   laboratory realization of a two-state, two-symbol finite automaton.  The
   automaton's input, output and software is made of DNA and its hardware
   consists of DNA manipulating enzymes.
   Programming amounts to choosing appropriate software molecules.  Upon mixing
   solutions containing these components, the automaton processes the input
   molecule according to its program, producing an output molecule that encodes
   the automaton's final state.  In our implementation 10^12 automata sharing
   the same software run independently and in parallel on inputs (which could,
   in principle, be distinct) in 120 microliter solution at room temperature at
   a combined rate of 10^9 transitions per second with a transition fidelity
   greater than 99.8%, consuming less than 10^-10 W.
   
   In the talk we will assume familiarity with Turing machines and automata, and
   will not assume familiarity with molecular biology and lab methods.
   
   Joint work with in Yaakov Benenson, Tamar Paz-Elizur, Rivka Adar, Ehud Keinan
   and Zvi Livneh.