A Mechanical Turing Machine: Blueprint for a Biomolecular Computer

 

Ehud Shapiro

Department of Applied Math and Computer Science

Weizmann Institute of Science

Rehovot 76100 Israel

Udi@wisdom.weizmann.ac.il

 

We describe a working mechanical device that embodies the theoretical computing machine of Alan Turing, and as such is a universal programmable computer. The device operates on three-dimensional building blocks by applying mechanical analogs of polymer elongation, cleavage and ligation, movement along a polymer, and control by allosteric conformational changes. Logically, the device is not more complicated than biomolecular machines of the living cell and all its operations are part of the standard repertoire of these machines, hence a biomolecular embodiment of the device is not infeasible. If implemented, such a biomolecular device may operate in vivo, interacting with its biochemical environment in a program-controlled manner. In particular, it may "compute" synthetic biopolymers and release them into its environment in response to input from the environment, a capability that may have broad pharmaceutical and biological applications.

 

 

 

In 1936 Alan Turing proposed a “pencil-and-paper” computing device, now called the Turing machine, as a formalization of the notion of a procedure. Although the Turing machine is prevalent in theoretical computer science and is theoretically a universal computer, it was never realized as an actual computing device. All present day computers are based on a different architecture, the "stored program" electronic computer architecture devised by von Neumann and colleagues in the late 1940's. In 1994 Adleman showed how to compute using DNA molecules and standard molecular biology laboratory techniques. Adleman's method involves encoding combinatorial search problems with DNA sequences and using in vitro selection techniques to synthesize and isolate DNA sequences that encode solutions to these problems. Subsequent work, further developed and expanded this research direction.

Adelman concluded his seminal paper3 saying: "In the future, research in molecular biology may provide improved techniques for manipulating macromolecules. Research in chemistry may allow for the development of synthetic designer enzymes. One can imagine the eventual emergence of a general purpose computer consisting of nothing more than a single macromolecule conjugated to a ribosomelike collection of enzymes that act on it." Here we attempt to advance this vision by proposing a detailed logical design for such a computer, with the ultimate goal of constructing a general-purpose programmable computer that can operate in vivo and interact with its biochemical environment. As the tools of molecular biology and chemistry are insufficient at present to realize this design with biomolecules, we realized it in a working mechanical implementation. This mechanical device serves as a proof-of-concept of the logical design as well as a high-level operational specification for a biomolecular implementation.

The mechanical computer employs a chain of basic building blocks (Fig. 1A), referred to as alphabet monomers, to represents the Turing machine's tape, and uses another set of building blocks (Fig. 1B), referred to as transition molecules, to encode the machine's transition rules. A transition molecule loaded with an alphabet monomer specifies a computational step of the computer similarly to the way an aminoacyl-tRNA specifies a translation step of the ribosome. The set of loaded transition molecules constitute the computer program (Fig. 1C).

The computer operates on two chains of building blocks simultaneously (Fig. 1D). One chain, referred to as the tape polymer, represents the Turing machine's tape and is edited by the computer similarly to the way a Turing machine modifies its tape. The other chain, referred to as the trace polymer, is a byproduct of the computation constructed incrementally from displaced transition molecules and displaced alphabet monomers, and has no analog in the theoretical Turing machine. A transition molecule, referred to as the active transition molecule, joins the two polymers. The active transition molecule is embedded in the tape polymer and represents the location of the Turing machine's read/write head as well as the machine's internal state. At the same time the active transition molecule is the terminal molecule of the trace polymer, representing the most recent transition of the computation. (Note that in this design the read/write head is located between adjacent tape cells, not on a specific cell, unlike a standard Turing machine1; this change does not affect the computational capabilities of the machine.)

The computer (Fig. 2A) is made of two subunits, referred to as small and large, each with a tunnel called the small tunnel and the large tunnel, respectively. The small tunnel provides incoming loaded transition molecules with access to the active transition molecule and to its adjacent alphabet monomer. Access is controlled by gating mechanisms (Fig. 2B) that block transition molecules that are ill-formed or do not match the current state and current tape symbol. These mechanical analogs of allosteric conformational changes open the channel only when a valid incoming transition molecule approaches. The large tunnel holds the active transition molecule and the tail of the trace polymer being constructed.

