FET: Small: Exploring the Computational Power of Stochastic Processes in Molecular Information Technology

随着计算技术的成熟，将可编程计算设备嵌入到以前几乎不可想象的物体和材料中成为可能：例如，火星上的自主机器人、带有嵌入式毫米级电子电路的“智能尘埃”飞秒卫星和“智能油漆”、具有嵌入式生化电路的“智能”分子疗法、具有嵌入式基因调控网络控制其活动的基因工程活细胞，以及具有控制分子材料组装和分解的可编程分子机器人的“智能”化学。随着微型化达到纳米和分子尺度，器件的制造和操作都变得不可靠，最终受到随机效应的支配。尽管经过了几十年的研究，但在高水平随机性存在的情况下的计算理论仍然不发达，因此构建随机计算系统的实践受到限制。虽然之前的大部分工作都集中在容错设计上，这些设计能够使用不可靠的和随机的组件稳健地实现确定性计算，但这个项目将调查分子设备的大量可用的随机操作如何提供增强的计算能力-超出了确定性实现使用相同资源所能达到的效果。因此，它将有助于为分子信息技术建立严格的计算机科学基础。长期的、可编程的分子信息技术最终将广泛影响工业和社会，因为可编程化学将使基于信息的响应性分子材料、先进的生物医学治疗和诊断、复杂的化学合成和分子尺度仪器以及分子纳米技术的其他应用成为可能。该提案包括培训和准备学生的教育和推广计划，重点是招收女性和少数族裔学生。初步调查将考虑已用于快速发展的DNA纳米技术和分子编程领域的计算模型：正式的化学反应网络、分子瓷砖自组装系统、聚合物反应网络和反应扩散系统。最近的工作表明，在小体积运行的混合良好的化学反应网络可以利用它们的随机性来表示复杂的概率分布，执行诸如概率推理等信息处理任务，并有效地寻找复杂组合问题的解。这个项目旨在通过建立在这些见解的基础上，提高对随机分子计算的好处的理解。首先，它将为产生概率分布的化学反应网络建立一个复杂性理论。其次，它将探索化学反应网络的随机约束满足如何在自组织反应扩散系统和其他结合了几何的模型中导致稳健的空间模式形成。第三，它将加深对随机自组装过程如何增强算法自组装能力的理解。一个具体的成果将是展示自组装DNA结构的随机成核如何执行类似于神经网络模式识别的信息处理任务。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.