第十四讲 计算机

1.机械计算器

现代的电子计算机是多条“科技树”的会聚，我们不妨先从计算器的历史讲起。除了安提基西拉机器等个别例外，西方的辅助计算器械是在17世纪发展起来的

提出对数概念的数学家纳皮尔在1617年发明了纳皮尔骨筹（Napier‘s bones）（图14.1），通过旋转和移动一组刻有数字骨棒，可以辅助进行乘法、除法、开方等运算。后来人们加以改进，把零散的骨棒封装在盒子里（图14.2），成为一个辅助计算的装置。

所谓运筹帷幄，中国古代数学家一般是用竹制算筹来辅助进行复杂计算的，宋代以后又有了珠算算盘来辅助计算。筹算也可以进行诸如开方、解方程等复杂运算，但中国数学家各有精妙的口诀和技艺传承，但没有想到把计算工具进一步封装成一套傻瓜化的装置。

第一个傻瓜化操作的计算机器大概是帕斯卡（1623-1662）发明的加法器（图14.3），加法器只能计算加减法，但妙处在于通过内部的齿轮联动装置（图14.4）实现自动进位，加法时不需要用“三下五除二”之类的口诀来关注进位问题，加几只需要在相应数位上旋转几格即可。

帕斯卡发明加法器时年仅19岁，当时在1639年诺曼底赤脚党起义之后，虽然被很快镇压，但在起义军杀税吏、焚税局之后，税务系统完全瘫痪。帕斯卡的父亲当时被指派去收拾烂摊子，整理了几年都看不到尽头，年轻的帕斯卡就发明了这台加法机器，给父亲分忧。这个发明得到了法国国王的嘉奖，在当时制造了数十台。

要加入乘法运算，就需要德国哲学家莱布尼茨在1673年提供的关键设计，他发明了“莱布尼茨轮”（图14.5）这样一种独特的齿轮转筒结构，实现了乘除法的机械化。设定乘数之后不断摇动手柄，最终停止时就会得出结果。

莱布尼茨自己设计并制造了两台模型机（图14.6），但因加工精度问题未能实用。但之后的机械计算器都参考了莱布尼茨轮的装置。

帕斯卡和莱布尼茨完成了机械计算器的核心原理，接下来就需要等加工工艺更精密、更标准化，才能让机械计算器实用化。

第一个成功商业化的计算器是1820年取得专利的四则运算器（Arithmometer）（图14.7），在最初的设计中包含3个莱布尼茨轮，用皮带抽拉来运转（图14.8）。它在1851-1915销售，由于相对小巧，价格适中，风靡一时，也带动了整个机械计算器产业，其它公司争相效仿。一直到20世纪中叶，不同款式的机械计算器各领风骚（图14.9），成为数理研究者的必备。

机械计算器的最高成就，应该是巴贝奇的差分机与分析机了。巴贝奇在1822年设计了他的第一台差分机（图14.10）。除了四则运算外，差分机可以进行多项式计算，解方程。巴贝奇为差分机设计了两个版本并申请到经费资助，但最后并未真正完成，不过有其他制造商根据巴贝奇的思想做出了一台机器（图14.11）并在1855年的巴黎世博会展出。

1991年伦敦科学博物馆根据巴贝奇的文献，用巴贝奇同时代的加工精度，制造出了差分机1号和2号（图14.12），证明了巴贝奇本人设计的有效性。

尚未完成差分机，巴贝奇就转向了另一项宏伟的计划，那就是“分析机”的制造。他从1834起提出了分析机的设想（图14.13），这是现代通用计算机的前身。分析机可以通过“打孔卡片”（图14.14）来制定“程序”，完成复杂的运算。这种打孔卡片的灵感可能来自于当时在纺织业流行的雅卡尔提花机所使用的打孔卡片（用于预先编制织物花案）。打孔卡片的形式在后来被沿用，成为各种早期计算机的输入媒介。

现代科学史家认为，分析机是“图灵完备”的，也就是说，它理论上能够完成任何现代计算机能够进行的计算，当然，运算时间远远比不上电子计算机了，例如进行两个20位数的相乘大概就需要3分钟的时间。

