从理论上的算法到物质化的算法

---记杨东屏研究员讲座

2006 年5月30日 晚上7点，应北京大学逻辑、语言与认知研究中心以及书生研究中心邀请，中科院软件所研究员杨东屏先生来到文史楼117教室，为北大师生作了一次有关算法与计算机的讲座：从算法说谈计算机。

杨东屏 先生首先从算法的历史讲起。今天我们普遍采用的记数法是由印度人于公元5世纪末发明的。公元9世纪初，这种先进的记数法传到了两河流域的巴格达。来自Khwarizmi的数学家Alkhwarizmi在巴格达学习了这种记数法，在此基础之上，Alkhwarizmi总结了关于自然数运算的一些算法，并把它们写于其著作《Algoritmi de numero Indorum》之中。历史上，这是对自然数算法的第一次系统总结。公元16世纪，这部著作传到了欧洲。或许是翻译出现了问题，或许是出现了其它问题，总之经过漫长的7个世纪，当Alkhwarizmi的这部著作传播到欧洲的时候，欧洲人错误地理解了“Algoritmi”这个词语的含义，他们把这部著作理解为：关于印度数字的规律。今天英语中的“Algorithm”一词即来源于此。

随后， 杨东屏 先生讲述了算法得到严格定义的历史过程。随着数学的不断发展，人们发现或许有些数学问题没有算法。一个很自然的问题是：究竟什么样的问题算法不可解？若要彻底解决这个问题，一个必要的前提就是给出算法的准确定义。1931年,哥 德尔发表了自己的不完全性定理，在证明过程中哥德尔定义了一类可计算函数，即原始递归函数，人们发现，所碰到的可计算函数一般都可以表示为原始递归函数， 于是就有人猜想：或许原始递归函数就是算法可计算函数的数学定义。但很快，阿克曼发现了一个函数，这个函数是可计算的，但是它的值的增长速度大于任何一个 原始递归函数，这就表明，存在一个可计算函数不是原始递归函数。1934年，受厄布 朗的启发，哥德尔在等式系的形式系统中定义出了递归函数，随后，哥德尔在普林斯顿高级研究院报告了自己的结果，这是历史上第一次给出算法可计算函数的定 义。此后，别的数理逻辑学家又陆续给出了其它一些算法可计算函数的定义，但它们都被证明与递归函数等价，这可以说明：递归函数就是对算法这个直观概念的准 确刻划。 杨东屏 先生讲到，在这些定义当中，应该特别指出的是图灵定义的图灵机，与别的定义相比，图灵机与人通常的计算过程非常相似。也正是由于图灵机的提出才使哥德尔相信，在递归函数之外并不存在别的算法可计算函数。

算法的严格定义的提出，尤其是图灵机的提出，使得算法的物质化，即通用电子计算机的出现，成为可能。 杨东屏 先生介绍了两种通用电子计算机的理论构想，一个是冯·诺依曼设计的EDVAC（Electronic Discrete Variable Automatic Computer）方案，一个是图灵提出的ACE（Automatic Computing Engine）计划。应该说，这两种理论构想都建立于图灵机的理论之上，它们的主要区别在于：冯·诺依曼的EDVAC方案主要面向数值计算，希望造出的计算机能够完成复杂的计算，而图灵的ACE计划主要面向人工智能，希望造出的计算机能够很好的模拟人的大脑。19世纪五十年代左右，这两种理论构想前后在现实中得以实现。在美国，依据冯·诺依曼的设计思想，科学家们造出了EDVAC，这就是今天很大程度上改变了我们生活的计算机的原型。在图灵的参与下，英国的科学家们也成功地造出了ACE。不过由于二战的原因，当时的英国在经济上并不宽裕，因此与EDVAC主要用硬件堆积不同，ACE较多地依靠软件来完成自己的运算。

最后， 杨东屏 先生还简要介绍了图灵在普林斯顿的工作，指出图灵提出的人机交互式系统对于计算机今后的进展具有一定的价值。

杨东屏 先生的讲座为听众展示了算法概念的明晰到计算机产生的过程，揭示了算法在当代计算机理论中的核心概念的地位和作用。

(琚凤魁  2006.6.6)