数学史 · 中文镜像

数学家传记

伦纳德·阿德曼Leonard Adleman

出生
1945年12月31日 美国加利福尼亚州旧金山

伦纳德·阿德曼是一位美国计算机科学家,最著名的是作为RSA加密算法的创造者之一。

完整传记

伦纳德·阿德曼的父亲是一名电器销售员,母亲是一名银行出纳员。作为在旧金山长大的小男孩,阿德曼几乎没有抱负,更不用说成为数学家了。据他自己承认,他是[1]“incredibly naive and immature”。然而,是他的高中英语老师通过阅读《哈姆雷特》让他意识到思想的美。正是在这位打开他眼界的老师的建议下,“to the fact that one could see things more deeply than the purely superficial”,阿德曼进入了乔治·伯克利的加州大学。仍然犹豫不决,他最初宣布要成为一名化学家(受多年观看电视上的Mr.Wizard启发),然后是一名医生(受他的Kappa Nu兄弟会兄弟启发),最后才决定主修数学。[1]

我经历了无数的事情,最终唯一能在合理时间内脱身的就是数学。

他花了五年时间,终于在1968年毕业,随后在美国银行找到了一份计算机程序员的工作。不久之后,他申请了医学院并被录取,但他改变了主意,没有入学。他决定转而成为一名物理学家,并在银行工作期间开始在旧金山州立学院上课。他再一次失去了兴趣。

我不喜欢做实验,我喜欢思考问题。

阿德曼最终回到伯克利攻读计算机科学博士学位。他有两个动机,第一个是实际的:-

我认为获得计算机科学博士学位至少能促进我的职业生涯。

第二个更为浪漫。马丁·加德纳在Scientific American上发表了一篇关于库尔特·弗雷德里希·哥德尔定理的文章,其深刻的哲学意义让阿德曼大为震撼:-

我想‘哇。这太妙了。’有几件事我觉得很妙——黑洞、广义相对论。我想,在我的一生中,就这一次,我要真正理解这些深奥结果中的一个。

阿德曼决定读研究生,并深入理解库尔特·弗雷德里希·哥德尔的定理,而不是停留在表面。然而,在研究生院期间,他经历了另一件事——他终于领悟了数学的真正本质和引人入胜的美。他发现那就是“... less related to accounting than it is to philosophy”。

人们把数学看作某种实用技艺,……当你成为一名数学家时,关键就在于你以某种方式看透这一点,看到数学的美与力量。

1976年,阿德曼完成了他的学位论文“Number Theoretic Aspects of Computational Complexities”,获得了博士学位,并立即在麻省理工学院谋得数学助理教授的职位。(他的父亲建议他留在美国银行,至少那里有不错的退休计划)。阿德曼在麻省理工学院的同事之一是Ronald Rivest,他的办公室就在隔壁。Rivest被斯坦福大学计算机科学家Martin Hellman及其学生Whitfield Diffie在The IEEE Transactions on Information Theory上发表的一篇文章所吸引(见[2])。他们在文中描述了一种新型加密系统的构想。它基于引入新的秘密“密钥”——用于加密和解密消息的数学公式。在此之前,任何拥有加密密钥的人只需逆向执行加密指令就能解密。Hellman和Diffie提出的是相当革命性的想法——使用单向函数或数学公式,这些函数在一个方向上容易计算,但除非事先知道它们是如何构造的,否则在反方向上不可能做到。加密密钥可以公开,这样任何人都可以发送编码消息。但只有拥有密钥实际构造的人才有解密密钥,从而能够解码。

Rivest宣布将找到这样一种单向函数,从而创造出公钥密码系统。这个想法本身显然是可行的,但找到一个真正的单向函数似乎是一项艰巨的任务。Rivest有一位同样热情的支持者——他的同事Adi Shamir。然而阿德曼却不那么兴奋——他认为这个想法很不切实际,不值得追求。然而很快,Rivest和Shamir开始发明编码系统,阿德曼同意通过尝试破解每个系统来测试它们。两人提出了42种不同的编码系统,每次阿德曼都能破解。在第43次尝试中,基于一个困难的因子分解问题,阿德曼承认由于所涉及的数学,该密码确实无法破解,并且分解可能需要几个世纪的计算。Rivest彻夜未眠,准备描述该密码的手稿,然后交给阿德曼。他按字母顺序列出了论文作者——阿德曼、Rivest、Shamir。阿德曼表示异议:-

我告诉Ron,“把我的名字从论文中去掉。这是你的工作”。

