Ph.D Thesis | |

Ph.D Student | Ratner Tamar |
---|---|

Subject | Advanced Bio-Molecular Computing Devices and Chemical Encoding and Processing of Alphanumeric Information |

Department | Department of Chemistry |

Supervisor | PROFESSOR EMERITUS Ehud Keinan |

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.