1.1　生物计算的产生

人类社会文明与信息处理的计算工具息息相关。计算工具是衡量人类社会文明程度的重要依据，也是推动人类社会发展的主要动力。人类社会历经石器时代、铁器时代、蒸汽时代、电气时代、信息时代，当前正处于人工智能时代，计算工具也由简单到复杂、由低级到高级，历经结绳记事、算筹、算盘、机械计算机、电子计算机等。其中，电子计算机也从电子管计算机、晶体管计算机、个人计算机（Personal Computer，PC）发展到当今的超级计算机，它们在不同的历史时期为人类社会的发展做出了不可磨灭的贡献。图1.1所示为人类计算工具发展历程。

其实，以人类神经系统为代表的生物神经系统一直都是人类社会信息处理的最好工具，该工具也随时代的变迁不断进化，进化的结果是脑神经系统愈发复杂。图 1.2 所示为人类神经系统的进化过程示意。人脑这个信息处理系统，不仅自身在进化发展，而且人类其他信息处理工具均由它设计研发，其中电子计算机是当今广泛应用的先进人造计算工具。

电子计算机是当今人类社会信息处理的核心工具，人们的生活离不开它。但是，电子计算机的计算模型是图灵机，图灵机是串行计算模式，故电子计算机不能有效求解NP完全问题。NP完全问题的特点是所需计算量随问题规模的增大呈指数级增长。而电子计算机的工艺制造技术已达极限，这迫使人们开始寻求新的计算模型，以期通过创造新的计算工具来解决阻碍当今社会发展的NP完全问题。

在寻求新计算模型的过程中，科学家从多个领域展开探索，相继提出了模拟脑信息处理的人工神经网络、模拟遗传机理的进化计算、基于生物大分子特性的生物计算、基于量子特征的量子计算、基于光特性的光计算等。当对这些计算模型研究到一定程度时，相应的计算机就会被研发出来。因此，可形象地称当今非传统计算机的研究处于“战国时期”，生物计算是“战国”中的“一员”。

由于生物计算主要用于求解NP完全问题，故本书第2章会较详细地介绍图论基础、图灵机、可计算性，以及基于图灵机的计算复杂性理论等。

生物计算源自理查德·菲利普斯·费曼（Richard Phillips Feynman）在1961年提出的研制亚微尺度计算机的构想 ^[1] 。1973年，查尔斯·H.贝内特（Charles H. Bennett）提出了一种用酶来催化的图灵机 ^[2] ；20世纪80年代，以蛋白质为信息处理数据的二态分子计算模型被提出，称为蛋白质计算模型。蛋白质计算模型实际上是受电子计算机的影响，希望用分子产生可控的“二态”来模拟所谓的“0,1”目标。关于蛋白质计算的具体内容将在第12章介绍。

1994年，伦纳德·阿德曼（Leonard Adleman）建立了一种枚举DNA计算模型，用于求解7个顶点有向图的哈密顿路径（Hamilton Path）问题，该模型的基本原理是以DNA分子为“数据”，以生物酶与聚合酶链反应（Polymerase Chain Reaction，PCR）等为“算子”，获得问题的解 ^[3] ，详述见第6章。DNA计算模型产生的另一个重要背景是人类基因测序计划这项巨大工程的实施。人类基因测序计划促使基因工程、分子生物学理论、生化操作技术（尤其是DNA测序技术）快速发展，为DNA计算的产生、实现与发展提供了丰沃的“土壤”，也为DNA计算机的研发奠定了基础。

作者在此领域的一些早期综述文章见文献[4-8]，感兴趣的读者可自行查阅。在DNA计算的研究过程中，作者发现了一种全并行计算模型——探针机 ^[9] ，相关理论及应用将在第9章给出。 n1iNTduaDRxS9hPfcgYEd7QnLeVNpkF+Y5bsr1ppUnuGk7f1z+LZIEGQ425jp4zs