|Ph.D Thesis||Department of Chemistry|
|Supervisor:||Prof. Keinan Ehud|
|Full Thesis text|
Two novel types of advanced bio-molecular computing (BMC) devices were developed and implemented. The first, a DNA-based transducer, can perform computational processes, encode computation outcomes and present the output as a biological function. The significance of this new device is its ability to recognize context-free languages. The second device is an arrow computing machine (ACM), which is an analog of a Turing machine. In addition to all of the transducer's abilities, it can use the process-produced data in the next stages of computation. These abilities provide the highest possible computation capabilities: recognizing unrestricted grammars.
A transducer is a general computation device, ubiquitous in both the living and inanimate worlds, which describes any functional system that can process information and transform it into another type of information. Moreover, the output of one computation may be used as an input for a consecutive computation. Such iterative application enables recursion and may present computational power equivalent to a Universal Turing machine.
We presented a DNA-based molecular transducer that can encode the computation outcome in the form of genetic information and produce a biological phenotypic output. We demonstrated the applicability of this by performing the task of a long division by 3 where the input was a binary number represented by a specific DNA sequence on a plasmid. The computation process employed several DNA enzymes as hardware and a set of several transition molecules in the form of short dsDNA molecules as software. The quotient of the division was represented by the newly written binary number whereas the remainder, being 0, 1 or 2, was represented by a specific E. coli resistance to one of three different antibiotics. We confirmed the iterative power of this transducer by operating it recursively on its own output.
An ACM is a general computation device, based on the theoretical Turing machine, which is known for its universal computing power. Thus far, several BMC machines that feature high computational-power have been designed and implemented. However, these devices were intended to solve only limited types of problems.
Here we present the principles and implementation of diverse sets of legitimate transition rules for different ACMs. Therefore, this system is adjustable for solving different and diverse problem types. We designed and realized an arrow computing machine, capable of recognizing a polynomial sequence of the form of L3n. The applicability of this device was demonstrated by performing computations with non-polynomial and polynomial inputs.