但“分析机”也并未实际完成，至今也未有后人建成，只有一些局部结构或模型被制作出来（图14.15）。有一个2011年启动的项目，号称要在2021年纪念巴贝奇逝世150周年前建成分析机。

分析机虽未实现，但已经有人为它编写程序了。那就是“第一位程序员”，艾达（Ada Lovelace，1815-1852）（图14.16）。

艾达是诗人拜伦的女儿，她出生后不久母亲就与拜伦离婚，因为母亲怨恨拜伦，不希望女儿学拜伦的样子，不注重文学教育，反而培养她从小学习数学。不过艾达还是受到了父亲的影响，长大后自称自己追求“诗意科学”（poetical science）。

1833年艾达在社交活动中遇见了侃侃而谈的巴贝奇，为他描绘的差分机吸引，从此保持通信。接触到分析机的思想后，艾达帮忙翻译扩散，同时附加了自己的许多笔记。在这些笔记中，包含有为构想中的机器编制的第一个程序（计算伯努利数）（图14.17）。

当然，艾达“第一位程序员”的名号是有争议的，因为这些编程思想显然来自巴贝奇本人，巴贝奇在设计机器时，肯定也构想过运算程序。但艾达确实想到了某些比巴贝奇更多的东西，那就是分析机的潜力。巴贝奇始终只是把分析机当作一台数学工具，而艾达认为其意义远不限于数学，她认为诸如诗歌和音乐等任何事物也都可以成为分析机的计算对象。

2.二战与现代计算机

巴贝奇的设想太过超前，在当时并没有市场需求，而且完全依靠机械齿轮的计算机成本高、能耗大、速度慢，即便建成也未必找得到用武之地。

对计算机的需求是在20世纪的两次世界大战中浮现出来的，特别是第二次世界大战，直接促成了现代电子计算机的产生。

首先是在无线电报成熟之后，军队普遍通过无线电传达情报和指令。但由于无线电信号是开放的，容易被敌军捕捉，这就促生了“密码学”的发展。

德国人仰仗精密的恩尼格码密码机（图14.18）传递军事讯息，信息被密码机自动转换成加密编码后发出，接收方也需要用密码机来解码才能够读懂信息。同盟国在努力破解德国的密码技术时，需要大量的自动化计算，这就推动了计算机的发展。

其次，世界大战展现出现代科技的狰狞面相，最先进的科学和技术被用于大规模屠杀人类的武器，改变了战争的面貌。

古代战争是在平面上打的，军队从地面上推进。近代有了火炮等高科技的远程武器，但人们也可以预先把不同仰角与射程对应好，炮兵估测完敌军的距离，就可以迅速调整火炮进行轰击。

但在一战时，飞机的参战改变了战争的形式，在二战时，飞机进一步普及，高空成为最关键的战场之一，再加上德国在1939年率先发明了导弹，使得战争立体化、复杂化。

理论上讲，高射火炮仍然可以打到飞机、拦截导弹，根据牛顿力学足以计算出正确的弹道。但问题是，计算的速度跟不上了。如果还依赖士兵用望远镜估测敌军方位，然后再回过头来计算抛物线，算完之后再人工指挥调整火炮，导弹早就炸到头上了。

雷达的发明大大强化了索敌的范围，但更关键的问题是必须要在“索敌—计算—发射”这三个环节都实现自动化，这就要求机器能够在短时间内汇总并计算复杂的数据，并且能够有效控制各种武器作出即时反应。

维纳就是在二战期间加入了美国军方的研究项目，战后提出了“控制论”的思想。他认为，机械和生物一样，都需要控制其机体和环境，而所谓控制，无非就是输入和输出信号的交互过程，“通信”不仅是人与人之间的外在活动，更是任何生物体或机械的内在的存在方式。维纳把机器控制的问题转化为信息处理的问题，并且提出了类似“人工智能”的概念，他认为将来机器会要求我们像理解人那样理解它们。

最后，还有原子弹这样的大型研发工程，要求海量的计算，也推动了对计算机的需求。

在上述新环境、新需求下，电子计算机就应运而生了。

