As computing technology matures, it becomes possible to embed programmable computing devices into objects and materials where it was previously almost unthinkable: autonomous robots on Mars, ?smart dust? femtosatellites and ?smart paint? with embedded millimeter-scale electronic circuits, ?smart? molecular therapeutics with embedded biochemical circuits, genetically engineered living cells with embedded genetic regulatory networks controlling their activity, and ?smart? chemistry with programmable molecular robots that control the assembly and disassembly of molecular materials, for example. As miniaturization reaches the nanometer and molecular scale, both device fabrication and device operation become unreliable, ultimately dominated by stochastic effects. Despite decades of study, the theory of computation in the presence of high levels of stochasticity remains underdeveloped, and the practice of building stochastic computing systems is limited accordingly. While the majority of prior work has focused on error-tolerant designs that enable robust implementation of deterministic computation using unreliable and stochastic components, this project will investigate how the abundantly available stochastic operation of molecular devices can provide augmented computing power ? going beyond what a deterministic implementation could achieve with the same resources. As such, it will help establish a rigorous computer-science foundation for molecular information technology. Long-term, programmable molecular information technology is poised to eventually impact industry and society broadly, as programmable chemistry will enable information-based responsive molecular materials, advanced biomedical therapeutics and diagnostics, sophisticated chemical synthesis and molecular-scale instruments, and other applications of molecular nanotechnology. The proposal includes education and outreach plans to train and prepare students with emphasis on recruiting students from women and minority groups.
Initial investigations will consider models of computation that have been used in the rapidly developing fields of DNA nanotechnology and molecular programming: formal chemical-reaction networks, molecular tile self-assembly systems, polymer-reaction networks and reaction-diffusion systems. Recent work has shown that well-mixed chemical-reaction networks operating in small volumes can utilize their stochasticity to represent complex probability distributions, to perform information-processing tasks such as probabilistic inference, and to effectively search for solutions to complex combinatorial problems. This project aims to improve understanding of the benefits of stochastic molecular computation by building on these insights. First, it will establish a complexity theory for chemical-reaction networks that generate probability distributions. Second, it will explore how stochastic constraint satisfaction by chemical-reaction networks can lead to robust spatial pattern formation in self-organizing reaction-diffusion systems and other models that incorporate geometry. Third, it will develop an understanding of how stochastic self-assembly processes can augment the power of algorithmic self-assembly. A concrete outcome will be a demonstration of how the stochastic nucleation of self-assembled DNA structures can perform an information-processing task similar to pattern recognition by neural networks.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
