Recent years have seen the advent of DNA-based computation, as well as the development of a DNA nanotechnology that produces objects, robust devices and periodic arrays. We propose to combine these areas, by using a robust 2-state DNA device and DNA array assembly techniques to prototype a programmable finite state machine capable of performing simple computations. The goal is to produce a system that is programmable, produces an output and is reusable. We exploit connections between Wang tiles, finite state machines (transducers) and com- putable functions. The main idea uses DNA TX molecules to represent transducer transitions and a sequence of 2-state DNA devices to program the input. Once the input is programmed, the computation of the transducer is obtained solely by DNA self-assembly. Further more, iter- ations and composition of transducers is also possible and hence all computable functions can be obtained. The project is composed of two major tasks, 1. To simulate computation by a finite state machine with output by a single assembly of input molecules and TX transition molecules. 2. To obtain transducer computation with a programmale input by DNA 2-state devices and TX molecules. Intelectual Merit. The project prototypes a nanomachine that is potentially programmable and produces an output that can serve as an input in a new device or as a template for orga- nization and growth of nanostructures used in nanoelectronics. The proposed machine has a potential for an algorithmic control of this growth. Theoretically, the design of the machine and the need for encoding (locally and globally) that is error correcting will lead to development of new techniques in algorithmic pattern design. Broader Impact. Research in DNA-based computation relies on many disciplines, such as computer science, DNA chemistry, nucleic acid enzymology, thermodynamics and molecular physics. Few individuals enter in to it with adequate preparation. We will attempt to provide some remedy for this problem during the course of this project. The graduate, undergraduate and high school students who participate in this work will be uniquely trained and will be prepared as unique interdisciplinary research scientists. Three graduate students (two at New York University and one at the University of South Florida) will receive graduate training through this award. They will meet with each other, and become familiar with the thinking and methodologies of their opposite colleagues in the other university. In addition, we will include an undergraduate in the project, to gain experience in combining computer science with DNA nanotechnology. We aim to include a high school student in the parts of the work for which they are eligible (e.g., computation and experiments not entailing the use of radiation). Besides their own nanotechnological and mathematical disciplines, the PI and the co-PI are prominent members of the DNA-based computation community. Both facets of this commu- nity recognize that it is converging with structural DNA nanotechnology. In recognition of this interdisciplinary phenomenon, the PI and the co-PI are involved in founding (as president and treasurer, respectively) the International Society for Nanoscale Science, Computation and Engineering" with a goal to facilitate communication among the members of the participating communities, and to recognize and promote the careers of the younger members, by offering them recognition and a forum for their ideas.
