DNA计算机：数学与生命的交融，本文主要内容关键词为：数学论文,生命论文,计算机论文,DNA论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：N031：N02文献标识码：A
1 DNA计算的理论、特点和问题
1994年11月美国计算机科学家L.阿德勒曼（L.Adleman ）在《科学》上公布了DNA计算机的理论，并成功的运用DNA计算机解决了一个有向哈密尔顿路径问题〔1〕。这一成果迅速在国际上产生了巨大反响〔2〕，同时也引起了国内学者的关注〔3〕。一些人相信，DNA计算蕴含的理念可使计算的方式产生“进化”。另一些人则看到DNA 计算的理念将有助于揭示生命的本质与演化。总之，这一全新的计算理论，将在数学与生命科学中产生极其深远而广大的影响。同时它也提出了一系列值得我们深思的哲学性问题。
DNA计算机目前尚处在理论研究阶段， 一旦它在实用意义上获得成功，DNA计算将彻底改变计算机硬件的性质。在过去的半个世纪里， 计算机完全就是物理芯片的同义词。但阿德勒曼DNA 计算机则是一种化学反应计算机〔4〕。它的基本构想是：以DNA碱基序列作为信息编码的载体，利用现代分子生物学技术，在试管内控制酶作用下的DNA序列反应，作为实现运算的过程；这样，以反应前DNA序列作为输入的数据， 反应后的DNA序列作为运算的结果。 阿德勒曼具体应用哈密尔顿有向图这个经典NPC问题，详细描述了他的理论。
DNA计算机的提出，产生于这样一个发现， 即生物与数学的相似性：①生物体异常复杂的结构是对由DNA 序列表示的初始信息执行简单操作（复制、剪接）的结果；②可计算函数f（w）的结果可以通过在w 上执行一系列基本的简单函数而获得。阿德勒曼不仅意识到这两个过程的相似性，而且意识到可以利用生物过程来模拟数学过程，更确切地说是，DNA串可用于表示信息，酶可用于模拟简单的计算。这是因为：①DNA是由称作核苷酸的一些单元组成，这些核苷酸随着附在其上的化学组或基的不同而不同。共有四种基：腺嘌呤、鸟嘌呤、胞嘧啶和胸腺嘧啶，分别用A、G、C、T表示。一些单个的核苷酸顺序连在一起形成DNA链。 单链DNA可以看作是由符合A、G、C、T组成的字符串。从数学上讲， 这意味着我们可以用一个含有四个字符的字符集∑＝A、G、C、T来为信息编码（电子计算机仅使用0和1这两个数字）。②DNA 序列上的一些简单操作需要酶的协助，不同的酶发挥不同的作用。起作用的有四种酶：a.限制性内切酶，主要功能是切开包含限制性位点的双链DNA；b.DNA连接酶，它主要是把一个DNA链的端点同另一个链连接在一起；c.DNA聚合酶，它的功能包括DNA的复制与促进DNA的合成；d.外切酶，它可以有选择地破坏双链或单链DNA分子。正是基于这四种酶的协作实现了DNA计算。
自阿德勒曼用DNA计算机解决了哈密尔顿有向图问题， 随后很快便有人用DNA计算机相继解决了其他一些疑难问题（NPC完全问题），如可满足性问题等。与电子计算机相比，DNA计算机有明显的优势。不过， 这些还仅仅是利用分子技术解决的几个特定问题，是为解决特定问题而进行的一次性实验。DNA计算机还没有一个固定的程式。 由于问题的多样性导致所采用的分子生物学技术的多样性，具体问题需要设计具体的实验方案。于是，便引出了两个根本性的问题，阿德勒曼最早就意识到了它们：①DNA计算机可以解决哪些问题？确切地说，DNA计算机是完备的吗？即通过操纵DNA能完成所有的（图灵机）可计算函数吗？ ②是否可设计出可编程序的DNA计算机？ 即是否存在类似于电子计算机的通用计算模型——图灵机——那样的通用DNA系统（模型）？目前， 人们正处在对这两个根本性问题的研究过程之中。在我们看来，这就类似于在电子计算机诞生之前的20世纪三四十年代——理论计算机的研究阶段。如今，已经提出了多种DNA计算模型，但各有千秋，公认的DNA计算机的“图灵机”还没有诞生。相对而言，一种被称为“剪接系统”的DNA 计算机模型较为成功〔5〕。
由于DNA链可以比作在四字符集上的串，为DNA计算建模的自然方式就是利用专门处理字符和字符串的形式语言理论。建模的关键就是要将实际的DNA重组抽象为数学上的剪接操作。实际的DNA重组，就是在前面所提到的四种“工具酶”的作用下，对DNA 链的切割和粘贴的组合过程。其数学抽象称为剪接操作。大体可做如下描述：给定字符集∑（其元素为符号）及其上的两个字符串x、y，利用剪接规则r剪接x和y 的过程可以分为：①在由剪接规则r决定的位置上切割x和y；②分别将结果中x的前段和y的后段、y的前段和x的后段连在一起。∑上的剪接规则r是形如α[,1]＃β[,1]＄α[,2]＃β[,2]的词，其中α[,1]、β[,1]、α[,2]、β[,2]是∑上的串，＃和＄是∑外的标记符。我们称z和w是根据剪接规则r＝α[,1]＃β[,1]＄α[,2]＃β[,2]剪接x和y的结果， 当且仅当存在∑上的x[,1]、x'[,1]、y[,2]、y'[,2]使得
x＝x[,1]α[,1]β[,1]x'[,1]，y＝y[,2]α[,2]β[,2]y'[,2]
且 z＝x[,1]α[,1]β[,2]y'[,2]，w＝y[,2]α[,2]β[,1]x'[,1]
并记作（x，y）→（z，w）。α[,1]β[,1]和α[,2]β[,2]这两个串称为剪接位点；x和y称为剪接项。剪接规则r 决定了切割的位点和位置：第一项在α[,1]和β[,1]之间，第二项在α[,2]和β[,2]之间。值得注意的是位点α[,1]β[,1]和α[,2]β[,2]会分别在x和y中出现多次，如果这样，选择哪一个位点是不确定的。结果会造成对x和y剪接的结果是（z，w）的一个集合。
将剪接操作当作基本工具来构建一种生成机制，便形成了剪接系统。给定一个字符串集A，A
∑[*]，∑[*]为字符集∑上由连接操作生成的字符串的集合（∑[*]中的元素为串），以及一个剪接规则集R（r∈R
∑[*]＃∑[*]＄∑[*]＃∑[*]），由此所生成的东西是由用下方法得到的串组成：从集A开始，在A和已获得的串上重复使用剪接规则。另外，应该说明一点，通常剪接x和y得到z和w后，仍可以将x和y当作剪接项，与此相似，对新生成的x和w也没有数量上的限制。但对某些串仅可使用有限次。故在数学上不用集合来表示剪接项，而用多重集——在每个时刻都应当记录每个串可用的个数。至此，可以给出剪接系统的一个简洁而又严格的定义：剪接系统是一个四元组r＝（∑、T、A、R），其中∑是一个字符集，T
∑是终结字符集，A是∑[*]上的多重集，R是剪接规则的集合。
定义了DNA计算的数学模型后，便可以来回答前面提出的DNA计算的完备性与通用性问题。在计算机科学中，众所周知的丘奇—图灵论点深刻地刻画了任何实际计算机的计算能力——任何可计算函数都是可由图灵机计算的函数（一般递归函数）。现已证明：剪接系统是计算完备的，即任何可计算函数都可以用剪接系统来计算。换句话说就是，任何图灵机可计算的函数都可以由这种DNA计算模型来计算。反之亦然。 这就回答了DNA计算机可以解决哪些问题——全部图灵机可计算问题。
对于第二个问题——是否存在基于剪接的可编程计算机——也有了肯定的答案：对每个给定的字符集T，都存在一个剪接系统， 其公理集和规则集都是有限的，而且对于以T 为终结字符集的一类系统是通用的。这就是说，理论上存在一个基于剪接操作的通用可编程的DNA 计算机。程序由往通用计算机公理集中添加的字符串组成。程序会有多个，而可利用的公理集合有无穷多个。这些计算机使用的生物操作只有合成、剪接（切割—连接）和抽取。
理论上DNA计算机具有现代电子计算机同样的计算能力， 但它具有的巨大潜力（功能）却是电子计算机不可比拟的：DNA 计算机运算速度极快，其几天的运算量就相当于计算机问世以来世界上所有计算机的总运算量；它的贮存容量非常大，1立方分米的DNA溶液可以存储1 万亿亿位二进制的数据，超过目前所有计算机的存储容量；它的能量消耗只有一台普通计算机的十亿分之一。如此优越的分子计算机当然是激动人心的。然而它离开发、实际应用还有相当的距离，尚有许多现实的技术性问题需要去解决。如生物操作的困难，有时轻微的振荡就会使DNA 断裂；有些DNA会粘在试管壁、抽筒尖上，从而就在计算中丢失了。尽管DNA计算机面对着许许多多的质疑，但它的提出者阿德勒曼教授依然是极其乐观的：DNA计算机刚刚提出，尚在胚胎时期， 与发展了半个世纪的电子计算机相比，确实相形见绌。在他看来，提出DNA 计算机并不就是要与电子计算机竞争。首先，分子计算的观念拓宽了人们对自然计算现象的理解，特别是生物学中基本算法的理解。另外，DNA 计算的观念向现有的计算机科学和数学提出了挑战，相信它所蕴涵的理念可以使计算的方式发生进化。
DNA计算理论是目前西方发达国家的一个研究热点， 有些困难已经通过新的程序设计技术（无须等待生物技术的发展），采用概率算法及修改数学问题等传统的解决方案得以解决。人们大都相信，分子计算的实际应用在未来是可行的。另外，要知道，类似合成杂交、抽取等所有生物操作的问题，都已被大自然中的生物系统所涉及，而且这些问题在生物体内已成功的解决了，这就不会在生物体外解决不了。向大自然学习，问题就会得到解决。
2 DNA计算：计算方式的进化
1994年11月阿德勒曼在提出DNA计算机的时候就相信：DNA计算机所蕴涵的理念可使计算的方式产生进化。后来的研究者就更坚信这一点了。如加拿大的卡尔（L.Kari）就更明确的指出：“DNA 计算是考察计算问题的一种全新的方式。或许这正是大自然做数学的方法：不是用加和减，而是用切割和粘贴、用插入和删除。正如用十进制计数是因为我们有十个手指那样，或许我们目前计算中的基本功能仅因为人类历史使然。正如人们已经采用其它进制计数一样，或许现在是考虑其它的计算方式的时候了”〔6〕。我们以为，这一说法是很有启示性的。确实， 仔细回顾一下人类计算方式或计算技术的历史，就不难体会到目前人们的计算方式确实是一种历史的结果，而非计算本性的逻辑必然。不过为了进一步论证和拓展这一观点，下面有必要就什么是计算、计算的方式是什么等问题给予一个简要的回答。
计算的本质是什么？应该说人类对其已经有了一个基本的清晰的认识，这就是递归论或可计算性理论中所揭示的一个基本内容：计算就是依据一定的法则对有关符号串的变换过程。根据丘奇—图灵论点，一切可计算的函数都是递归函数。抽象地说，计算的本质就是递归。不过这里我们想给出一个直观的描述：计算就是从已知符号开始，一步一步地改变符号串，经过有限步骤后，最终得到一个满足预定条件的符号串的过程。这样一种有限的符号串的变换过程与递归过程是等价的、一致的。所谓计算方式就是符号变换的操作方式，尤其指最基本的动作方式。广义地讲，还应包括符号的载体或符号的外在表现形式。从中国古代的筹算方式（一组竹棍表征）、珠算方式，到后来的笔算方式就是一系列的计算方式的变化（它们各自具有各自的操作方式）。相对于后来的机器计算方式，这些计算的方式均可归结为“手工计算方式”，其特点是用手工操作符号，实施符号的变换——摆排竹棍、拨弄算珠或书写符号。机器计算的历史可以追溯到1641年，当年18岁的法国数学家帕斯卡尔从机械时钟得到启示——齿轮也能计数，成功地制作了一台齿轮传动的八位加法计算机。这使人类计算方式、计算技术进入了一个新的阶段。后来经过人们数百年的艰辛努力，终于在1945年成功地研制出了世界上第一台电子计算机。从此，人类进入了一个全新的计算技术时代。就电子计算机而言，至今它也经历了四个大的时期。从最早的帕斯卡尔齿轮机到今天最先进的电子计算机，计算技术有了长足的发展。这是一个计算方式发生重大变革的历史时期。这时计算表现为一种物理性质的机械的操作过程。但是，无论是手工计算还是机器计算，其计算方式——操作的基本动作都是一种物理性质的符号变换，具体是由“加”和“减”这种基本动作构成的。二者的区别就在于前者是手工的，后者是自动的。
然而，如今出现的DNA计算则有了更大的本质性的变化。 计算不再是一种物理性质的符号变换，而是一种化学性质的符号变换，即不再是物理性质的“加”、“减”操作，而是化学性质的切割和粘贴、插入和删除。这种计算方式的变革是前所未有的，具有划时代的意义。它将彻底改变计算机硬件的性质，改变计算机基本的运作方式，其意义将是极为深远的。我们完全可以做这样一番想象，一旦DNA计算机全面实现， 那么真正的“人机合一”就会实现。到那时，人们最不需要的就是电脑，因为大脑本身就是一台自然的DNA计算机， 人们真正需要的只是一个接口。DNA计算机蕴涵的理念不仅可以使计算的方式产生进化， 而且可以使人类的大脑、思维产生进化。这是我们对阿德勒曼认识的一点补充。然而，尽管DNA计算较之以往的各种计算有了重大的变革，但是， 在计算本质上，它同人类有史以来的一切计算都是等价的、一致的。这是因为：任何可计算函数都可由剪接系统来实现，即任何图灵机可计算的函数也可以由DNA计算机来计算。反之， 任何由剪接系统计算的函数都可由图灵机计算。这就是说，DNA计算也是一种递归计算。 这一结论有着重要的数学意义。它一方面使人们认识了DNA计算的本质； 另一方面进一步证实或支持了丘奇—图灵论点，使丘奇—图灵论点首次获得了电子计算机之外的生物计算机的证实，这种证实自然是更加有力的。
综上所述，我们看到，计算之所以为计算，在于它具有一种根本的递归性，或在于它是一种可一步一步进行的符号串变换操作。至于这种符号变换的操作方式如何，以及符号的载体或其外在表现形式如何，都不是本质性的东西，它们无不是一种历史的结果，无不处于一种不断变革或进化的过程之中。符号可以用一组竹棍表征、用一组算珠表征、用一组字母表征，也可以用齿轮表征、用电流表征，还可以分子表征、电子表征等等。不同表征下的符号变换有着不同的操作方式，甚至同一种表征下的符号变换都可以有不同的操作方式。在此，计算本质的统一性与计算方式的多样性得到了深刻的体现。我们相信，随着科学技术的不断发展，计算方式的多样性还会有新的表现。既然DNA 计算机的出现已经打开了人们畅想未来计算方式的思维视窗，那么就让我们翘首以待吧。
3 DNA计算：生命进化的方式
生命是什么？生命是怎样进化的？这是人类一个永恒的话题。随着自然科学的不断发展，生命问题也在不断变换着其形式，人们对它的理解、认识也在不断地更新，以适应新的理论的发展与进步。在20世纪八九十年代，由于人类基因组计划、计算机人工生命、遗传方法和DNA 计算机等一系列全新的理论和观念的出现，使人们对生命是什么、生命是怎样进化的等重大基础性问题再一次产生了新的理解。这种理解的核心内容是：生命就是一台自然计算机。生命的法则就是算法，生命就是以计算的方式在进化着。DNA 计算对这样一种生命观给予了强有力的支持。DNA计算表明了计算存在于生物学的根基上，计算处于生命的核心， 生命本身就是由一系列复杂的计算组成的。下面我们对此作一个简要的论述。
什么是算法？简单地说，算法就是求解某类问题的通用法则或方法。通常要求用它能够在有限步骤内一步一步地完成对问题的求解。换句话说，算法也就是对有关数据或符号进行变换的方法规则。计算就是对算法的执行或对数据、符号依据有关规则进行的变换操作。长期以来，计算、算法一直是数学的专有概念。但如今由于电子计算机深刻而广泛的运用，使人们对这两个基本概念有了更宽泛地认识，使它们泛化到了整个自然界。认为自然界就是一台巨型自然计算机。任何一种自然过程都是自然规律作用于一定条件下的物理或信息过程，其本质上都体现了一种严格的计算和算法特征。在此，自然系统相当于计算机的硬件，自然规律相当于计算机的软件，而自然过程就是计算机的计算过程。生命系统作为自然界中最复杂最有特色的系统，它也就是形形色色的自然计算机中的一种。
DNA计算机就是对生命这种自然机的一种表征。这是因为，DNA是生命的信息库和程序库，既是一套自复制的程序，同时又是一个以进化论为基础发展过来并正在发展的程序。它构成了遗传、发育、进化统一的物质基础。现代生物学表明，一方面DNA可以看作是由A、G、C、T 四个字符组成的字符串。从数学上讲，这意味着我们可以用一个含有四个字符的字符集∑＝｛A、G、V、T｝为信息编码。DNA 代码与计算机代码所不同的只是它不是二进制的，而是一种四进制代码。有人甚至指出：除了专业术语不同之外，分子生物学杂志里面的每一页都可以换成计算机技术杂志的内容。另一方面，DNA 能够对该信息载体进行一系列可控制的变换（即化学反应）。变换的具体方式是DNA的复制、剪切、连接、 修复，变换的过程就是一种生命过程，也即生命的自构造性特征。因此，我们完全可以把生命看作是一台自然计算机，生命的进化法则就是算法。另外，DNA作为一种自然语言，和计算机程序语言一样， 具有不同的层次，具有递归、并行、模块化的基本特征。现代生物学表明，一维线性分子在特定的环境中通过复杂而准确的信息处理，可拓展为一个丰富的四维时空生命体，这种展现过程所获得的新信息反过来又不断地反映到一维线性分子中，导致生物物种的不断进化。这正是DNA 程序语言层次性的表现。一维DNA序列只不过是最低级的生命机器语言， 所有的高级语言都必须编译成DNA序列语言才能执行。目前，DNA这种自然语言的词法、句法规则我们尚不清楚，但本质上是一种程序化语言〔7〕。
DNA计算机的提出，就是一种分子算法的化学实现。 以前分子算法，如自复制自动机、胞格自动机、遗传算法、人工生命等全都是在电子计算机上实现的，DNA计算机的出现是分子算法的化学实现的开端。 这种立足于可控的生物化学反应或反应系统，无疑更加有力地直接地表明了生物现象与过程的计算特征。而这对于现代生物学的研究自然有着十分积极的影响。正如阿德勒曼所说：DNA计算机的构想， 是从另一个角度出发启示人们用算法的观念研究生命。“算法对于生命的意义，就在于以过程或程序描述代替对生物的状态或结构描述，将生命表示为一种算法的逻辑，把对生命的研究转换成为对算法的研究”〔8〕。 在这个意义上，生命就是程序、就是算法——一种能够实现自我复制、自我构造和自我进化的算法。在尼葛洛庞帝的《数字化生存》中，有一个已是众所周知的主题论断：计算不再只和计算机有关，它决定我们的生存。但是，尼葛洛庞帝仅是从社会生活的意义上说这番话的。我们在这里则要赋予它另一种新的含义——生理生存，即计算决定我们的肉体的生存。
生物学界这种算法观念的广泛运用，更增强了人们运用算法观念看待整个自然界的信心，拓展了人们对自然现象的理解。要知道生命是最复杂的自然现象之一，是自然界进化的最高代表。因此，我们完全有理由猜想：整个宇宙也是按算法构成的，是按算法演化的。现实世界之万事万物只不过是算法的复杂程度的多样性。从虚无到存在、从非生命到生命、从感觉到意识，或许整个世界的进化过程就是一个计算复杂性不断增长的过程。看来毕达哥拉斯或许真是对的：万物皆数！应该说，这便是DNA计算机所蕴涵的最深奥的哲学理念：数学可能是万物的基础， 数学可能是现实世界和可能世界的核心。今天，我们或许应该将毕达哥拉斯的哲学再向前推进一步：存在的意识就是数学意识。因为DNA 计算宣称数学处于生命的核心。
收稿日期：2000—05—12
标签：电子计算机论文; 阿德勒论文; 数学论文; 计算机算法论文; 符号函数论文; dna论文; 符号计算论文; 生命本质论文; 电脑论文; 图灵机论文; dna分子论文;