我多么希望我能记起那个圆,
那是阿基米德破解的确切关联。
作者不详,由J. S. 麦凯叙述
《π、
和e的记忆法》,1884年
哥贝克力石阵位于土耳其南部,靠近幼发拉底河的源头。在对该遗址的发掘中,研究人员发现了一系列神秘的巨石阵。4米高的石灰岩石柱围成10~20米宽的圆圈。这些圆圈以一对更大的巨石为中心。这些石柱的形状类似于一个拉长的“T”。大多数石柱都刻有丰富的动物浮雕。在某些部位上的图案令人联想到人的手和手臂。石阵总共有20个圆圈和大约200根石柱。
哥贝克力石阵令人印象深刻,但它真正的不同寻常之处在于其建造年代。该遗址可追溯到公元前10000年至公元前8000年,远远早于古苏美尔。这使哥贝克力石阵成为世界上已知的最古老的巨石遗址。
在6 000年后的欧洲,仍然存在建造巨石圆圈的做法。人们不禁要问,这个圆圈到底有什么特别之处,以至于人类在如此长的时间里选择将其作为一种最伟大的纪念碑建筑?
圆的根本特征是从中心点到边缘的距离是恒定的。这个距离就是圆的 半径 (radius)。圆的 直径 (diameter)或宽度是其半径的两倍。一个圆的 周长 (circumference)是其边缘的长度。一个圆越大,它的周长和直径就越大。可以通过测量来衡量周长与直径之间的关系。拉直一根绳子穿过圆的直径,并将其长度与周长进行比较。你会发现这个圆的周长略大于它直径的三倍。重复测量后能够发现,这个比率对于所有大小的圆来说都是恒定的。当然,从数学的角度来看,“三倍多一点”这个结论并不是特别令人满意。数学家想要的是精确的答案。确定一个圆的周长与直径的精确比率是一场永无止境的探索。
这个确切的比率——不管其真实值是多少——如今用希腊字母π来表示。威尔士数学家威廉·琼斯(William Jones)在1707年首次使用π表示圆周率,古希腊人并不这样用。
把π的真实值全写下来是不可能的。18世纪60年代,约翰·海因里希·兰伯特(Johann Heinrich Lambert)证明了π是一个 无理数 (irrational number),这意味着想要枚举π需要无限多位数字。无论枚举到什么程度,数字都不会出现循环。人们最多能做到获取π的近似值。
除了前面几个整数外,π可以说是数学中最重要的数字。如果没有π,我们就很难对圆和球体进行推理。计算圆周运动、旋转和振动将成为数学难题。π的值被用在许多实际应用中,从建筑到通信、从航天飞行到量子力学。
最早的近似估计3,只对了一位数。大约在公元前2000年,巴比伦人估计π是 =3.125,算对了两位数。埃及莱因德纸草提供了一个略好一点的近似值 =3.16049,接近算对了三位数。然而,计算π值的第一个真正突破来自希腊数学家阿基米德。
阿基米德(约公元前287—公元前212年)被认为是古代最伟大的数学家之一。他出生在西西里岛的锡拉库萨,那里当时是希腊殖民地的一部分。
阿基米德的生平细节不详。今天,人们记住的是他从浴缸里跳起来,跑到街上大喊“Eureka!”(意思是“我找到了!”)的一幕。这个故事出自维特鲁威(Vitruvius)撰写的史书。书中提到阿基米德受国王之托检查一顶王冠。国王怀疑他的金匠偷偷地用一种廉价的金银合金代替了纯金。合金看起来和真金一模一样。阿基米德能找到真相吗?
在金银合金和纯金之间有一个可以测量的差别:纯金的密度更高。物体的密度是它的重量(或质量)除以它的体积。王冠的重量是可以测量的。然而,确定它的体积似乎是不可能的,因为它的形状是不规则的。
在一个充满宿命意味的夜晚,阿基米德爬进浴缸时,浴缸里的水碰巧溢出来了。就在那个瞬间,阿基米德意识到,想要测量一个不规则物体的体积,可以通过测量它浸入水后的排水量来实现。这一推论使他得以确定王冠的密度。
那顶王冠并非纯金打造。金匠犯罪了。
阿基米德破解了一系列重要的力学难题,包括阐释了杠杆定律。然而,他最大的贡献是在几何学上。他的诸多研究推动他探求π的正确值。他的研究成果是一种前所未有的精确计算π值的算法。
阿基米德的π近似算法基于三个方面的认识。首先,正多边形与圆形的外形近似。其次,多边形的周长很容易计算,因为它的边是直的。最后,正多边形的边越多,越接近于圆形。
想象一个圆。然后想象一个六边形(一个正六边形)画在这个圆的内部(图2.1)。六边形的角与圆的边缘相接触,它的边刚好在圆的内部。因为六边形比圆小,所以按道理讲,六边形的周长接近圆的周长,但略小于圆的周长。 [1]
一个正六边形在轮廓上近似于六个完全相同的三角形边对边合在一起,每个重合的边都指向中心点。这些三角形是 等边 (equilateral)三角形,也就是说,所有三条边的长度相等。由于一个六边形有六条边,所以它的周长等于六条三角形边长之和。六边形的直径等于两条三角形边长之和。因此,正六边形的周长与直径之比是 =3。因此,3是π的一个合理近似值。
现在,想象在圆的外面画一个六边形(图2.1)。在这种情况下,六边形每个边的中间与圆接触,而不是角与圆接触。圆的直径现在等于从六边形中心点到其中一边中点距离的两倍。这个更大的六边形的周长是圆直径的 倍。这就得出了π的另一个估计值:3.46410。这个估计值接近真实值,但大了一点。
图2.1 一个带有内六边形的圆(左)和一个带有外六边形的圆(右)。内六边形包含构成它的等边三角形
阿基米德用一种算法改进了这些近似推算。该算法每次迭代都会使两个多边形的边数翻倍。多边形的边越多,用它获得的π的近似值就越可靠。
算法的操作如下:
以一对内多边形和外多边形的周长作为输入。
内多边形周长和外多边形周长相乘。
除以二者之和。
得出一个新的外多边形的周长。
把这个新外多边形的周长乘以之前的内多边形周长。
求平方根。
得出一个新的内多边形的周长。
输出新的内多边形和新的外多边形的周长。
在第一次迭代中,算法将六边形变成了十二边形(有12条边的图形)。这样得到π的估计值为3.10582(内多边形)和3.21539(外多边形),提高到了六位数。
阿基米德算法的美妙之处在于,它可以反复运行。一次运行得到的输出可以作为下一轮迭代的输入进入算法中。这样一来,十二边形就可以转化为二十四边形。四十八边形可以变成九十六边形,以此类推。每一次重复,内多边形和外多边形都向圆更逼近了一点,得出更好的π估计值。
阿基米德完成了一个九十六边形的计算,得到π的两个估计值: 前者精确到四位数。后者不那么精确,但更简单,因而更受欢迎。
不幸的是,阿基米德在锡拉库萨陷落时被一名罗马士兵杀害了。关于这次冲突,有不同版本的描述。在一个版本中,阿基米德拒绝陪同士兵去见他的上级军官,理由是他正在研究一个特别有趣的问题。在另一个版本中,阿基米德试图阻止那个士兵偷他的科学仪器。令人惊奇的是,在将近2 000年之后的1699年,阿基米德的算法才被超越。
考古证据表明,文明出现在中国的时间与出现在美索不达米亚和埃及的时间差不多。中国的城市社会大约最早是在长江和黄河沿岸发展起来的。我们对中国早期数学知之甚少,因为当时用来写字的竹简容易腐烂。虽然东西方之间有过交流,但中国数学似乎在很大程度上是独立发展的。
现存最古老的中国数学著作《周髀算经》于公元前300年左右问世。这本书主要涵盖历法和几何,其中包括勾股定理。《九章算术》是一部类似于莱因德纸草的数学问题汇编,从大约同一时期流传下来。
中国对π值的探究似乎比西方要执着很多。公元264年,刘徽用一个96边的内多边形得到了一个近似值——3.14,精确到了三位数。后来,他将这个方法扩展到一个有3 072条边的多边形,得到了一个改进的近似值——3.14159,精确到了六位数。
公元5世纪,祖冲之在儿子祖暅的协助下做出了更准确的估计。父子二人使用了多边形方法,与阿基米德的方法类似。然而,他们实施了更多次的迭代。他们算出的上限和下限分别为3.1415927和3.1415926,精确到了七位数,创造了新的世界纪录。他们的成就屹立了近900年,是他们卓越贡献的有力证明。
今天,我们知道π等于3.14159265359,精确到12位数。对π的计算现在由计算机算法来承担。根据吉尼斯世界纪录,π的最精确值有31万亿位。产生这一数值的程序是由来自日本的埃玛·岩尾春香(Emma Haruka Iwao)编写的。程序在谷歌云上的25个虚拟机上运行计算,共花费了121天。
公元前212年阿基米德被杀害是罗马统治欧洲的先兆。公元前146年,古希腊向罗马屈服。从公元前1世纪到公元5世纪,罗马帝国控制着地中海地区。当帝国最终灭亡时,欧洲文明也随之瓦解。此后1 000年里,欧洲数学之光忽明忽暗。在黑暗中,几个学术中心照亮了东方。
大约在公元762年,哈里发哈伦·拉希德(Harun al-Rashid)在他的新首都巴格达建立了智慧馆(Bayt al-Hikmah)。他的继任者不断扩建智慧馆,使之成为9世纪到13世纪一个重要的知识中心,这段时期现在被称为伊斯兰黄金时代。在智慧馆工作的学者将用希腊语和印度语写成的科学和哲学文本翻译成了阿拉伯语。他们还进行了数学、地理、天文学和物理学方面的原创研究。
智慧馆最有影响力的知识分子是穆罕默德·伊本·穆萨·阿尔·花剌子模,他在780年至850年间居住于巴格达。他的生平鲜为人知。然而,他有三部主要作品得以流传至今。
《代数学》(The Compendious Book on Calculation by Completion and Balancing)是一部代数著作。 事实上,英语中的“代数”(algebra)一词,就是从这本书的阿拉伯语标题(al-jabr,意思是恢复平衡)派生而来的。这本书描述了如何使用算法来解决数学问题,特别是线性方程和二次方程。 [2] 虽然此前已经有过关于代数的著作,但是阿尔·花剌子模的呈现风格引起了人们的关注。相比于其他人的工作,他的工作更系统、更循序渐进、更算法化。
阿尔·花剌子模在《印度算术法》(On the Hindu Art of Reckoning,约825年)一书中描述了十进制数字系统,我们今天使用的数字系统也在其中。 十进制数字系统起源于印度河谷文明(今巴基斯坦南部),该文明大约繁盛于公元前2600年,与吉萨金字塔的建造时间大致是同一时代。除了从宗教文献中搜集到的资料外,人们对该地区的原始数学知之甚少。一些铭文显示,9个非零的印度-阿拉伯数字(1—9)于公元前3世纪到公元2世纪之间出现在该地区。可以确定的是,西弗勒斯·塞博赫特(Severus Sebokht)主教在一封信中明确提到了9个非零的印度数字。他在公元650年左右生活在美索不达米亚地区。大约在同一时期,零(0)这个数字终于在印度出现了。
到了8世纪,由于使用起来非常方便,许多波斯学者都采用了印度-阿拉伯数字系统——阿尔·花剌子模的书就是关于这个主题的。他的著作成了印度-阿拉伯数字传向西方的渠道。1126年,英国自然哲学家巴斯的阿德拉德(Adelard of Bath)将《印度算术法》从阿拉伯语翻译成了拉丁语。阿德拉德译本之后,比萨的莱昂纳多(Leonardo of Pisa,即斐波那契)在1202年出版了关于这个主题的另一部著作——《计算之书》(Liber Abaci)。
1258年,在阿尔·花剌子模去世400年后,智慧馆在蒙古军队攻陷巴格达后被摧毁。
令人惊讶的是,人们接受新数字系统的速度很慢。用了几个世纪的时间,罗马数字(I、II、III、IV、V等)才被印度-阿拉伯数字取代。欧洲学者似乎非常乐于用算盘进行计算,并用罗马数字记录结果。直到16世纪,随着人们开始使用笔和纸来计算,十进制数字系统才成为首选。
英语中的“算法”(algorithm)一词正是来自《印度算术法》(Algoritmi de Numero Indorum)拉丁文译本书名中阿尔·花剌子模的名字。
14世纪至17世纪的欧洲文艺复兴时期,人们重新发现了古典哲学、文学和艺术。数学也重新兴起,尤其体现在会计、力学和地图制作等实践领域的应用当中。15世纪印刷机的发明进一步促进了学术和学问的传播。
随后的18世纪启蒙运动中,西方哲学发生了革命。延续几个世纪的教条在实证和理性诘问下被一扫而空。数学和科学成为思想的基础,技术进步改变了社会的方方面面,民主和对个人自由的追求占据了上风。
观念的转变、沉重的赋税和一场场农业歉收引发了1789年的法国大革命。在这场血腥的动乱中,一位法国数学家为一个算法奠定了理论基础,该算法后来成为世界上最常用的算法之一。
图2.2 1839年由皮埃尔·阿方斯·费萨尔(Pierre-Alphonse Fessard)创作的约瑟夫·傅里叶的半身像[©纪尧姆·皮奥勒(Guillaume Piolle)/CC-BY 3.0.]
1768年,让-巴蒂斯特·约瑟夫·傅里叶(Jean-Baptiste Joseph Fourier,图2.2)出生于法国欧塞尔。傅里叶9岁时成为孤儿,在当地宗教组织开办的学校接受教育。这个小伙子在数学方面的天赋在他十几岁的时候就显现出来了。尽管如此,这个年轻人还是接受了牧师培训。成年后,傅里叶放弃了政府部门的工作,投身数学事业,成为一名教师。但很快,他就卷入了席卷全国的政治剧变。受大革命理想的启发,傅里叶倒向了政治激进主义,并加入了欧塞尔革命委员会。在随后的恐怖统治中,傅里叶发现自己卷入了敌对派系之间的暴力争端。他被关进了监狱,险些被送上断头台。
此后,傅里叶以教师身份搬去巴黎进修。他因数学才能被任命为新成立的巴黎综合理工学院(École Polytechnique)的教师。仅仅两年后,他就成了分析与力学学会的主席。傅里叶似乎注定要在学术界度过一生,直到一件意想不到的事情改变了他的人生轨迹。
在拿破仑领军入侵埃及时,傅里叶被任命为法军的科学顾问。法军于1798年7月1日占领了亚历山大。从那以后,胜利转为可耻的溃败。拿破仑离开了埃及,但傅里叶留在了开罗。在那里,他把自己的科学工作分派出去,并利用业余时间对埃及的文物进行研究。
在傅里叶最终回国后,拿破仑安排这位数学家担任伊泽尔省的行政长官,该省位于阿尔卑斯地区,首府为格勒诺布尔。正是在那里,傅里叶开始撰写他的巨著。他的著作《热的解析理论》(Théorie de la Chaleur)于1822年出版。顾名思义,这本书是关于金属棒中的热传导的。更重要的是,这本书提出,任何波形都可以看成适当时间延迟的和按比例放大缩小的谐波的加合。这个想法在当时备受争议。然而,傅里叶的假定后来被证明是正确的。
为了理解傅里叶的理论,让我们来进行一个思想实验。想象一个游泳池。在泳池一端放一台造波机,假设另一端有某种溢流管且不会反射波。我们假设这台机器产生的单个波浪的波长就是游泳池的长度。我们看着波峰从泳池的一端移动到另一端,然后下一个波峰出现在起点。这个简单的波形被称为 一次谐波 (fi rst harmonic,图2.3)。它的 周期 (period)——两个波峰之间的距离——等于泳池的长度。
现在,想象一下造波机动得更快些。这一回,两个完整的波形周期等于泳池的长度。换句话说,我们总是可以在泳池中看到两个波峰,而不是一个。这个波形就是 二次谐波 (second harmonic)。它的周期等于泳池长度的一半。
图2.3 3个谐波(左)和由它们加合产生的波形(右)。二次谐波被缩小了1/2,三次谐波被延迟了1/2个周期
接下来,我们再把造波机的速度提高一倍。这一回,周期是泳池长度的四分之一。这就是 三次谐波 (third harmonic)。
再来一次翻倍,就得到 四次谐波 (fourth harmonic),以此类推。这个谐波序列叫作 傅里叶级数 (Fourier series)。
傅里叶的非凡思想是,所有的波形——无论何种形状的波形——都是缩放和延迟谐波的加合。缩放的意思是放大或缩小波形的大小。放大会使波峰更高,波谷更低。缩小则相反。延迟一个波形意味着在时间上平移它。延迟意味着波峰和波谷比之前更晚到达。
让我们来看看把谐波加合的效果(图2.3)。设定一次谐波的 振幅 (amplitude)是1。一个波形的振幅是它与平衡位置之间的最大偏差。谐波的振幅就是波峰的高度。二次谐波的振幅是1/2。三次谐波的振幅为1,延迟为1/2个周期。如果我们把这些谐波进行加合,就能得到一个新的 复合波 (compound waveform)。加合的过程模拟了现实世界中波浪相遇时发生的情况。它们就是一个骑在另一个上面。用物理学中的术语表达就是波的 叠加 (superpose)。
显然,加合波形很容易。要逆转这个过程就复杂得多。如果给定一个复合波,如何确定组成复合波的谐波的振幅和延迟?答案就是使用 傅里叶变换 (Fourier transform,FT)。
FT以任何波形作为输入,并将其分解为谐波组分。它的输出是原始波形中分解出来的每一个谐波的振幅和延迟。例如给定图2.3中的复合波,FT将输出三个谐波组分的振幅和延迟。FT的输出是两个序列,其中一个列出了谐波的振幅。对于图2.3中的复合波,各谐波组分的振幅为[1, ,1]。第一项是一次谐波的振幅,以此类推。第二个输出序列是各个谐波的延迟:[0,0, ],以周期计算。
尽管最初只是物理学家对此感兴趣,但在计算机发明后的几十年里,傅里叶变换的真正力量才突显出来。计算机可以快速地、低成本地分析各种波形。
计算机以数字列表的形式存储波形(图2.4)。每个数字代表某一特定时刻波形的水平。较大的正值与波峰相关,绝对值较大的负值与波谷相关。这些数值被称为 样本 (sample),因为计算机每隔一段时间就会对波形的水平采集一次“样本”。如果采样次数足够密集,数字列表就会给出波形形状的合理近似值。
FT首先生成一次谐波。生成的波形包含1个周期——1个波峰和1个波谷,并且与输入序列的长度等同。该算法将两个数字列表里的样本逐个相乘,例如[1,-2,3]×[10,11,12]=[10,-22,36]。然后将这些结果加合起来。加合值就是输入与一次谐波之间的 相关系数 (correlation)。相关系数是对两个波形相似性的衡量,如果相关系数较高,就表明输入中的一次谐波较强。
该算法接下来对延迟四分之一周期的一次谐波副本重复实施求相关系数的操作。这样一来,相关系数衡量的就是输入波形与延迟的一次谐波之间的相似性。
将两个相关系数值(无延迟的和延迟的)融合起来,就可以产生一次谐波的振幅和延迟的估计值。振幅等于两个相关系数的平方和再除以样本数量后的平方根,延迟是通过计算两个相关系数的相对强度得出的。相对强度表明该组分在时间上与两个版本的谐波有多接近。
图2.4 一个波形以及用来表征这一信号的相关联的样本值
对所有的高次谐波实施这种求双重相关系数(无延迟的和延迟的)和融合的操作。这就得出了它们的振幅和延迟。
综上所述,FT算法的工作原理如下:
以一个波形作为输入。
对每一个可能的谐波重复以下步骤:
产生谐波。
求输入与谐波的相关系数。
将谐波延迟四分之一个周期。
求输入与延迟谐波的相关系数。
计算谐波的整体振幅和延迟。
当所有谐波处理完毕后停止重复。
输出每一个谐波的振幅和延迟。
乍一看,把一个复合波分解成组成它的谐波的过程像是数学上的空想——展示起来很漂亮,但几乎没有实际用处。这种观点与现实相去甚远!FT被广泛用于分析现实世界中的 信号 (signal)。
信号是现实世界中随时间变化的任何量。声音信号是能被我们听到的气压的变化。在语音识别系统(如Siri、Alexa)中,FT会在进一步分析之前将声音信号分解成其谐波组分。数字音乐播放器(如Spotify、Tidal)依靠FT识别冗余谐波信息,从而降低数据存储量。
无线电信号是一种可以用电子设备探测到的电磁变化信号。在无线通信系统(如WiFi、DAB)中,FT可以使数据通过无线电信号得到有效传输和接收。
尽管FT非常有用,但它需要用掉很多算力。求相关系数需要花费大量的时间,特别是对于长波形来说。现代设备使用一种原始算法的变体,它被恰当地命名为快速傅里叶变换,或简写为FFT。
FFT发明于1965年,用以满足迫切的军事需要。冷战期间,美国希望能够监视苏联的核试验。唯一的方法是在友好国家的监测站测量爆炸引起的地震震动。不巧的是,使用传统的FT来分析地震数据的速度非常慢。科学家詹姆斯·库利(James Cooley,1926—2016)和约翰·图基(John Tukey,1915—2000)想出了一个新版本的算法,可以在很短的时间内产生相同的结果。
他们的算法利用谐波波形的对称性在不同的求相关系数阶段之间共享结果。在谐波波形中,波谷只是波峰的反面。波峰上升的那一半是下降部分的镜像。高次谐波是低次谐波的加速版。通过对中间结果的再用,消除了计算过程中不必要的重复。
这个主意很奏效。库利-图基版的FFT使美军能将苏联的核试验定位在15千米的精度范围内。
出乎意料的是,在FFT“发明”近20年后,人们发现这个算法实际上已经存在180多年了。伟大的德国数学家卡尔·弗里德里希·高斯(Carl Friedrich Gauss,1777—1855)在1805年将该算法用于天文学数据分析。作为一个完美主义者,高斯生前没来得及将这些结果发表,这种方法最终是在他去世后出版的论文集中被发现的。高斯1805年的笔记显示,他甚至早于傅里叶就开始了这方面的研究。现在回过头来看,这个算法称为高斯变换可能更合适!
傅里叶于1830年5月16日逝世。他的名字后来被刻在埃菲尔铁塔的侧面,以此表彰他的科学成就。
傅里叶动荡的一生几乎与工业革命的时期完全重合。在仅仅70年的时间里,古老的手工业被机器生产所取代。在这些变化中,一位英国人开始思考,机器除了能织布,是不是也能用来做计算。算术领域会不会发生一场工业革命?
[1] 阿基米德无法获得我们今天使用的正弦、余弦和正切三角函数的种种好处。内六边形的边长是 内角的一半等于圆心到边的圆心角。外六边形的边长是
[2] 二次函数型算法的形式为ax 2 +bx+c=0,其中a、b、c是已知常数(或称系数),x是待计算的未知数。
在过去的50年里,人类文明史上最明显和最鲜明的特点是,机械的应用使工业生产水平出现了惊人的提高,对旧工艺流程的改进以及新工艺流程的发明。
托马斯·亨利·赫胥黎(Thomas Henry Huxley)
《过去半个世纪的科学进步》,1887年
手动执行计算缓慢而枯燥。几千年来,发明家们一直在尝试设计能够加速计算的设备。第一个成功的产出是算盘。公元前2500年左右,苏美尔人发明了泥板算盘,这是从用鹅卵石计数和沙子书写演变而来的。后来,为了更快速地计算,他们在泥板表面蚀刻了线条和符号。珠轨算盘是在中国发明的,然后经由古罗马人在欧洲普及开来。
第一个机械计算器是在17世纪由法国人和德国人各自独立发明的。它由手动曲柄驱动,通过杠杆、轮齿和齿轮的运动来完成加法和减法运算。这种手工制作的复杂设备既昂贵又不可靠,大多数只是作为新奇物件卖给富人。
18世纪末和19世纪初发生了工业革命。工程师们设计出以蒸汽和水流为动力的机器,取代了传统的手工生产方式。手工生产向机器生产的过渡引发了生产力的迅速提高和重大的社会变革。劳动力从农村转移到城镇,在嘈杂、黑暗且危险的工厂里与机器一起劳作。
动力纺织机以固定的织法生产纺织物。1804年,法国纺织工兼商人约瑟夫·马里·查尔斯[Joseph Marie Charles,人称“雅卡尔”(Jacquard)]想出了一个颠覆性的重新设计。雅卡尔的织布机可以 被编程 (programmed),以生产不同织法的纺织物。这台机器能根据卡片上打孔而成的图案来织布。通过改变卡片上的打孔图案,可以产生不同的织法。一系列卡片被连在一起形成循环,这样机器就能重复织出程序设定的图案。
因此,到19世纪早期,欧洲已经有了手摇驱动的计算器和蒸汽驱动的可编程织布机。一位从小对机器着迷的英国数学家开始思考如何将这些概念结合起来。想来蒸汽驱动的可编程机器能比人类更快、更可靠地进行计算吧?他的想法几乎改变了世界。
查尔斯·巴贝奇(Charles Babbage,图3.1)于1791年出生在英国萨里郡的沃尔沃思。身为一个富有银行家的儿子,巴贝奇成为一名数学专业的学生。起初,他自学成才,18岁时被剑桥大学录取。一到那里,他就发现数学系相当古板,令人失望。巴贝奇是个任性的年轻人,他既不迎合考官,也不讨好潜在的雇主。尽管他是一位杰出的数学家,但毕业后却没能在学术界找到一份工作。在父亲的资助下,巴贝奇决心自己开展独立的数学研究。他搬到了伦敦,进入了首都的科学界,发表了一系列备受好评的论文。
科学论文——就像巴贝奇发表的那些——是研究的命脉。一篇论文是描述一个新想法的报告,它有实验结果或数学证明作为支撑,理想情况下两者兼有。科学依赖于证据,证明必须经过验证,实验必须是可重复的。论文由同领域的专家评审。只有最好的论文才会被发表。至关重要的是,论文中提出的观点必须新颖且是经过验证的。在期刊或会议上发表文章,可以向科学界有兴趣的各方传播新观点。发表一篇论文是一个学者职业生涯的里程碑,这表明他们在该领域具备了实力且站稳了脚跟。
图3.1 最早的程序员―查尔斯·巴贝奇(左,约1871年)和艾达·洛芙莱斯(右,1836年)[左图:从美国国会图书馆检索获取,www.loc.gov/item/2003680395/。右图:获取自英国政府艺术收藏中心,GAC 2172;玛格丽特·萨拉·卡彭特(Margaret Sarah Carpenter)作品:(奥古丝塔)艾达·金,洛芙莱斯伯爵夫人(1815―1852),数学家,拜伦勋爵之女]
在巴贝奇的年代,由于缺乏公共基金,只有少数几所大学和少数富有的科学爱好者能开展科学研究。科学论述常常发生在富人的沙龙里,甚至连“科学家”这个词都是新出现的。多年来,巴贝奇一直是维多利亚时代绅士科学家的典范。1828年,他最终被任命为剑桥大学卢卡斯数学教授。他能长时间艰苦地工作,这极大地放大了他原本就有的天赋。虽然他是一位颇有成就的数学家,但也许他的主要天赋在于发明机械设备。
基于他已发表的论文的诸多贡献,巴贝奇被选为英国皇家学会会士。他的职责之一是为英国皇家天文学会审核数学表格。这些表格列出了重要天文现象的预测时间和位置。海员广泛使用这些表格作为导航的辅助工具。由于手工计算很费力,这些表格常常包含错误。在无垠的大洋中,一个小错误就可能导致船只失事。
为了减轻计算的工作量,巴贝奇设计了一种蒸汽动力机械,可以自动计算和打印表格。十进制数字由轮齿、齿轮和杠杆的位置来表示。该引擎能够自动执行一系列计算、进行存储和重复使用中间结果。这台机器被设计成可执行单一的固定算法。因此,它缺乏可编程性。尽管如此,相比于以前的计算器,这种设计仍然算得上是一个重大进步,因为以前的计算器需要手动输入每一个数字和运算。巴贝奇制作了这种机器的一个小型工作模型。英国政府看到巴贝奇这个概念的价值后,同意资助建造巴贝奇差分机。
事实证明,制造差分机颇具挑战性。零件制造上的微小误差就会使机器变得不可靠。尽管政府不断投资,巴贝奇和他的助手杰克·克莱门特(Jack Clement)还是在完成了机器的一部分后就放弃了建造它。英国财政部在该项目上总共花掉了近1.75万英镑。这不是一笔小数目,用这笔钱足以从罗伯特·斯蒂芬森(Robert Stephenson)先生那里购买到22辆崭新的铁路机车。
尽管差分机项目失败了,巴贝奇仍然被自动计算的想法所吸引。他设计了一种新的、更先进的机器。分析机将是机械的,用蒸汽驱动,以十进制运算。它还是完全可编程的。这种新机器借鉴了雅卡尔的织布机,可以从打孔卡片上读取指令和数据。同样,结果也是通过打孔卡片呈现。分析机将成为第一台通用计算机。
巴贝奇再次向政府寻求资助。这一次,钱没有到手。分析机项目搁浅了。
巴贝奇在意大利都灵向一群数学家和工程师演示了分析机,那是他唯一一次关于分析机的公开演讲。路易吉·费德里科·梅纳布雷亚(Luigi Federico Menabrea)是与会者之一,他是一名军事工程师。他做了笔记,随后在巴贝奇的帮助下,发表了一篇关于该设备的论文。论文是用法文写的。巴贝奇的另一位支持者艾达·洛芙莱斯非常欣赏这篇文章,并决心将其翻译成英文。
艾达·洛芙莱斯[原名奥古丝塔·艾达·拜伦(Augusta Ada Byron)]生于1815年,是拜伦勋爵和拜伦夫人的女儿(图3.1)。拜伦夫人[安妮·伊莎贝拉·诺埃尔(Anne Isabella Noel),原姓米尔班克]本身就是一位数学家。她的丈夫拜伦勋爵至今仍被尊为英国最伟大的诗人之一。拜伦勋爵与夫人的婚姻只维持了一年,两人就分开了。拜伦夫人讲述了她丈夫的忧郁情绪和她受到的虐待。关于拜伦勋爵对婚姻不忠的谣言持续存在。这位诗人颜面扫地地离开了英国,再也没有见过他的女儿。
在母亲的要求下,洛芙莱斯从小就学习科学和数学。这些都是理性的学科,不会像诗歌和文学那样产生令人担忧的影响力。1833年,年仅17岁的她在一次社交聚会上结识了巴贝奇。当时,巴贝奇是个41岁的鳏夫,有四个孩子。他继承了父亲的财产,住在伦敦马里波恩区多塞特街1号的豪宅里,过着优渥的生活。巴贝奇家的晚宴是一个引人注目的场合,出席者是一个由上流社会人士、艺术家和科学家组成的群体,令人大开眼界。200多位名人聚集在一起在当时是很常见的。有位善于打趣的人说,光有财富是不足以获得邀请的。需要具备以下三个条件之一:“智力、美貌或地位”。
洛芙莱斯被巴贝奇的计算设备迷住了。在巴贝奇的邀请下,洛芙莱斯和她的母亲查看了差分机负责运行的部分。巴贝奇和艾达建立了友谊。他们定期通信,讨论分析机和其他科学话题。19岁时,艾达嫁给了威廉·金(William King),成为奥古丝塔·艾达·金,洛芙莱斯伯爵夫人。
艾达·洛芙莱斯不仅将梅纳布雷亚的论文翻译成了英文,还用7篇笔记内容将其扩展了一倍多。这篇论文题为《分析机概述》(Sketch of the Analytical Engine),是一篇颇具远见的文章。虽然分析机从未建成,但巴贝奇已经详细说明了这台设想中的机器可以执行的指令。这使巴贝奇和洛芙莱斯可以为这台尚不存在的计算机编写程序。
论文着重讨论了算法和与其等价的程序之间的关系。作者们阐述了算法是一种抽象的计算方法,在巴贝奇和洛芙莱斯的案例中,它被书写成数学方程式的序列。这篇论文在方程式(或称之为代数公式)表达的算法与编码在打孔卡片上的程序之间建立了等价关系:
这些卡片仅仅是对代数公式的转化,或者换一种更明确的说法,这是另一种形式的解析法。
数学方程的序列只能由人来完成。相反,打孔卡片上的指令可以由分析机高速自动执行。
洛芙莱斯在对这篇论文的增补中呈现了一系列以程序形式编码的数值算法。在没有分析机的情况下,测试程序的唯一方法就是手动执行,模仿计算机的动作。在论文的注释G中,洛芙莱斯写出了计算前5个伯努利数的程序的执行 追踪 (trace)。执行追踪列出了计算机会执行的指令,以及每一步之后得到的结果。洛芙莱斯不知道的是,她的执行追踪与古巴比伦人带有实例的算法展示遥相呼应。现代的程序员仍然使用执行追踪来更好地理解他们编写的程序的行为。
作者们很有预见性地指出了程序中可能出现的错误,或 程式错误 (bug):
就算实际的运行机制在工作过程中是正确的,卡片也可能会给它输入错误的指令。
讽刺的是,人们后来在论文中包含的一个程序列表中发现了一个错误:在应该是4的地方出现了3。这是第一个软件版本里的第一个程式错误。是此后许多同类问题的先祖!
论文还提出了计算机处理其他形式信息的设想,而不仅仅是处理数字:
它还可以作用于除数字以外的其他事物,这些事物之间的基本关系可以用抽象的运算科学概念来表达,而且还可以根据分析机的运算方法和分析机的工作机制加以调整。
换句话说,虽然分析机被设计用来执行算术运算,但所使用的符号可以代表其他形式的信息。此外,这台机器可以被编程或修改,以处理这些其他形式的数据。作者们知道它可以对代表字母、单词和逻辑值的符号进行运算。巴贝奇甚至折腾着通过编写程序来玩井字游戏和国际象棋。
巴贝奇、梅纳布雷亚和洛芙莱斯的精彩论文是一门新科学的第一缕曙光。把算法、程序设计和数据联系起来的科学,就是计算机的科学。又过了100年,这一领域才被承认并命名为计算机科学。
这是洛芙莱斯唯一的科学出版物。多年间,她的健康状况一直很差,年仅36岁便死于癌症。她和巴贝奇一直是好朋友,直到生命的最后。在她的要求下,她被葬在诺丁汉郡的哈克诺尔,与她早已疏远的父亲安葬在一起。
巴贝奇在他的余生中断断续续地研究分析机。 由于当时的机械制造技术存在缺陷,他的计划一次又一次地受挫。巴贝奇的分析机是又一次光荣的失败。
图3.2 计算机先驱艾伦·图灵,约20世纪30年代
尽管如此,巴贝奇还是没有停歇。他到处旅行。有一次,他下到维苏威火山里面,目的是勘察火山内部。他的著作涉及经济学、地质学、人寿保险和哲学等方面。除了设计各种计算机器外,他还是一个多产的发明家。他涉足政界,甚至参加过竞选。在他的晚年,巴贝奇因不被建制派认可而心怀愤懑。他参与了一场公开抨击伦敦街头音乐家的运动,他觉得那些人的刺耳声音令人难以忍受。在洛芙莱斯去世18年后,巴贝奇于1871年离世,他的机械数字计算机之梦也随之破灭。
事后看来,分析机明显具备了现代计算机的所有要素,仅一个要素除外:分析机是机械的,而不是电子的。商业化生产的电灯泡是托马斯·爱迪生在巴贝奇死后发明的。又过了50年才有人尝试制造可编程的电子计算机。巴贝奇留给计算机界的遗产是洛芙莱斯的论文。
没有可编程机器,就只能靠理论家来描绘算法和计算的未来。其中最具影响力的是艾伦·图灵(Alan Turing,图3.2)。
1912年,图灵出生于英国伦敦。由于他的父亲是殖民地的公务员,图灵的父母在他刚一岁的时候就返回了印度。图灵和他的兄弟留在了英国,由一位退役的陆军上校和他的妻子照顾。过了好几年,他们的母亲才回到英国与孩子们团聚。然而家人团聚的时间很短。13岁时,图灵被送进了寄宿学校。
在学校里,图灵和同班同学克里斯托弗·莫科姆成了好友。两人都对科学和数学有浓厚的兴趣。他们在课堂上来回传递纸条,讨论谜题和答案。图灵渐渐被莫科姆折服。不幸的是,莫科姆于1930年死于肺结核。图灵深受打击。
图灵的母亲埃塞尔·萨拉·图灵[Ethel Sara Turing,原姓斯托尼(Stoney)]在她的回忆录中满怀温情地回忆起她成年的儿子:
他有时会心不在焉、胡思乱想,沉浸在自己的思想中,偶尔会显得不好相处……有几回,他的羞怯使他显得极度无礼。
有些人不像图灵母亲那样同情图灵,而是认为他是一个不合群的人。他的一位讲师推测,正是图灵的孤僻以及他坚持从第一性原理出发思考问题,给他的工作注入了罕见的新颖度。也许是因为才华高绝,图灵不会轻易容忍蠢人。他还有一些古怪的习性,比如在泰迪熊波吉面前练习演讲,把杯子锁在暖气片上以防被偷。图灵很难相处,但他的许多同行都很喜欢他,这是种罕见的组合。
图灵获得了剑桥大学的奖学金,并取得了数学一级荣誉学位。在大学里继续深造的过程中,图灵在一篇杰出的科学论文中提出了三个重要的思想:他正式定义了算法;他定义了通用计算机必须具备的功能;他用这些定义证明了有些函数是不可计算的。令人惊奇的是,图灵在数字计算机问世之前就完成了所有这些工作。
图3.3 图灵机
图灵提出了一种想象的计算机,现在被称为图灵机,它由无限长的纸带、纸带带头、存储器和一组控制机器运行的指令组成。纸带被分成了无数个单元格。每个单元格只有够写下一个符号的空间。带头可以一次读取或写入一个正下方单元格里的符号。图灵机可以一个单元格一个单元格地来回移动纸带,它还可以在存储器中存储一个值。存储的值称为机器的当前 状态 (state)。
与机器相关联的是一组指令,它们控制机器的动作。指令的作用方式与现代计算机中指令的工作方式大不相同。在图灵机中,每条指令由1个前置条件和3个动作组成,如果前置条件满足,则执行动作。前置条件取决于机器的当前状态(存储器中的值)和当前位于带头下方的符号。如果当前状态和符号与前置条件中指定的值相匹配,则执行与前置条件相关联的动作。允许的动作如下:
1.针对带头正下方的符号,带头可以对符号进行替换、擦除或保持其不变。
2.纸带可以向左或向右移动一个单元格,也可以保持静止不动。
3.内存中的当前状态可以更新或保持不变。
图灵设想由人类程序员编写程序供机器执行。程序员将程序和输入数据提供给副手,由副手手动操作机器。以如今的眼光来看,很容易看出处理指令是如此简单直接,机械或电子设备可以取代人类操作员。操作员执行如下算法:
将输入值以符号的形式写在纸带上。
设置机器的初始状态。
重复以下步骤:
核对当前在带头下的符号。
核对机器的当前状态。
搜索指令以找到匹配的前置条件。
执行与匹配前提条件相关联的3个动作。
当存储器保持在指定的停止状态时,停止重复。
当图灵机停止运行时,结果可以显示在纸带上。
在现代人看来,图灵机似乎已经过时了,但它体现了计算机的所有必备功能——读取和写入数据、执行易于修改的指令、处理表示信息的符号、根据数据做出决定以及重复指令。图灵从没想过他的机器会被造出来。相反,图灵机一直被认为是计算机的一个抽象模型——一个能够促进计算理论发展的构想。
最重要的是,图灵机可以操作符号。人负责给这些符号赋予意义。这些符号可以被解读为代表数字、字母、逻辑(真/伪)值、颜色或无数其他量中的任何一个。
图灵机没有专门的算术指令(也就是加、减、乘、除)。算术运算是通过执行程序来实现的,这些程序处理纸带上的符号,从而达到算术运算的效果。例如,计算2加2是通过一个程序来完成的,该程序将纸带上的符号“2+2”替换为符号“4”。在现代计算机中,算术运算是内置的,以提高处理速度。
图灵认为他的机器足够灵活,可以执行任何算法。他的理念——如今已被广泛接受——具有两面性。它定义了什么是算法,什么是通用计算机。算法是图灵机可以通过编程来执行的一系列步骤。通用计算机是指能够执行程序的机器,且这些程序与图灵机所能执行的程序等同。
如今,通用计算机的标志是 图灵完备 (Turing complete)。换句话说,它可以模拟图灵机的运行。纸带符号当然可以用其他物理量代替,例如现代计算机中使用的电子电压电平。所有现代计算机都是图灵完备的。如果它们不是图灵完备的,那它们就不是通用计算机。
图灵机的一个基本特性是它能够检查数据并决定下一步执行什么操作。正是这种能力使计算机比自动计算器更高级。计算器不能做决定。它可以处理数据,但不能对数据做出响应。决策能力赋予了计算机执行算法的能力。
图灵用他假想的机器来帮助他解决可计算性中的一个经典问题:“所有的函数都能用算法计算吗?”函数接受输入并产生一个值作为输出。乘法是一个可计算的函数,这意味着有一个已知的算法来计算所有可能的输入值的乘法结果。图灵纠结的问题是:“所有函数都是可计算的吗?”
他证明了答案是否定的。有些函数是不能用算法计算的。他证明了一个特殊的函数是不可计算的。
是否有一个算法总是可以判断另一个算法即将终止?停机问题(halting problem)探讨的就是这个问题。停机问题展示出了编程中的一个实际困难。程序员如果犯了错误,很容易编写出某些步骤永远在重复的程序。这种情况被称为 无限循环 (infi nite loop)。通常,我们并不希望程序是不终止的。对于程序员来说,有一个检查程序是很有帮助的,它可以分析一个新编写的程序,并判断它是否包含任何无限循环。这样就可以避免执行无限循环。
图灵证明了不存在通用的检查算法。他的证明是基于一个悖论。关于悖论,说谎者悖论是一个很好的例子,它蕴含在如下声明中:
这句话是假的。
就像任何逻辑陈述那样,这个陈述可以是真的,也可以是假的。如果这个陈述是真的,那么我们必须得出这样的结论:“这句话是假的”。一个陈述不可能既是真的又是假的。这是自相矛盾的。或者换另一种情况,如果这个陈述是假的,那么我们必须得出这样的结论:“这句话不是假的”。这是另一个自相矛盾。由于两种可能性(真与假以及假与真)都是自相矛盾的,所以这种说法是一个悖论。
图灵用一个悖论来证明停机问题不存在解。基于悖论的证明方法如下:
取一个你想证明为假的陈述。
现在,假设这个陈述是真的。
在该假设基础上,建立逻辑线。
如果得出的结论是一个悖论,而且逻辑线是正确的,
那么这个假设肯定是无效的。
图灵的证明从如下假设开始:
解决停机问题的检查算法确实存在。
这种假定的检查算法能显示一个程序是否停止。如果被检查的程序停止运行,那么检查算法输出“停止”。否则,检查算法输出“不停止”。那么检查算法为:
以一个程序作为输入。
如果程序总是停止,
那么输出“停止”,
否则输出“不停止”。
接下来,图灵按照逻辑线进行推理。他首先创建了一个能运行检查算法,以检查检查算法本身的程序(图3.4):
重复以下步骤:
将检查算法作为输入,运行检查算法。
如果检查算法输出“不停止”,那么停止重复。
图3.4 图灵对停机问题的解答
程序对检查算法的输出进行检查。如果检查算法输出“不停止”,那么循环终止,程序停止。如果检查算法输出“停止”,那么程序将无限次重复因而不会停止。然而,检查算法检查的是算法自己。因此,只有当检查算法没有停止时,检查算法才会停止。相反,如果检查算法停止,检查算法就不会停止。这两种结果都是自相矛盾的。这是一个悖论。
既然推理的逻辑线是正确的,那么最开始的假设一定是无效的。这意味着解决停机问题的检查算法不可能存在。停机问题是不可计算的。对于有些函数,即使有了完整的认识,也是无法计算的。计算是有限度的。
好消息是,许多有用的函数(从输入值映射到输出值)都是可计算的。困难在于如何提出有效的算法来执行所需的映射。
1936年,图灵前往普林斯顿大学攻读博士学位。文学学士学位或理学学士学位涉及一系列授课课程和一系列笔试,而更高级的哲学博士学位则涵盖一个完整的研究项目。博士学位的最终阶段是提交博士论文和一场激烈的口头答辩。能否授予博士学位取决于候选人是否提出一项有证据支持的新工作,证据可以是实验上的,也可以是数学上的。图灵的博士学位由美国数学家和逻辑学家阿朗佐·丘奇(Alonzo Church)指导,他主要研究计算的理论问题。
1938年,图灵回到剑桥大学。1939年9月4日,也就是英国对纳粹德国宣战的第二天,图灵加入了位于布莱奇利园的政府编码与密码学校。代号为“X站”的布莱奇利园是英国战时最高机密的密码破译中心。
根据从一个波兰组织获得的情报,图灵和戈登·韦尔什曼(Gordon Welchman)开发了一台特殊用途的计算机,以协助破解德国的恩尼格玛密码。“炸弹”(The Bombe)破译机是一种机电计算装置,于1940年建成。虽然“炸弹”破译机可以进行重新配置,但它不是可编程的。与同时代的其他设备一样,它只能执行固定的算法。“炸弹”破译机协助研究小组破译了从德国潜艇截获的无线电通信信息。英国海军靠收集到的情报能够确定德国U型潜艇的位置,并提前警告盟军船只即将受到攻击。这直接使许多盟军海员的生命得以保全。图灵被授予大英帝国勋章,以表彰他在战时的贡献。他高级机密工作的细节没有被披露。
战后,X站被解散了。图灵加入了位于伦敦的国家物理实验室(National Physical Laboratory,NPL),在那里他加入了一个设计通用电子计算机的项目。由于任务很难,而且图灵不善于与他人合作,项目进展缓慢。沮丧的图灵离开了国家物理实验室,回到了剑桥,然后在曼彻斯特大学找了个工作。曼彻斯特大学一直在加紧研制自己的电子计算机。
在他的职业生涯中,图灵一直在思考计算机的前景,最终他得到了一台计算机。他开始为曼彻斯特大学的这台计算机编程,并编写了一份使用手册。他撰写了一系列关于计算机可能的应用前景的科学论文。他提出,计算机可以预测分子在生物系统中的行为,这为现代生物信息学埋下了伏笔。他认为计算机可以解决迄今为止需要人类智能才能解决的问题。他还推测,到2000年,人类询问者将不可能辨别出与其交流的文字信息是来自人类还是计算机。至今还没有计算机能通过这个所谓的人工智能图灵测试。
1952年,图灵报告说他的家被盗了。他告诉警察,他的一个朋友阿诺德·默里(Arnold Murray)认识这个窃贼。在警方的追问下,图灵承认了他和默里的同性恋关系。图灵被指控犯有“严重猥亵罪”。法院判决图灵接受激素“疗法”——化学阉割的委婉说法。图灵此前是一名狂热的业余运动员和马拉松运动员,这种“疗法”似乎对他的健康产生了负面影响。
两年后,年仅41岁的图灵被发现死在自己的床上。毒理学测试表明他的死因是氰化物中毒。验尸官判定图灵死于自杀。许多人质疑这一结论。没有找到任何遗书。图灵的床边被发现有一个吃了一半的苹果,但它从未被检测是否含有氰化物。 他的朋友们做证说他死前几天精神很好。一些人认为,图灵是被英国特工暗杀的,他们想要防止图灵泄露战时机密。这种猜测看起来牵强附会。图灵习惯于在家开展化学实验。他的死亡很可能只是一场意外。
X站发生的事情直到20世纪70年代才被公开。就连在那里工作的人们的家人也不知道他们在布莱奇利园取得了什么成就。2013年,英国女王伊丽莎白二世赦免了图灵的同性恋“罪行”。
图灵对计算机科学的贡献是巨大的。他定义了什么是计算机和算法,他给计算设定了界限,他的图灵机仍然是所有计算机比较的基准,通过图灵测试已经成为人工智能一直以来的目标之一。然而,比他的发明更重要的是他那些散布在一篇篇论文中的零散想法。那些看似漫不经心的思考为后来追随他脚步的人开辟了未来探索的道路。为了表彰他的成就,计算机科学界的最高荣誉被命名为ACM图灵奖(简称图灵奖)。每年100万美元的奖金由美国计算机协会(Association for Computing Machinery,ACM)提供,以表彰“具有持久且重大技术价值”的贡献。
当图灵在布莱奇利园忙着破解恩尼格玛密码时,其他地方也在开发可编程的电子(为主体的)计算机。在柏林,德国工程师康拉德·楚泽(Konrad Zuse)建造了一系列基于继电器的机电计算设备。可编程且全自动的Z3计算机于1941年建造完成。虽然Z3不是图灵完备的,但它包含了许多高级功能,其他地方的研究者后来也发明了这些功能。 战争严重地阻碍了楚泽的工作。缺乏零部件、有限的资金和空中轰炸都拖慢了Z系列计算机的研发。到1945年,楚泽的工作基本无法推进了。图灵完备Z4计算机的开发也陷入注定的停滞状态。直到1949年,楚泽才重新成立了一家公司来生产他的设备。Z4计算机最终于1950年交付给苏黎世联邦理工学院。楚泽的公司在被德国电子产业巨头西门子收购之前生产了200多台计算机。
而在美国,第二次世界大战对初代计算机的研发是一个福音。受到巴贝奇差分机示范模型的启发,霍华德·艾肯(Howard Aiken)在哈佛大学设计出了一台电子计算机。这台名为“哈佛马克1号”的计算机(又名自动化循序控制计算器)由IBM公司资助和承建,于1944年交付。这台机器是完全可编程的和自动化的,可以在没有干预的情况下连续多日运行。然而,“哈佛马克1号”缺乏决策能力,因此不是图灵完备的,所以它不算一台通用计算机。
世界上第一台可操作的数字通用计算机在美国宾夕法尼亚州建成。这台机器由美国陆军提供资金,具有明确的军事用途,于1946年向媒体公开。这是算法发展革命的开始。