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

随着越来越复杂的分子系统的建立，科学家和工程师在纳米尺度上组织和控制物质的能力正在迅速提高。越来越明显的是，需要一种系统的方法来指导分子工程师关于哪些类型的系统对构建有用并能够产生有趣的行为。想想20世纪40年代S时期计算机科学的状况，当时正值信息革命的黎明。一些专门用途、容易出错的计算机已经建成。艾伦·图灵和其他人刚刚开始了可计算性理论的理论研究，该理论告诉我们，在给定无限资源的情况下，计算机可以做什么。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.