The computer operates in cycles, processing one transition molecule per cycle. In each cycle an incoming loaded transition molecule that matches the current state and its adjacent alphabet monomer becomes the new active transition molecule and its accompanying alphabet monomer is incorporated into the tape polymer. This is achieved by displacing the currently active transition molecule and the matched alphabet monomer, effectively editing the tape polymer, and elongating the trace polymer by the displaced molecules (Fig. 1D). Specifically, when processing a left transition molecule the computer moves left to accommodate the molecule, if necessary, and displaces the currently active transition molecule and the alphabet monomer to its left by the new molecule. The computer processes a right transition molecule similarly by moving right and displacing the alphabet monomer to the right of the active transition molecule.

The mechanical computer is similar to the ribosome in several respects. Both operate on two polymers simultaneously, and their basic cycle consists of processing an incoming molecule that matches the currently held molecules on the first polymer, elongating the second polymer, and moving sideways. Like the ribosome in the living cell, the computer requires supporting devices similar in function to aminoacyl tRNA synthetases to load bare transition molecules with correct alphabet monomers, and a device similar in function to proteases to decompose the trace polymer and make its components available for reuse. However, unlike the ribosome, which only "reads" the messenger-RNA in one direction, the computer edits the tape polymer and may move in either direction.

The trace polymer created during the computation represents past state changes and head movements, as well as the symbols that were "erased" from the tape during each transition, and as such has several important advantages. First, the trace polymer renders the computer reversible. Bennett claims that, due to thermodynamic considerations, electronic computers are inherently energy-inefficient since their basic “store to memory” operation irreversibly erases the content of the memory location. To remedy this inefficiency Bennett proposed a “hypothetical enzymatic Turing machine”. This hypothetical device is similar to our computer in representing the Turing machine's tape as a polymer of basic building blocks and in being dependant on the "Brownian motion" of its building blocks to effect a computation. Since the trace polymer embodies a complete record of the computation, a molecular implementation of the computer will be subject to the speed/energy consumption tradeoff ofreversible devices. Second, computation traces in general, and the trace polymer in particular, enable many "software" program analysis and debugging tools, which are critically needed for large scale applications. Third, the trace polymer enables "hardware" error detection and correction. One expects that any biomolecular implementation of the computer may exhibit non-negligible error rate. Such errors can be detected, and possibly also corrected, by cascading several computers along the same trace polymer, each detecting, and possibly also correcting, errors produced by its predecessor.

Perhaps the most important property of the mechanical computer is that it is reactive: it can have an ongoing, program-controlled, interaction with its environment. This capability is a result of the biologically-inspired architecture of the computer rather than inherited from the theoretical Turing machine, which was conceived as a "batch" computing device that receives its input at the beginning of the computation and produces an output if and when the computation ends. The ribosome, for example, suspends the construction of a polypeptide chain when a required amino acid is unavailable. Similarly, our computer can be "programmed" to suspend until a specific molecule is available. The availability of such a control molecule can be tied to other relevant environmental conditions, thus triggering a computation only when these conditions prevail.

The Turing machine is a non-deterministic computing device1 in that it can make choices during a computation, and so is our computer. Not only can it have left and right transitions applicable simultaneously, but also it can also have two or more left (or right) transitions with the same recognition site but with different target states or new symbols to be written. In a biomolecular implementation, this capability can be used to have the environment affect the course of a computation, based on the relative concentrations of molecules that enable one computational step compared to molecules enabling a different computational step. Using these two capabilities, the computer can be programmed so that both the timing and the course of a computation are affected and controlled by the biochemical environment.

We endow the computer with an output device as follows. A simple extension to the Turing machine design is an instruction that erases the tape segment to the right of the read/write head. This instruction does not change the computing power of the machine, and for the theoretical model does not seem useful either. However, we interpret this instruction in our context to mean: "cleave the tape polymer to the right of the active transition molecule and release this tape polymer segment to the environment". With this instruction, the computer can create and release any effectively computable polymer of alphabet monomers, in any number of copies, in the course of a computation. A cleaved tape polymer segment released by one computer can serve as the initial tape for the computation of another computer, or it can be ligated under certain conditions to the tape of another computer, thus enabling parallel processing, communication and synchronization among multiply operating computers.

The computer design allows it to respond to the availability and to the relative concentrations of specific molecules in its environment, and to construct program-defined polymers and release them into the environment. Hence, if implemented using biomolecules, the computer can be part of biochemical pathways. In particular, given a biomolecular implementation of the computer that uses ribonucleic acids as alphabet monomers, one can envision how cleaved tape polymer segments can function as messenger-RNA, effecting program-directed synthesis of proteins in response to specific biochemical conditions within the cell. Such an implementation can provide a family of computing devices with broad biological and pharmaceutical applications.

 

 

 

 

