约翰.麦卡锡 --"人工智能之父"和LISP语言的发明人
1971年的图灵奖授予提出"人工智能"这一术语并使之成为一个重要的学科领域的斯坦福大学教授约翰. 麦卡锡（ John McCarthy)。
麦卡锡1927年9月4日生于波士顿。他的父亲是一个爱尔兰移民，做过木匠和渔夫，同时也是一个发明家和工会积极分子，拥有捻船缝机和桔汁冷冻机两项专利。麦卡锡的母亲是来自立陶宛的犹 太人，热心于*女*权运动，当过记者。夫妻两人在20世纪30年代都曾参加美国共产党。受父母的影响，麦卡锡对社会问题也比较关注，参与过在加州的Palo Alto 创办自由大学的活动，倡议过修改"人*权*法*案"（the Bill of Rights，这是美国于1789年通过的对美国宪法的第一次修正案）。但与他在计算机科学上所做的工作和贡献相比，麦卡锡主要还是一个科学家而非社会活动家。此外，麦卡锡还喜欢攀登、跳伞、驾驶滑翔机等有刺激性和危险性的运动，曾和他的第二任妻子维拉.沃特森(Vera Watson)一起攀登过世界上不少大山高峰。沃特森是一位程序员，也是世界知名的女登山运动员，是第一位独自攀上西半球第一高峰、位于阿根廷和智利边界的安第斯山脉的阿空加瓜山（海拔6960米）的女性，后来在一次攀登位于尼泊尔中部的阿那波尔那峰（海拔8 075米）的妇女探险活动中不幸遇难牺牲。
麦卡锡是一个天赋很高的人，还在上初中时，他就弄了一份加州理工大学的课程目录，按目录自学了大学低年级的高等数学教材，做了教材上的所有练习题。这使他1944年进入加州理工学院以后可以免修头两年的数学，并使他虽因战时环境（第二次世界大战当时正在进行之中，美国也在珍珠港事件后宣布参战）要在军队中充任一个小职员，占去了部分时间，仍得以在1948年按时完成学业。然后到普林斯顿大学研究生院深造，于1951年取得数学博士学位。麦卡锡留校工作两年以后转至斯坦福大学，也只呆了两年就去达特茅斯学院任教（达特茅斯学院位于新罕布什尔州的汉诺威）。在那里，他发起了并成功举办了成为人工智能起点的有历史意义的"达特茅斯会议"。1958年麦卡锡到MIT任职，与明斯基(L. Minsky,1969年图灵奖获得者)一起组建了世界上第一个人工智能实验室，并第一个提出了将计算机的批处理方式改造成为能同时允许数十甚至上百用户使用的分时方式（time-sharing）的建议，并推动MIT成立组织开展研究。其结果就是实现了世界上最早的分时系统--基于IBM 7094的CTSS和其后的MULTICS。麦卡锡虽因主持该课题的负责人产生矛盾而于1962年离开MIT重返斯坦福，未能将此项目坚持到底，但学术界仍公认他是分时概念的创始人。麦卡锡到斯坦福后参加了一个基于DEC PDP -1的分时系统的开发，并在那里组建了第二个人工智能实验室。 麦卡锡对人工智能的兴趣始于他当研究生的时候。1948年9月，他参加了一个"脑行为机制"的专题讨论会，会上，冯.诺伊曼发表了一篇关于自复制自动机制论文，提出了可以复制自身的机器的设想，这激起了麦卡锡的极大兴趣和好奇心，自此就开始尝试在计算机上模拟人的智能。1949年他向冯.诺伊曼谈了自己的想法，后者极表赞成和支持，鼓励他搞下去。在达特茅斯会议前后，麦卡锡的主要研究方向是计算机下棋。下棋程序的关键之一是如何减少计算机需要考虑的棋步。麦卡锡经过艰苦探索，终于发明了著名的α-β搜索法中，麦卡锡将结合的产生与求评价函数值（或称返上值或倒推值）两者巧妙地结合起来，从而使某些子树结点根本不必产生与搜索（这谓之"修剪"--pruning或cutoff）。之所以称为α-β搜索法，是因为将处于取最大值级的结点的返上值或候选返上值PBV（Provisional Back-up Value）称为该结点的α值，而将处于取最小值级的结点的候选返上值或返上值称为该结点的β值。 这样，在求得某结点以下的α值时，就可与其先辈结点的α值相比较，若α≥β， 则可终止该结点以下的搜索，即从该结点处加以修剪，这叫β修剪；而在求得某结点以下的β值时，就可与其先辈结点的α值相比较，若β≤α，则可终止该结点以下的搜索，即从该结点处加以修剪，这叫α修剪。为了说明α-β修剪，我们举一个最简单的例子。设在取火柴棍的游戏中，A、B两人轮流从N根火柴中取1根或2根，不得多取，也不能不取。取走最后一根火柴者胜。用A(n)、B(n)表示轮到A或B时有n根火柴的状态，当n = 5时轮到A取，则如下图所示，A有两种可能，一是取2根火柴进入B（3），另一是取1根火柴进入B（4）。显然，进入B（3）后，不管B取几根，A必胜，故A必走这一步，余下的分支不必再搜索了。α-β搜索法至今仍是解决人工智能问题中一种常用的高效方法。
至于达特茅斯会议，当东道主的麦卡锡是主要发起人，另外3个发起人是当时在哈佛大学的明斯基（1969年图灵奖获得者），IBM公司的罗杰斯特(N. Rochster)，信息论的创造人香农。麦卡锡发起这个会议时的目标非常宏伟，是想通过10来个人2个有共同努力设计出一台具有真正智能的机器。会议的经费是洛克菲勒基金会资助的，包括每个代表1200美元加上外地代表的往返车票。会议的原始目标虽然由于不切实际而不可能实现，但由于麦卡锡在下棋程序尤其是α-β搜索法上所取得的成功，以及卡内基-梅隆大学的西蒙(H. A.Simon)和纽厄尔（A. Newell,这两人是1975年图灵奖获得者）带来了已能证明数学名著《数学原理》一书第二章52个定理中的38个定理的启发式程序"逻辑理论家"LT（Logic Theorist）,明斯基带来的名为Snarc的学习机的雏形（主要学习如何通过迷宫），这使会议参加者仍能充满信心地宣布"人工智能"这一崭新学科的诞生。
1959年，麦卡锡基于阿隆索.邱奇(Alonzo Church)的λ-演算和西蒙、纽厄尔首创的"表结构"，开发了著名的LISP语言（LISt Processing language），成为人工智能界第一个最广泛流行的语言。LISP是一种函数式的符号处理语言，其程序由一些函数子程序组成。在函数的构造上，和数学上递归函数的构造方法十分类似，即从几个基本函数出发，通过一定的手段构成新的函数。LISP语言还具有自编译能力。具体说来，LISP有以下几个主要特点： 1． 计算用的符号表达式而不是数； 2． 具有表处理能力，即用链表形式表示所有的数据； 3． 控制结构基于函数的复合，以形成更复杂的函数； 4． 用递归作为描述问题和过程的方法； 5． 用LISP语言书写的EVAL函数既可作为LISP语言的解释程序，又可以作为语言本身的形式定义； 6． 程序本身也同所有其他数据一样用表结构形式表示。 已经证明，LISP的这些特点是解决人工智能核心问题的关键。此外，精巧的表机制也是进一步简化LISP程序设计的方便而有力的工具，因此，LISP自发明以来，已经被广泛用于数学中的符号微积分计算，定理证明，谓词演算，博奕论等领域。它和后来由英国伦敦大学的青年学生柯瓦连斯基（R. Kowaliski）提出、由法国马赛大学考尔麦劳厄（A. Colmerauer）所领导的研究小组于1973年首先实现的逻辑式语言PROLOG(PROgramming in LOGic)并称为人工智能的两大语言，对人工智能的发展起了十分深远的意义也吸引了负责设计Algol语言的国际委员会，麦卡锡因此而被吸收为该委员会的成员。Algol中后来采纳了LISP关于递归和条件表达式这些思想。
麦卡锡在20世纪50年代末研究的另一个课题是如何程序能接受劝告从而改善其自身的性能。为此他提出过一个名为Advice Taker的系统的设想。有资料说，这是世界上第一个体现知识获取工具思想的系统，1968年建成。实际上，这个系统并未最后完成，只是完成了一部分，用LISP语言建立起了一个具有常识(common sense)的软件，能理解告诉它的是什么，并能评估其行动的后果。但正是在Advice Taker的开发过程中，启发麦卡锡提出了用"分时系统"代替"批处理系统"的建议，使计算机的使用方式引发了一场革命。
除了人工智能方面的研究和贡献这外，麦卡锡也是最早对程序逻辑进行研究并取得成果的学者之一。１963年他发表的论文"计算的数学理论的一个基础"一文（收录于P. Braffort和D. Hirschberg编辑的《计算机程序设计和形式系统》--Computer Programming and Formal Systems, North Holland, 33-70页）集中反映了他这方面的成果。麦卡锡在这篇论文中系统地论述了程序设计语言形式化的重要性，以及它同程序正确性、语言的正确实现等问题的关系，并提出在形式语义研究中使用抽象语法和状态向量等方法，开创了"程序逻辑(logics of programs)研究的先河。程序逻辑就是一种"语言"，用这种语言可以无二义地表达程序的各种性质，其语义规定了该语言中各种表达式的意义，而它的一组规则则用同意义相关的方式去操作这些表达式以计算该语言中的各种断言(assertation)的真值。研究程序的逻辑对于帮助人们了解软件是否合理十分重要，它可以用于程序的逻辑对于帮助人们了解软件是否合理十分重要，它可以用于程序验证(program verification)，自动程序设计，为优化和审计而进行的程序分析等方面。麦卡锡在上述论文中提出的方法是用递归函数作为程序的模型。他以两个链表(list)的"附加"(append)操作为例说明可以用递归的方法定义这个函数，并可以用形式化的方法证明链表的附加操作是满足结合律的(associative law ),即x @ (y @ z) = (x @ y) @ z。麦卡锡进而证明了用一系列递归定义的函数就完全可能建造大型的软件系统，并用归纳法证明这些系统所具有的性质。麦卡锡所提出的方法是有关程序逻辑研究中第一个比较系统而成熟的方法，曾被广泛地采用。
20世纪70年代以后，麦卡锡又开始研究非单调逻辑。在经典逻辑中，由已知事实推出的结论，决不会在已知事实增加时反而丧失其有效性，因此是"单调的"(monotonic)。但在人类思维过程中，由于信息的不完全和认识的局限性，常常有随着事物的发展变化，原有结论被否定和取消的情况，这就导致了所?"非单调逻辑"(nonmonotonic logic)。非单调逻辑中有一类是基于最小化语义的最小化非单调逻辑。1980年，麦卡锡在一篇论文中提出了"限制逻辑"或称"限界逻辑"，成为这类非单调逻辑中比较成功的一个体系(见J. McCarthy：Circumscription--a form of nonmonotonic reasoning. Artificial Intelligence ,Vol.13，1980，27-39页)。限制逻辑的基本思想是："限制"某个谓词P也就是排除以P的原有事实为基础所建立的大部分模型，而只保留有关P的最小模型。这与人类思考问题时总是在某些条件限制下考虑，也就是只考虑所涉及的个体或关系，而决不去涉及其他个体或关系，是比较相符的。1986年，麦卡锡在AI杂志上就限制逻辑的应用发表了进一步的研究论文："限制逻辑在常识知识形式化中的应用"(Applications of Circumscription to Formalizing Common Sense Knowledge, AI, Vol.28，1986，89-116页)，对倡导常识推理和常识研究起了十分重要的作用。
麦卡锡的主要著作有： 《自动机研究》（Automata Studies, Princeton Uni. Pr.,1956,与香农合编） 《信息学：科学美国人之书》(Information：A Scientific American Book, Freeman, 1966) 《形式化的常识：麦卡锡论文选集》(Formalizing Common Sense：Papers by John McCarthy , Ablex Pub. Co., 1990, 蒝. Lifschitz 编辑) 除了获得图灵奖以外，麦卡锡在1988年获得由日本INAMORI基金会所设立的KYOTO奖，这个奖主要奖励在高科技方面作出杰出贡献的科学家，麦卡锡是这个奖的第5位获得者。1990年麦卡锡获得美国全国科学奖章 (National Medal of Scien- -ce)。 麦卡锡的图灵奖演说题为"人工智能研究的现状"(The Present State of Research on Artificial Intelligence)。但不知什么原因，这篇演说没有发表。在《前20年的图灵奖演说集》(ACM Turing Award Lectures--The First 20 Years：1966-1985 ，ACM Pr.)中，则以"附录"(postscript)的形式约请麦卡锡另写了一篇"人工苣一般原理"(Generality in Artificial Intelligence),刊于该书257-268页。
麦卡锡现仍在斯坦福大学计算机科学系任教，其电子信箱为： jmc@cs.stanford.edu 出自《ACM图灵奖——计算机发展史的缩影》（高等教育出版社） |
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 理论计算机科学 』 → 数理逻辑大师们[转帖]
(订阅本版)
2006/4/18 15:41:00
新浪微博
顶端