最早发展起来的是所谓“机电计算机”，它们并未使用真空电子管，而是采用电路控制的机械继电器作为逻辑单元，虽然依靠电力但本质上还是由无数机械开关进行控制。

1941年，德国人制造的Z3（图14.19）是世界上第一台实用的可编程的全自动数字计算机，包含2000个继电器。但因为经费不足而没有发挥作用，后被炸毁。

盟军在1943年建造的巨像计算机（图14.20）在二战中发挥了作用，它是为了破解德军的洛伦兹密码机（比恩尼格码密码机更高端，专用于指挥系统）而打造的。巨像计算机是第一台全电子的计算机，使用了真空管作为逻辑单元，但它不是图灵完备的，只能通过面板上的数十个开关进行有限的“编程”，数据则通过打孔纸带输入。

1944年的哈佛马克I号（图14.21）是受到分析机影响的机电计算机，用途广泛（但也不是图灵完备的），冯·诺依曼曾借用它为曼哈顿计划提供协助。

我们熟悉的ENIAC（图14.22）是第一台通用的（图灵完备的）全电子的计算机，全称叫电子数字积分计算机。由美国军方赞助，从1945年开始运行，主要用于弹道计算，也参与过核武研发。

同年，冯·诺依曼提出“存储程序通用电子计算机方案”，确立了现代计算机的“冯·诺依曼结构”，即运算器、控制器、存储器、输入设备、输出设备。奠定了电子计算机的基础。

3.图灵机

上文一直都没有明确解释究竟何谓“图灵完备”，那么究竟图灵完备或图灵机是什么意思呢？电子计算机不只是机械工艺和电子科学的集大成之作，同时更凝聚了数学和哲学领域的思想成就。所谓“图灵机”其实是一个纯粹数学的概念。但由于这一数学概念不太容易理解，所以我放到最后才略加说明，觉得枯燥的读者可以直接跳过。

之前提到，布尔的逻辑代数影响了计算机的发明，逻辑代数把逻辑理解为代数运算，用数值0和1代表“假”与“真”。后来，弗雷格提出“概念文字”，构建公理化的形式语言系统。包含是、非、有、无、与、或之类范畴的逻辑命题，全都可以被符号化而翻译为各种“等式”，并通过少数几条公理推演出这些命题的对错。

设计一个形式语言系统，需要包括以下几点：有限的符号集、语法规则、若干公理和演算规则。对于一个形式系统来说，有“一致性”和“完备性”两项大要求。所谓一致性，是要求这个体系不能推演出相互矛盾的两条命题，而所谓完备性，是指任何一条合乎语法规则的命题，都应该能够从公理中推演出来要么为真要么为假。

弗雷克发展起来的“一阶逻辑”系统同时符合一致性和完备性的要求，随后逻辑主义者希望更进一步，把整个数学的大厦建立在形式逻辑之上。通过集合论的语言，数学命题也被还原为一个形式系统，那么这个形式系统是一致且完备的吗？

学者们开始了构建和证明，但屡屡受挫，罗素悖论让人们开始恐慌，而哥德尔最终给出致命一击：著名的“哥德尔不完备性定理”，证明了只要一套形式语言系统包含整个自然数及其四则运算的系统，那么它要么是不一致的，要么是不完备的。

哥德尔的证明使用了一个巧妙的办法，即“哥德尔编码”，他把形式系统中的（有限的）每一个符号依次对应于一个自然数，比如“=”=5，“0”=6，“（”=8、“）”=9等等。然后每一个由符号组成的语句就翻译为一系列数字的排列，比如其第1个符号是3，第二个符号是7，第三个符号是5……然后再把自然数中所有素数排列起来，第1个素数是2，第二个素数是3，第三个素数是5等等。最后，我们把每一个素数都乘以它所对应位置的符号数的幂次，再一并乘起来，就得到了一个“哥德尔数”。

举例来说，“0=0”这样一个等式，包含3个符号，第1个是0，对应于6；第2个是=，对应于5；第3个还是0，对应于6。那么我们找到第1、2、3个素数（2、3、5），对应乘幂，就得到：

26×35×56=243000000