但Rivest坚持,最终说服了他。

我想,‘好吧,这将是我参与过的最不重要的一篇论文,但几年后我需要简历上有足够多的条目来获得终身教职,……另一方面,我确实做了大量的智力工作来破解密码1到42。所以合理的做法是成为第三作者。’

马丁·加德纳在他的专栏中写到了这个密码,现在以相关人物的名字命名为RSA(见[3]),令阿德曼大为惊讶的是,他们和这个密码的名声迅速传播开来。大量信件涌入,而在此之前唯一研究加密技术的国家安全局(NSA)表示担心,像RSA这样看似不可破解的密码的发表可能会危及国家安全!

Rivest、Shamir和阿德曼将他们的密码专利转让给了MIT,并于1983年成立了一家公司,加利福尼亚州雷德伍德城的RSA Data Security Inc.,以制造RSA计算机芯片。阿德曼被任命为总裁,Rivest为董事会主席,Shamir为财务主管。1996年,该公司以2亿美元出售。

MIT为阿德曼提供了激发智力的氛围,但他渴望加利福尼亚,他想在那里定居并组建家庭。因此,他于1980年在洛杉矶的南加州大学找到了一份工作(他现在是那里的Henri Salvatori计算机科学讲席教授和分子生物学教授)。三年后,他在一次单身舞会上遇到了未来的妻子Lori Bruce。他们一见钟情,六周后结婚。

同年,阿德曼与R S Rumely和C Pomerance发表了一篇论文,描述了一种用于区分素数与合数问题的‘近乎多项式时间’确定性算法。这是理论计算机科学中第一个发表在Annals of Mathematics上的结果(见[4])。

这一年还见证了计算机科学的一个里程碑式发展。南加州大学的研究生Fred Cohen提出了关于“a program that can 'infect' other programs by modifying them to include a possibly modified version of itself”的新想法。阿德曼是Cohen的导师,他一得知这个想法就立即确信它会奏效。他向Cohen提议将程序命名为‘病毒’,Cohen最终于1984年发表了他的第一篇病毒论文,并于1986年发表了关于同一主题的博士学位论文。

阿德曼生活中的一个关键转折点出现在90年代初,当时他将热情转向免疫学领域。他对免疫学兴趣日益增长的原因之一是免疫学中未解决的问题“had the kind of beauty mathematicians look for”[5]。阿德曼很快专注于研究称为T淋巴细胞的白细胞,这些细胞在艾滋病患者中的稳步下降使他们容易受到致命感染。T细胞主要分为两种类型——CD4和CD8。在健康和新感染者中,每立方毫米血浆中大约有800个CD4 T细胞。然而,在与艾滋病相关的长达十年的潜伏期内,这个数字逐渐下降。通常,在CD4细胞计数降至200以下后,艾滋病特征性感染就会开始。然而,“losing a T cell is not like losing an arm or a leg”[5]。人体,即使是HIV感染者的人体,也可以通过制造新的T细胞来补充T细胞计数。为什么HIV感染患者的CD4 T细胞群会缩小,这相当神秘。

阿德曼和其他人提出,问题在于监测T细胞水平的稳态机制——它不区分CD4和CD8细胞。因此,每当它检测到T细胞丢失时,稳态机制就会同时生成CD4和CD8细胞以恢复T细胞总数。然而,CD8细胞的增加有效地抑制了CD4细胞的产生,因此HIV继续攻击CD4,从而降低其数量。正如阿德曼所说[5]:-

稳态机制……是盲目的。

阿德曼和旧金山加利福尼亚大学的弗洛伦斯·南丁格尔·大卫 Wofsy在1993年2月的Journal of Acquired Immune Deficiency Syndromes(JAIDS)上描述了他们对这一假说的检验(见[6])。遗憾的是,艾滋病研究界对阿德曼想法的回应并不令人鼓舞。阿德曼并未因此气馁,他决定更深入地了解HIV的生物学,以便成为更有说服力的倡导者。他进入南加州大学的分子生物学实验室,在Nickolas Chelyapov(现为阿德曼自己实验室的首席科学家)的指导下开始学习现代生物学的方法。

对阿德曼来说,这是一段密集学习的时期,他早先对生物学的看法正在经历重大转变。他解释了原因[7]:-

生物学如今是研究储存在DNA中的信息——由四个字母组成的字符串:A、T、G和C,分别代表碱基腺嘌呤、胸腺嘧啶、鸟嘌呤和胞嘧啶——以及这些信息在细胞中经历的变化。这里面有数学!