Figure 1: Transition molecules and operation of a parenthesis checker program

A parenthesis checker verifies that a string consisting of left and right parentheses is well formed. For example, "()", "(())", and "(())()" are well-formed whereas "(()", " )(", and "()())", are not. It operates by marking pairs of matching parentheses inside-out and left-to-right, until all parentheses have been marked in which case it accepts the string. Otherwise the string is rejected. The figure illustrates the program and its operation.

  1. Alphabet molecules are considered one unit wide. They have a side-group representing the symbol, and left and right links for forming the tape polymer.

  2. Transition molecules are two units wide and two units high. The molecule shown implements the left transition abbreviated (,S1 ® S0,# and read: If the control state is S1 and the head reads symbol "(" to the left, then change state to S0, write symbol #, and move left one cell. The molecule has a recognition site for the symbol "(" and the state S1 on its lower side, a side-group representing the new state S0 above and a missing upper-right quadrant that accommodates the new symbol to be written, #, as well as left and right links enabling it to be part of the tape polymer.

  3. These eight transition molecules shown schematically constitute the parenthesis checker program. The top row includes right transition molecules, which are read similarly to a left transition molecule (see B) with "right" replacing "left" through the description. The bottom row includes left transition molecules. The last transition enters into state S3 and accepts the string. Blank recognizes the end of the non-blank part of the tape, namely the case where the transition molecule is at the end of the tape polymer.

  4. Example transition that occurs during a computation on the string "(()()())". The configuration consists of a tape polymer (1) and a trace polymer (2). An incoming right transition molecule S0,) ® #,S1 (3) loaded with an alphabet molecule # (4) that matches the current state of the current active molecule (5) and the alphabet symbol to its right (6). The updated configuration shows the displaced transition molecule (5) and displaced alphabet molecule (6) that are now part of the elongated trace polymer (2), with the incoming transition molecule (3), now the active transition molecule, and the incoming alphabet molecule (4), both form part of updated the tape polymer (1).

 

 

 

 

 

 

 

 

 

 

Figure 2: Mechanical Computer

  1. The computer is 18 x 29 x 9cm. The small tunnel (1) is part of the small subunit and is two units wide. The large tunnel (2) is part of the large subunit and is three units wide, so that it can accommodate the displaced transition molecule and the new active transition molecules. The small and large subunits can move one unit sideways relative to each other. Such movement is necessary following a change of direction of the computation. An incoming transition molecule (3) is approaching the active transition molecule (4) and the alphabet molecule to its right (5). The tape polymer can move left or right one unit, aligning the active transition molecule to the left or to the right side of the large tunnel. Such movement is necessary to accommodate consecutive transitions in the same direction.

  2. Five mechanisms in the small tunnel prevent erroneous transitions from occuring. All mechanisms are based on a spring-loaded bellcrank/cam (a) which is connected to a linkage (b) which in its free state blocks passage of the approaching transition molecule. Each bellcrank/cam checks for a certain condition and if the condition is met, is rotated. The connected linkage then moves out of the way of the approaching transition molecule, essentially effecting a conformational change in the tunnel. Two mechaisms (1,2) detect that the (left or right) transition molecule is loaded with an alphabet molecule. Two mechanisms (3,4) detect that a Blank recognition site matches the (left or right) end of the tape polymer and one mechanism (5) detects that the recognition site of the incoming transition molecule matches the state side group ofthe active transition molecule and the alphabet symbol to its right.

 

The computer was designed utilizing SolidWorks Corporation's SolidWorks 98 Software, and was manufactured on a 3D Systems Inc. SLA-5000 Stereolithography Apparatus by Scicon Technologies of Valencia, CA. Material is a Dupont 8110 epoxy/polypropylene/polyethylene blend. The size of the mechanical computer and its components do not make it susceptible to Brownian motion. Hence assembly of transition molecules, pushing transition molecules down the small tunnel, and moving the small and large subunits relative to each other and relative to the tape polymer, all need to be done manually.

 

 

 

 

 

 

 

 

 

Acknowledgements

Mechanical design by K. Karunaratne from Korteks and M. Schilling from Schilling 3D Design. I thank Avi Karni and Doron Lancet for helpful comments and discussions.