这样一来，形式系统中的每一条语句，都一定能对应为一个自然数（比如243000000），而不同的语句所对应的一定是不同的自然数。

在这套编码的巧妙之处在于，只要形式语言系统包含自然数系统，那么这个语言中的每一语句所对应的自然数同时也属于这一语言内部。最后，哥德尔构造了一个巧妙的自我嵌套，证明了完备性必将导致不一致。

我这里当然不再深入展开哥德尔的论证，但之所以讲到这里，是因为这正是图灵机的直接来源。

图灵在1936年发表了论文“论可计算数及其在判定问题上的应用”，基于哥德尔的论证展开讨论，重新定义了计算概念。

在形式语言中，“证明”其实就变成了“计算”，完备性指的实质上就是这一系统内部的每一合法命题都是可计算的。但问题是，究竟什么是“计算”呢？

人类在论证或计算时，经常会思维跳跃，比如“显然”、“易证”、“同理”、“综上可知”等等，都是人类们常用的词汇了。但是，一个严谨的计算或论证，显然不应包含这些暧昧的过程，而是每一步之间都应该刻板、机械地进行。

图灵认为，机械计算就是让机器自动就能够进行的计算，于是，图灵设计了一台虚拟机器，即“图灵机”，把可计算性定义为“可被图灵机计算”。

这台机器试图模仿人类在进行计算时的思维方式，但又排除了人类思维的暧昧性。图灵认为，人在计算时，思维是线性的，每一阶段只盯着有限的一小块事情，然后在阶段性计算之后转向另一块东西，在每一阶段的行为，只取决于两个方面，一是个别被注意的符号，二是一定的心灵状态。

因为计算过程是线性的，我们可以把计算的对象和计算的结果统统都写到一张一维的纸条上。由于所有符号都可以被编码为自然数，所以这张纸条上有且仅有数字，换成2进制的话就是一条只有0或1的纸条。理想的图灵机包含一条无限长的纸带。（图14.23）

每一个时刻有且仅有一个纸条上的位置被注意，机器首先读取这一位置的数字，然后进过计算，决定在这个位置上写下另一个数字（或不变），然后就转向另一个位置（左移或右移），切换成另一个心灵状态（或不变）。

而所谓心灵状态，包括可以用几个四元数组组成：“读—写—转—切”，如（1, 1, -1, 3）表示：若读取到1，则仍写下1，然后退后1格，切换到第3种心灵状态再继续读取。（0, 1, 0, 0）则表示如果读取到的是0，则擦掉改写成1，然后停止不动，完成计算。

一系列有限的心灵状态就构成了一种计算程序。要注意，这些四元数组仍然可以全部编码为数字，写在一条纸带上。

这样一来，图灵也完成了一个巧妙的嵌套，因为写着程序的纸带也可以随时变成作为数据的纸带，同一串数字X，既可以用作程序，也可以用作数据。那么我们就可能通过“程序X”来计算“数据X”，

图灵把完备性问题被转换为“停机问题”，也就是说，当我们用任意程序X去计算任意数据Y的时候，能否预先判定它是否会“停机”（得出最终结果）？借助形如“X计算X”的自相嵌套，图灵巧妙地论证了停机问题无解。

在这一深奥而巧妙的数学证明中，建构的计算机器，正是后来电子计算机的理论原型。当我们说一台机器或一套语言是“图灵完备”的，那就是说它给出的计算完全等价于这个“图灵机”，一台图灵完备的计算机算出什么结果，图灵机也应当算出同样的结果，反之亦然。（更准确地说，实际的电子计算机都是阉割版的图灵机，因为不存在“无限长的纸带”，计算机只有有限的内存。）

我在这里讲那么多，并不想做数学史的科普，关键在于，从哥德尔到图灵，他们把信息时代的精神推演到极致——打破实体和信息的界限。机器、程序和数据三位一体，本质上都是数字。在机械计算器的时代，“用计算器计算计算器”是神经错乱的说法，但现在，用程序编写程序早已是家常便饭。

在古代人眼中，面和体都是不能放在一起计算的，诸如x3+x2=x这样的算式都是不可理解的。但在信息时代，所有的边界的消融于数字之间。