Data processing: generic control systems or specific application – Generic control system – apparatus or process
Reexamination Certificate
1998-11-02
2001-07-24
Brusca, John S. (Department: 1631)
Data processing: generic control systems or specific application
Generic control system, apparatus or process
Reexamination Certificate
active
06266569
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computational devices based on Brownian motion of components, and miniaturization and molecular implementation of such devices.
BACKGROUND OF THE INVENTION
Alan Turing conceived the Turing machine in the 1930's as a basic and fundamental abstract computation device, to be used as an instrument for studying the mathematical concept of computation and computability.
A Turing machine
10
, shown in
FIG. 1
, consists of an infinite storage tape
12
divided into tape cells
14
, each cell
14
is capable of storing a single symbol, and a read/write head
16
connecting the tape
12
to a finite control
11
. The machine
10
operates according to a control program, consisting of a finite number of state-transition rules, which are quintuples of the form <S,A,S′,A′,Dir>. Such a rule is interpreted as follows: If the finite control
11
is in state S, and the tape cell
14
of the read/write head
16
contains the symbol A, then change the control state to S′, replace the symbol A by A′, and move the read/write head
16
one cell
14
in direction Dir (Dir is either “left” or “right”). The Turing machine
10
begins its operation with a finite input written on the otherwise blank tape
12
, the read/write head
16
located on the left-most non-blank symbol, and the control in a designated initial state. The computation progresses according to the control program, and terminates when no State-transition rule applies. The content of the non-blank part of tape
12
upon termination is considered the output of the computation.
During the 1930's other mathematical models of computation were developed, including the Lambda Calculus by Alonzo Church and the Primitive Recursive by Kurt Goedel. Following proofs that all these models are equivalent in their computational power, “Church's Thesis” was formulated, stating that all conceivable computational models, past and future, will turn out to be computationally equivalent to each other and in particular to the Turing machine.
While mathematically as powerful as any other computational model, the Turing machine was never implemented as a practical computation device. Turing envisioned his machine being operated by a human being, called “computer” that follows the rules of the control program and uses markers, pencil and an eraser to implement the read/write head
16
.
In the 1940's, von Neumann and colleagues conceived the stored-program electronic computer, on which all modern computers are based.
In the 1970's, Charles Bennett performed a theoretical investigation of physical computation devices based on the Turing machine model. Bennett was motivated by the observation that the standard electronic computers are inherently energy-inefficient since their basic “store to memory” operation irreversibly erases the content of the memory location. Bennett believed that due to thermodynamic considerations computation devices that proceed in a reversible way would be more efficient, and he proposed two conceptual implementations of the Turing machine model that are reversible. One of these conceptual implementations, which he called “Brownian computer” since its operation was based on the Brownian motion of molecules, is a precursor to our invention. In Bennett's Brownian computer, named “hypothetical enzymatic Turing machine”, the tape is a macromolecule consisting of a structural backbone bearing tape symbols and a head marker, and each quintuple of the control program is realized by a specific enzyme that effects the transition by removing and adding a tape symbol, and moving the location of the head marker. [Reference: Charles, H. Bennett, The Thermodynamics of Computation—A Review, International Journal of Theoretical Physics, Vol. 21, No. 12, 1982, pp.905-940].
More recently, interest in molecular computation devices resumed following the work of Adelman [Leonard M. Adelman, Molecular computation of solutions to combinatorial problems, Science, 266:1021-1024, 1994] in 1994, who showed how DNA segments combined with DNA related enzymes can be used to effect computations. Adelman's method was based on creating a test-tube solution consisting of DNA segments and performing “biological steps”, effected by a human or a robot, which include adding certain enzymes to the solution, dividing the solution into several tubes, and/or changing the temperature of the solution. At the end of these steps the result of the computation is extracted via standard biological tools. Following that paper numerous proposals were made on how to implement a DNA-based Turing machine using DNA and related enzymes [Most of this work was reported in the four Proceedings of the Meetings on DNA Based Computers, DIMACS, 1995, 1996, 1997, 1998, and are reviewed in Eric Winfree's Ph.D. Thesis, Algorithmic Self-Assembly of DNA, Caltech, May, 1998]. These proposals fall into two broad classes: one class requires each step of the computation to be effected by a “biological step” as in Adelman's method. The second class [Erik Winfree, Simulations of Computing by Self-Assembly, Preliminary Proceedings of the Fourth International Meeting on DNA Based Computers, DIAMACS, Jun. 15-19, 1998, University of Pennsylvania, edited by Lila Kari, Harvey Rubin and David Harlan Wood, pages 213-239, and references thereto] creates a set of molecules that “self-assemble” in a way that effects a computation. Our invention belongs to that class.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a mechanical working model of simple computation device similar to the Turing Machine. It can be seen that this extrapolates into molecular type implementations.
The technology of the Polymerase Chain Reaction (hereafter referred to as PCR) is similar in concept to this invention, however, whereas PCR is limited to the duplication of DNA, the present invention can be shown to perform useful computational output that can be executed in the form of a program. As any modern day computer can be shown to be reduced to a Turing machine in concept, thus any solvable problem could be solved by the Turing machine.
Thus, the invention can be seen as both a description of a computation device that can be readily operated by a human, or a robot, as envisioned by Alan Turing, as well as a specification for a molecular computation device, which can be driven by Brownian motion, as envisioned by Charles Bennet. The invention constitutes a specification for such a molecular computation device in that it describes the properties of the monomers as well as the enzyme components required by any molecular embodiment of the device.
The applications of such a molecular computation device are as an alternative to the existing computers, and more importantly, the integration of computational steps in sequences of biochemical reactions with therapeutic and/or biochemical purposes.
For convenience of implementation, our invention realizes a variant of the Turing machine in which the read/write head is located between cells, rather than on a cell. In a “move left” transition (Dir=“left”) the head reads the content of the cell to the left, writes on it, and moves one cell to the left. In a “move right” transition the symmetric description applies.
The invention is a Turing machine based on Brownian motion and consisting of three subsystems: an information storage tape, a history tape and an enzyme. The information storage tape is a polymer consisting of alphabet monomers that represent the content of the machine's tape and one state-transition monomer that represents the location of the machine's read/write head as well as its state. The history tape is a polymer of tstate-transition monomers used in the computation, to which are attached alphabet monomers which were displaced (“deleted”) during the computation. The last monomer in the history tape is the state-transition monomer in the information storage tape. The
Karunaratne Kanchana S. G.
Shapiro Ehud
Brusca John S.
Donner Irah H.
Hale and Dorr LLP
Zephyrien International N.V.
LandOfFree
Method and system of computing similar to a turing machine does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system of computing similar to a turing machine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system of computing similar to a turing machine will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2558317