DNA molecule provides a computing machine with both data and fuel

A molecular finite automaton that uses input as fuel. (A) Encoding of a, b, and terminator (sense strands) and the <state, symbol> interpretation of exposed 4-nt sticky ends, the leftmost representing the current symbol and the state S1, similarly the rightmost for S0. (B) Hardware: The FokI restriction enzyme, which recognizes the sequence GGATG and cleaves 9 and 13 nt apart on the 5′ → 3′ and 3′ → 5′ strands, respectively. (C) Software: Each DNA molecule realizes a different transition rule by detecting a current state and symbol and determining a next state. It consists of a <state, symbol> detector (yellow), a FokI recognition site (blue), and a spacer (gray) of variable length that determines the FokI cleavage site inside the next symbol, which in turn defines the next state. Empty spacers effect S1 to S0 transition, 1-bp spacers maintain the current state, and 2-bp spacers transfer S0 to S1. (D) Input: The exposed sticky end at the 5′ terminus of the DNA molecule encodes the initial state and first symbol. Each symbol is encoded with 5 bp separated by 3-bp spacers. (E) Suggested mechanism of operation of the automaton. The computation proceeds via a cascade of transition cycles, each cleaving and scattering one input symbol, exemplified with the input molecule bab in the initial state S0 and the transition S0 →b S1. Both hardware and software molecules are recycled.