他开始阅读经典教材The Molecular Biology of the Gene,该书由因沃森-克里克模型而闻名的詹姆斯·D·沃森(见[13])合著。阿德曼生动地叙述了他研究一种相当特殊的酶[7]的描述时的情景:-

一天深夜,我躺在床上读沃森的教材,读到对DNA聚合酶的描述。这是酶之王——生命的制造者。在适当条件下,给定一条DNA链,DNA聚合酶会产生第二条“沃森-克里克”互补链,其中每个C都被G取代,每个G都被C取代,每个A都被T取代,每个T都被A取代。例如,给定一个序列为CATGTC的分子,DNA聚合酶将产生一个序列为GTACAG的新分子。聚合酶使DNA能够复制,进而使细胞能够复制,最终使你能够繁殖。对于严格的还原论者来说,DNA聚合酶对DNA的复制就是生命的全部意义。

他继续写道:-

DNA聚合酶是一台令人惊叹的小型纳米机器,一个单分子“跳”到一条DNA链上并沿着它滑动,“读取”它经过的每个碱基,并将其互补碱基“写”到一条新的、正在生长的DNA链上。

这是阿德曼顿悟的时刻:-

躺在那里欣赏这种神奇的酶时,我惊讶地发现它与艾伦·图灵在1936年描述过的某种东西相似,艾伦·图灵是著名的英国数学家。

阿德曼当时正在思考“艾伦·图灵机”。

他的机器有一个版本由一对纸带和一个称为有限控制器的机制组成,该机制沿着“输入”纸带移动读取数据,同时沿着“输出”纸带移动读取和写入其他数据。有限控制器可以用非常简单的指令编程,人们可以轻松编写一个程序,在输入纸带上读取一串A、T、C和G,并在输出纸带上写出Watson-Crick互补串。与DNA聚合酶的相似性几乎再明显不过了。

甚至还有更多是真的:-

但有一条重要信息使这种相似性真正引人注目:图灵的玩具计算机被证明是通用的——尽管它很简单,但可以通过编程来计算任何可计算的东西。(这个概念本质上是著名的“丘奇论题”的内容。)换句话说,人们可以编程一个图灵机来产生Watson-Crick互补串、分解数字、下棋等等。

阿德曼几乎无法抑制他的兴奋:-

这一认识让我从床上坐了起来,对妻子洛里说:“天哪,这些东西可以计算。”那一夜我再没睡着,一直在想办法让DNA来解决问题。

他欣然决定制造一台DNA计算机,类似于艾伦·图灵机,但用酶取代有限控制器。十年前,IBM研究员Charles H. Bennet和Rolf Landauer已提出过基本类似的想法(见[8]),但当时还不确定是否存在既能产生Watson-Crick互补链又能执行其他数学功能的酶。阿德曼希望他的DNA计算机至少能做一些像下棋一样有趣的事情。为此,他开始学习DNA化学的基本工具,如聚合酶、连接酶、凝胶电泳、DNA合成等。商业DNA可根据特定要求定制且易于获得,这对他的目的帮助极大。

现在可以在纸上写下一段DNA序列,寄给商业合成机构,几天后就能收到一个试管,其中含有大约分子数量的DNA,全部(或至少大部分)具有所描述的序列。……这些分子以干燥形式装在小管中交付,看起来是一小团白色无定形块状物。

理论上,建造一台能计算任何可计算问题的计算机只需要两样东西——一种存储信息的方法以及作用于信息的简单操作。DNA本身就是信息的存储库(它包含‘生命的蓝图’!),而像聚合酶这样的酶已被用来操作这些信息。阿德曼知道他已经拥有足够的东西来建造一台通用计算机。

接下来他必须做的是选择一个他的DNA计算机能够解决的问题。阿德曼决定选择哈密顿路径问题。

……给定一个有向边图以及指定的起始顶点和终止顶点,当且仅当存在一条从起始顶点出发、在终止顶点结束并恰好经过其余每个顶点一次的路径时,称存在一条哈密顿路径。哈密顿路径问题就是对于任何给定起始和终止顶点的图,判定是否存在哈密顿路径。

尽管哈密顿路径问题已被广泛研究,但求解它的高效算法仍未出现。20世纪70年代初的研究表明,该问题根本不可能存在高效算法(证明这一点至今仍是一个未解决的问题!)。事实上,它属于一类更大的问题,称为“NP完全”问题。然而,仍有如下一些算法可以奏效:

