AF: Small: Theory of Molecular Programming: Computability and Complexity

随着越来越复杂的分子系统的建立，科学家和工程师在纳米尺度上组织和控制物质的能力正在迅速提高。越来越清楚的是，需要一种系统的方法来指导分子工程师构建有用且能够产生有趣行为的系统。想想20世纪40年代信息革命初期的计算机科学状况吧。一些专用的、容易出错的计算机被制造出来了。艾伦·图灵和其他人刚刚开始了可计算性理论的理论研究，该理论告诉我们，在无限资源的情况下，计算机可以做什么。直到20年后，计算复杂性理论才出现，该理论研究的是在有限资源的情况下，计算机能做什么。如今，研究人员发现自己在分子计算领域也处于类似的境地。这方面的实验工作正变得越来越复杂。DNA链位移已被用于构建逻辑电路，其组件是自由漂浮的DNA链和复合物，能够计算平方根。DNA瓦片组装已被用于实现能够生长成分形图案和计数二进制的细胞自动机。DNA折纸技术使精确控制和放置各种分子结构和系统成为可能。pi相信分子编程最终将允许制造和控制纳米级和宏观人工制品，其纳米级部件以纳米级精度排列，这些人工制品将具有与生物有机体相当的复杂性，并且分子制造范式将受到生物生长和发育的启发。使用严格的数学模型，精确地研究分子系统可能实现哪些壮举，不可能实现哪些壮举，是本提案的主要目标。工作将集中在各种资源边界之间的权衡，这些资源边界是由分子编程产生的。这些包括不同分子种类的数量，键类型的数量，消耗的燃料分子的数量，以及组装/计算所需的时间或体积。将研究分子运动、刚性、随机性和不确定性等分子资源。今天，对于哪些任务可以通过化学有效地执行，我们完全没有正确的理解。本项目的主要目标是发展这种认识，并为分子编程的系统发展提供理论基础。该项目包括为夏季本科生提供资金，pi将作为大四本科生项目的顾问。此外，pi将参与教授传统上与计算机科学无关的学生，以便未来的分子工程师可以接触到设计复杂纳米级化学系统所需的方法和实践。学生将学习分子编程理论，并成为在这个令人兴奋的领域工作的新一代的一部分。拟议的研究将辅以当地K-12学校中代表性不足的少数民族的教育和推广活动。

The ability of scientists and engineers to organize and control matter at the nanoscale is rapidly improving as ever more complicated molecular systems are being built. It is becoming clear that a systematic approach is needed to guide molecular engineers as to the kinds of systems that are useful to construct and are capable of interesting behavior. Consider the state of computer science in the 1940's, at the dawn of the information revolution. A handful of special-purpose, error-prone computers had been built. Alan Turing and others had just initiated the theoretical study of computability theory, which tells us what computers can do given unlimited resources. It was to be 20 years before the advent of computational complexity theory, the study of what computers can do given limited resources. Researchers find themselves in a similar position today in molecular computing. Experimental work in this area is becoming more and more sophisticated. DNA strand displacement has been used to construct a logic circuit, whose components are free-floating DNA strands and complexes, capable of computing square roots. DNA tile assembly has been used to implement cellular automata capable of growing into fractal patterns and counting in binary. DNA origami is enabling precise control and placement of a variety of molecular structures and systems. The PIs believe that molecular programming will ultimately allow fabrication and control of nanoscale and macroscopic artifacts whose nanoscale parts are arranged with nanoscale precision, that these artifacts will have complexity comparable to that of biological organisms, and that molecular fabrication paradigms will be inspired by biological growth and development.Investigation of precisely what feats are possible and impossible to implement with molecular systems, using rigorous mathematical models, is a primary aim in this proposal. Work will focus on the tradeoffs between various resource bounds that arise uniquely from molecular programming. These include number of distinct molecular species, number of bond types, amount of fuel molecules consumed, and time or volume required for assembly/computation. Molecular resources such as molecular motion, rigidity, randomness and nondeterminism will be studied. Today, a proper understanding of which tasks are efficiently executable by chemistry is totally absent. The major goals of this project are to develop this understanding and provide a theoretical foundation for the systematic development of molecular programming.The project includes funding for summer undergraduate students, and the PIs will act as advisees for senior-year undergraduate projects. Additionally, the PIs will be involved in teaching students that are not traditionally associated with computer science so that future molecular engineers can be exposed to methods and practices needed for designing complex nanoscale chemical systems. Students will learn the theory of molecular programming and be part of a new generation to work in this exciting field. The proposed research will be complemented by educational and outreach activities with underrepresented minorities from local K-12 schools.