给定一个有向图GG,有nn个顶点,起点为uu,终点为vv,

  1. 在图中生成一组随机路径。
  2. 删除任何不以uu开始且以vv结束的路径。
  3. 删除任何不恰好经过nn个顶点的路径。
  4. 删除任何不至少经过每个顶点一次的路径。
  5. 如果该集合非空,则说“Yes”;否则说“No”。

插图:Adleman.gif ↗
尽管这个算法效率不高,但只要路径生成得足够随机,并且所得集合足够大,它就能给出相当正确的结果。阿德曼在他的第一次DNA计算中使用的正是这个算法。对于他的哈密顿路径问题,他选择了以下有向图:

在这个图中,哈密顿路径的起点和终点分别是0和6。阿德曼首先为图中的每个顶点和每条边分配了一个随机的DNA序列(这些序列被称为寡核苷酸)。由于每个DNA序列都有其Watson-Crick互补序列,每个顶点都关联着它的互补序列。一旦编码确定下来,顶点对应的互补DNA序列和边对应的序列就被合成出来。剩下的步骤最好由阿德曼本人来描述:-

我取了一小撮(大约101410^{14}个分子)每种不同的序列,把它们放入一个共同的试管中。为了开始计算,我只是加入了水——再加上连接酶、盐和少量其他成分,以近似细胞内的条件。总共只用了大约五十分之一茶匙的溶液。在大约一秒钟内,我手中就有了哈密顿路径问题的答案。

阿德曼随后不得不进行一个相当繁琐的实验,通过这个实验他必须剔除大约100万亿个编码非哈密顿路径的分子。他实现了上述算法这一事实意味着,在执行完所有前面的步骤之后,试管中剩下的任何DNA都必然编码所需的哈密顿路径。最终,阿德曼花了七天时间在分子生物学实验室里完成了世界上第一次DNA计算。

阿德曼在Science1994年11月号上报告了他的这一杰出发现(见[9]),如今他被恰如其分地誉为“DNA计算之父”。分子计算是当代科学研究中最令人兴奋的领域之一,在阿德曼的实验之后的几年里,它见证了一些引人注目的突破。1995年,普林斯顿大学的Richard J. Lipton提出了(见[10])另一个著名的“NP完全”问题——即所谓“满足”问题(SAT)——的DNA解法。2002年,由以色列雷霍沃特魏茨曼科学研究所的Ehud Shapiro领导的一个研究团队设计出一种由酶和DNA分子组成的分子计算机器,它每秒可执行330万亿次操作,比最快的个人计算机还要快100,000倍以上。几个月内,同一个团队就在他们先前模型的基础上改进出一种新模型,其中DNA输入同时也是机器的燃料来源(见[12])。《吉尼斯世界纪录大全》承认这台计算机是迄今建造过的“the smallest biological computing device”[11]。

这类DNA计算设备在制药和生物医学领域具有革命性的意义。科学家们预见到一个未来,那时微小的DNA计算机将能够监测我们的健康状况,并释放正确的药物来修复受损组织。Shapiro [11]说:-

自主生物分子计算机或许能够作为“细胞中的医生”工作,在活细胞内运行并感知宿主的异常……通过查询其编程的医学知识,计算机可以通过合成并释放药物来对异常做出反应。

大卫 Hawksett,吉尼斯世界纪录的科学评委,恰如其分地指出[11]:-

这是一个让科幻作家也难以跟上的研究领域。

这种‘细胞中的医生’的分子计算愿景,只是科学家们正在大力追求的众多愿景之一,他们现在是新‘分子科学’的执火炬者,这门科学试图深入探索生命隐藏的奥秘。确实引人注目的是,看似迥异却同样多产的生物学和数学领域的结合催生了这样一项事业。在这个专业分工激烈的时代,同样令人鼓舞的是,这一切是由一位数学家开始的。也许有一天我们能够证明阿德曼的愿景[7]:-

在过去半个世纪里,生物学和计算机科学蓬勃发展,毫无疑问,它们将成为新千年我们科学和经济进步的核心。但生物学和计算机科学——生命与计算——是相关的。我相信,在它们的交界处,伟大的发现正等待着那些寻求它们的人。

参考文献

正文里的方括号编号指向这里,悬停即可直接看到条目。书目保留原文——译了书名反而查不到文献。

延伸资源

原站列出的延伸阅读与外部数据库,照原样保留,目标多为英文页面。