计算机科学发展史
by
张可
摘要
本文准主要介绍计算机这门学科的理论发展史，从计算机理论模型的设想开始到通用计算机的实现，以及关于下一代计算机的思考。笔者一直认为不管是学习什么学科，其发展史都是非常有必要的，只有了解了这个学科从零开始发展到现在的过程，才能对整体有更深刻的理解。另外本文也不会涉及太多硬件方面迭代发展的描述。
引言
我们都知道现代通用计算机的理论计算模型是图灵机，图灵被称为计算机之父，关于图灵本人也流传了很多故事，比如二战时期发明解码机破解了德军的通讯密码，这还被拍成了电影《模仿游戏》；还有他关于对人工智能的定义，能通过图灵测试的才算是真正的人工智能；以及他由于性取向问题导致最终咬了一口带毒的苹果而自杀，甚至传言 Apple 的 Logo 就源于此。
而直到 2013 年英国女王才宣布赦免早已去世的图灵，据说 2021 年英国的 50 英镑钞票上将会印上图灵的照片。但实际上图灵机最初发明的目的跟计算机并没有任何关系，只是为了解决一个困扰当时数学家们很久的一个问题：希尔伯特的判定问题。
莱布尼茨之梦
这一切可以追溯到十七世纪的莱布尼兹，先引用一段百科上对他的介绍。
戈特弗里德·威廉·莱布尼茨（德语：Gottfried Wilhelm (von) Leibniz，1646年7月1日－1716年11月14日），德意志哲学家、数学家，历史上少见的通才，获誉为十七世纪的亚里士多德。他本人是律师，经常往返于各大城镇；他许多的公式都是在颠簸的马车上完成的，他也自称具有男爵的贵族身份。 莱布尼茨在数学史和哲学史上都占有重要地位。在数学上，他和牛顿先后独立发明了微积分，而且他所使用的微积分的数学符号被更广泛的使用，莱布尼茨所发明的符号被普遍认为更综合，适用范围更加广泛。莱布尼茨还对二进制的发展做出了贡献。
莱布尼兹在很多学科都有所建树，最广为人知的是发明了数学工具微积分，不过关于微积分的发明者一直存在争议，大部分人可能认为是牛顿，但实际上是他和莱布尼兹几乎同时发明点的，而且莱布尼兹更早于牛顿发表微积分论文。
值得一提的是，二进制系统也是莱布尼兹在 1679 年设计的，并在他 1703 年发表的文章《论只使用符号0和1的二进制算术，兼论其用途及它赋予伏羲所使用的古老图形的意义》出现。
当然这些并不是本文重点，莱布尼兹所在的时代还没有计算机的概念，但天才莱布尼兹却一直有一个梦想。
他梦想对一种普遍的人工数学语言和演算规则进行一种百科全书式的汇编，知识的任何一个方面都可以用这种数学语言表达出来，而演算规则将揭示这些命题之间所有的逻辑关系。
精炼我们的推理的唯一方式是使它们同数学一样切实，这样我们能一眼就找出我们的错误，并且在人们有争议的时候，我们可以简单的说，让我们计算“calculemus”，而无须进一步的忙乱，就能看出谁是正确的。—— 《发现的艺术》1685, W 51
莱布尼兹的这个构想很容易让人联想到符号逻辑或者叫数理逻辑或者像编程语言？本质上仍然是亚里士多德的逻辑学，只不过使用了抽象代数的方式来记述。但莱布尼兹虽然对这个构想有这狂热的热情但实际上他对此并没有太多的研究，而符号逻辑也是后来经过戈特洛布·弗雷格以及伯特兰·罗素等人才逐渐完善。
事实上莱布尼兹的一生并不算是顺风顺水，迫于生计，他只能一边帮着汉诺威的公爵们编写他们的家族史一边开展自己的研究，如果他能像牛顿一样没有生活压力的拖累，或许他能在符号逻辑方面大放异彩。
从亚里士多德时代一直到莱布尼兹，逻辑学还是以自然语言的形式叙述，虽然莱布尼兹并没有在符号逻辑上做出太多贡献，也没有改变这一个局面，但至少他再原有的基础上提出了关于下一代发展的思考。
对于科学的发展我一直抱着相当乐观的态度，科学的车轮滚滚向前，这是自然的规律，莱布尼兹只需要提出这个想法就够了，以后会有更多优秀的数学家们来实现他的梦想。
乔治布尔-逻辑与数学的桥梁
几乎每个强类型编程语言的基本数据类型都有布尔类型，布尔类型用于表示逻辑运算中的基本类型：真假值。当然布尔逻辑运算的发明者就是乔治布尔。
乔治·布尔（英语：George Boole，1815年11月2日－1864年12月8日），英格兰数学家和哲学家，数理逻辑学先驱。
布尔致力于推动莱布尼兹构想的发展，他试图将亚里士多德的三段论与代数相结合，只要找到转换方程式，那逻辑就可以像代数一样进行运算，而逻辑学也将成为数学的一个分支。
首先，布尔认为可以将代数中的加法、乘法与逻辑中的与或结合起来，他将逻辑推理中一些用于表示个体或者集合的占有特殊地位的名词表示为类（class），例如一个杯子的类，一条鲸鱼的类。
现在用字母来表示类，如果字母 x 和 y 表示两种特定的类，那么布尔就说，xy 表示既在 x 中又在 y 中的事物的类。那么 xx = x 则总是为真。
在 x 表示一个数的普通代数中，什么时候方程 x² = x 为真？答案很显然：仅当 x 为 0 或 1 时方程才为真。于是布尔得出了一条原理：如果只限于 0 和 1 两个值，那么逻辑代数就成了普通代数。
至此布尔完美的解决了这个问题，他的研究成果成了逻辑学与数学的桥梁，一劳永逸的证明了逻辑演绎可以是数学的一个分支。
弗雷格-数理逻辑奠基人
弗里德里希·路德维希·戈特洛布·弗雷格（德语：Friedrich Ludwig Gottlob Frege，1848年11月8日－1925年7月26日），著名德国数学家、逻辑学家和哲学家。是数理逻辑和分析哲学的奠基人。
弗雷格被公认为伟大的逻辑学家，如同亚里士多德，哥德尔，塔尔斯基。他于 1879 年出版的不到 100 页《概念文字》（Begriffsschrift）标志着逻辑学史的转折。《概念文字》开辟了新的领域。
Begriffsschrift 一词由弗雷格从德文词“Begriff” （概念）和“Schrift”（大致为“文字”或“书写方式”之意）拼接而成。其副标题是：“一种模仿算术语言构造的纯思维的形式语言”。这部著作被誉为“也许是自古以来最重要的一部逻辑学著作”。
概念文字实际上是一种逻辑语言，所以从这个观点看，概念文字是我们今天使用的所有计算机程序设计语言的前身。书中先确定了基本概念和标号（sign），象命题（”断定／判断”），和全称量词（”普遍性”），蕴涵（”条件性”），否定和等号；然后他声明了九个形式化的命题作为公理（它们是在语义上证明了的形式化陈述）以及在语法上证明了一百多个形式陈述。
所以概念文字实际上是弗雷格在借鉴了传统逻辑自然语言与算术的形式语言创造出来的，奠定了逻辑学日后发展的基础。
到了这里逻辑学已经发展的非常成熟了，逻辑学家们可以通过逻辑符号语言进行逻辑演绎，从形式上来说，这距离莱布尼兹之梦只差一步之遥，但此时罗素的一封信却几乎将弗雷格的毕生研究毁为一旦，他也再也没有从这个打击中恢复过来。
罗素在信中指出，用集合的集合进行推理很容易导致矛盾。罗素的悖论可以这样来说明：如果一个集合是它自身的一个成员，那么就把这个集合称为异常的；否则就称它为正常的。如果把所有正常集合所组成的集合记为 ε，那么ε是正常的还是异常的？答案必定非此即彼。但情况似乎并非如此。ε 是正常的吗？如果 ε 是正常的，那么由于 ε 是由所有正常集合所组成的集合，它就将属于自身。而这恰恰说明它是异常的。如此一来，ε 就只能是异常的了。可是，由于它是由所有正常集合所组成的集合，所以它将不属于自身。而这恰恰又使它成为正常的！无论哪个结果都导致了矛盾！对于可怜的弗雷格来说，这一矛盾表明他的体系所基于的那些前提是靠不住的。
希尔伯特的问题
我们必须知道 我们必将知道
这是大卫丶希尔伯特 1930 年退休时的结束语，这句话被篆刻哥廷根城市墓地里他的墓碑上面。
这句话代表着人类对知识最纯粹的渴望和追求，即使此时的哥德尔已经证明了希尔伯特计划的失败，即使有些问题永远也无法被证明，但人类永远也不会停下迈向真理的脚步。
大卫·希尔伯特（David Hilbert，1862年1月23日－1943年2月14日），德国数学家，是19世纪末和20世纪前期最具影响力的数学家之一。希尔伯特1862年出生于哥尼斯堡（今俄罗斯加里宁格勒），因发明了大量的思想观念（例如不变量理论、公理化几何、希尔伯特空间）而被尊为伟大的数学家。
1900 年，希尔伯特在巴黎的国际数学家大会上作了题为《数学问题》的演讲，提出了 23 道最重要的数学问题，这就是著名的希尔伯特的 23 个问题，也是留给新世纪数学家们的挑战，这些问题中与图灵机相关的主要是下面三个：
- 数学是完备的吗？也就是说，面对那些正确的数学陈述，我们是否总能找出一个证明？数学真理是否总能被证明？
- 数学是一致的吗？也就是说，数学是否前后一致，不会得出某个数学陈述又对又不对的结论？数学是否没有内部矛盾？
- 数学是可判定的吗？也就是说，能够找到一种方法，仅仅通过机械化的计算，就能判定某个数学陈述是对是错？数学证明能否机械化？
希尔伯特希望通过这些问题建立起数学安全坚实的地基，一劳永逸地解决所有关于对数学可靠性的种种疑问，这被称为“希尔伯特计划”，可事实并没有按照希尔伯特的预期发展，这个野心勃勃的计划即将被一个名不见经传的年轻数学家哥德尔浇灭。
哥德尔不完备定理
1993 年 8 月，哥德尔协会在捷克共和国的布尔诺召开会议，纪念哥德尔诞辰87周年。除了既定的科学议程之外，这次会议还特地举行了一个纪念仪式，由布尔诺的市政要人在哥德尔童年时的故居安放纪念牌匾。我仍清楚地记得那时的情景：我们打着伞，站在初秋时节略有些寒意的细雨中；开始是一些捷克语的演讲，随后，一支身着色彩艳丽的民族服装的乐队演奏了几首曲子。——节选自《逻辑的引擎》
故事发展到这里，魔鬼般的自指已经不止一次出现在各种悖论中，数学大厦的根基似乎开始摇摇欲坠。关于哥德尔的一些理论侯世达的《哥德尔、埃舍尔、巴赫：集异璧之大成》书中有很详细的介绍，并且在更高层次上分析了同一种理论如何通过哥德尔、埃舍尔、巴赫在三个不同领域中折射出自己的色彩，很棒的一本书。
库尔特·弗雷德里希·哥德尔（Kurt Friedrich Gödel，1906年4月28日－1978年1月14日），出生于奥匈帝国的数学家、逻辑学家和哲学家，维也纳学派（维也纳小组）的成员。哥德尔是二十世纪最伟大的逻辑学家之一，其最杰出的贡献是哥德尔不完备定理和连续统假设的相对协调性证明。
1931 年哥德尔发表哥德尔不完备定理，定理包含两个部分：
- 任何自洽的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中不能被证明的真命题，因此通过推理演绎不能得到所有真命题（即体系是不完备的）。
- 任何逻辑自洽的形式系统，只要蕴涵皮亚诺算术公理，它就不能用于证明其本身的自洽性。
这回答了希尔伯特的前两个问题，基本算数系统是不完备的，存在不可证明也不可证否的问题。
所以，希尔伯特的证明数学系统一致性和完备性的梦想至此就破灭了。
哥德尔的证明非常精巧。他先将所有的数学陈述和证明符号化，然后给每个符号串赋予一个数字，这个过程被称为哥德尔配数法。借助数学归纳法，我们可以建立针对所有自然数的陈述，而这样的陈述本身对应着一个数字，这个数字也符合陈述本身的要求。换言之，这个陈述陈述了它本身的性质。
那么现在还剩一个问题，到底哪些问题是可判定的，哪些是不可判定的呢？
图灵
终于说到计算机之父——图灵了，但此时的图灵还不是计算机之父，图灵似乎也没料到自己的研究跟计算机有什么关系，他只是在纽曼教授的课上听到了希尔伯特和哥德尔的研究。
艾伦·麦席森·图灵，OBE，FRS（Alan Mathison Turing，1912年6月23日－1954年6月7日）是英国计算机科学家、数学家、逻辑学家、密码分析学家和理论生物学家，他被誉为计算机科学与人工智能之父。
哥德尔不完备定理虽然证明了基础数学是不完备的，有些问题是无法判定真假的，但还有个问题，到底有哪些问题可以判定哪些不可以？
让我们仔细思考这个问题，对于一个问题，可计算性到底意味着什么？小学的时候我们就学过加减乘除的计算公式，对于乘除法这种通过几步简单的运算就可以得到结果，后来到了初高中，问题变得复杂，但我们仍然可以通过有限的步骤来推导出结果，那么我们可以认为这些问题都是可判定的，因为我们计算出了结果，但对于另一些问题，无论我们如何推导，无论通过多少步骤都无法得到结果，例如停机问题。
让我们再来思考什么是计算，或者说是机械计算，想想我们上学的时候是如何推导数学公式的，我们利用一支笔，在纸上读写数据，最终完成整个推导过程。
图灵准确的抓到了问题的本质，他设计了一个能够模拟“机械计算”的简单到不能再简单的机器，如果这个机器能够完全模拟出整个计算过程，那么他就可以计算所有可被计算的问题。因此如果一个问题不能被这个机器计算，那就是不可判定问题，这就是图灵机。
1936年5月28日，图灵在论文《论可计算数及其在判定问题上的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem）中提出“图灵机”的设想，他将逻辑中的任意命题用一种通用的机器来表示和计算，并能按照一定的规则推导出结论，其结果是：可计算函数可以等价为图灵机能计算的函数。换句话说，图灵机能计算的函数便是可计算的函数，图灵机无法计算的函数便是不可计算的函数。
其实图灵并不是第一个解决这个问题的人，在图灵发表这个论文的几个月前，美国数学家阿隆佐·邱奇（Alonzo Church）提出 λ 演算，得出了与图灵同样的结论，并实际上丘奇最初的目的是重构整个数学大厦的基础，只不过后来被发现其中包含自指，无法成立，但 λ 演算也不是一无是处，至少可以解决希尔伯特判定问题，这也算是 λ 演算的副产品了吧。
通用图灵机
通用图灵机是指可以将一个图灵机作为输入的图灵机，这也就是今天通用计算机的理论数学模型。
所以说起来，通用计算机理论模型也是图灵机的副产品，图灵机本来只是存在理论中用于证明希尔伯特判定问题的一个设定，只不过正好发现可以用来制作通用计算机，真是无心插柳柳成荫。
冯·诺伊曼结构
1945年6月，冯·诺伊曼与戈德斯坦、勃克斯等人，联名发表了一篇长达101页纸的报告，即计算机史上著名的“101页报告”，是现代计算机科学发展里程碑式的文献。明确规定用二进制替代十进制运算，并将计算机分成5大组件，这一卓越的思想为电子计算机的逻辑结构设计奠定了基础，已成为计算机设计的基本原则。
该结构被称为冯·诺伊曼结构（Von Neumann architecture）普林斯顿结构（Princeton architecture），是一种将程序指令存储器和数据存储器合并在一起的电脑设计概念结构。本词描述的是一种实现通用图灵机的计算设备，以及一种相对于并行计算的序列式结构参考模型（referential model）。
约翰·冯·诺伊曼（John von Neumann，1903年12月28日－1957年2月8日），出生于匈牙利的美国籍犹太人数学家，理论计算机科学与博弈论的奠基者，在泛函分析、遍历理论、几何学、拓扑学和数值分析等众多数学领域及计算机学、量子力学和经济学中都有重大贡献。
我们在学习计算机原理的时候肯定都了解过冯诺依曼架构，其作为主流计算机体系结构早已广为人知，如果说图灵机是计算的理论数学模型，那冯诺依曼架构就是计算机的工程逻辑模型。
冯·诺伊曼结构主要特点有：
- 以运算单元为中心
- 采用存储程序原理
- 存储器是按地址访问、线性编址的空间
- 控制流由指令流产生
- 指令由操作码和地址码组成
- 数据以二进制编码
ENIAC
电子数值积分计算机（Electronic Numerical Integrator And Computer），简称 ENIAC，是世界上第一台通用计算机。它是图灵完全的电子计算机，能够重新编程，解决各种计算问题。
二战期间，美国陆军弹道研究实验室为了计算弹道资助宾夕法尼亚大学穆尔电气工程学院研制 ENIAC，1946年2月15日正式投入使用。
ENIAC 那个年代数据还需要通过穿孔纸带存储程序，效率底下，所以虽然是图灵完备的，但是操作比较复杂，修改程序可能要几个星期才能完成，并且会造成算力的浪费。
正当 ENIAC 快要研制完成时，当时深处曼哈顿计划的冯·诺伊曼加入了进来，这个问题不仅当时ENIAC 的两个负责人普雷斯伯·埃克特和约翰·莫奇利意识到了，冯·诺伊曼也迫切的希望能够对此进行改进。因此他们向弹道研究室提出研制可存储程序计算机：EDVAC 的申请，很快得到了批准。
EDVAC
离散变量自动电子计算机（Electronic Discrete Variable Automatic Computer，EDVAC）是一台美国早期电子计算机。与它的前任ENIAC不同，EDVAC采用二进制，而且是一台冯·诺伊曼结构的计算机。
1945年6月，冯·诺伊曼于坐火车通勤到洛斯阿拉莫斯时，他在火车上手写了上面说的那个 101 页的报告《EDVAC报告书的第一份草案》（First Draft of a Report on the EDVAC），这份报告对于计算机来说有这划时代的意义，其中提出的冯·诺伊曼架构一直延续至今，从此全世界都开始抢着研制可存储程序的计算机，计算机行业得以蓬勃发展。
克劳德·香农-信息论
我们今天会把科技革命信息革命挂在嘴边，信息革命的起点可以从香农信息论开始算起，1948年，香农发表了划时代的论文——通信的数学原理，奠定了现代信息论的基础。同时，香农也是数字电路的创始人。另外，虽然香农是计算机科学的基础的奠基人之一，但你肯定想不到，他的博士论文是关于遗传学的。
克劳德·艾尔伍德·香农（Claude Elwood Shannon，1916年4月30日－2001年2月26日），美国数学家、电子工程师和密码学家，被誉为信息论的创始人。香农是密歇根大学学士，麻省理工学院博士。
数字电路
1937年，21岁的香农是麻省理工学院的硕士研究生，他在其硕士论文中提出，将布尔代数应用于电子领域，能够构建并解决任何逻辑和数值关系，被誉为有史以来最具水平的硕士论文之一。
香农在大学时代接触到了布尔关于逻辑系统的理论，后面又获得了电子工程学和数学的学士学位，研究生阶段进入麻省理工学院参与了微分分析机的相关工作，这些经历让香农对计算机的基本组成有了更深层次的思考，他现是证明了布尔代数和二进制算术可以简化当时在电话交换系统中广泛应用的机电继电器的设计。
然后，香农对这些概念进行了扩展，证明了基于机电继电器的电路能用于模拟和解决布尔代数问题。这也就是我们今天熟知的逻辑电路。
香农的这篇论文发表之后，用电子开关模拟布尔逻辑运算成了现代电子计算机的基本思路，香农的工作成为数字电路设计的理论基石。
信息论
信息论是香农在 1948 年发表的《通信的数学原理》论文中提出的概念，该研究奠定了现代信息论的基础。
信息论是应用数学，计算机科学以及电子学的一个分支，其内容主要包括信息的定义、量化、存储及通信等。信息的概念及量化原本是很模糊的，而且跟数学毫无关系，在计算机出现之前，这可能并不重要，但随着计算机能力的提升以及所带来的社会的变革，信息将会呈指数增长，这个时候必须对信息进行更严格的定义，为后来的信息革命奠定基础。
在信息论中有个非常重要的概念：熵（entropy）又称为信息熵，用来描述每条消息中的信息的平均量。熵以 bit 为单位，可以通过计算得到精确的熵值，值越大信息越不确定，因此把熵理解为消息中不确定性的度量。
熵的计算公式如下，其中 P 是概率质量函数。
除此之外，信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。
与上面介绍的一些研究成果不同，信息论属于交叉科学，信息本身并不单纯是计算机科学的概念，实际上包括人类的对话、日常生活中的各种事件都包含了信息，而数学只是信息论的一个统计工具，因此其研究成果对很多行业都有深远的影响。例如航海家深空探测任务的成败、光盘的发明、手机的可行性、互联网的发展、语言学和人类感知的研究、对黑洞的了解等等。
最后
计算机是人类理性思维最伟大的作品，从无知到思考的过程经历了上亿年的演化，可当人类真的开始思考时，短短上千年，便挣脱了思想的牢笼，对自身充满好奇，抛开固有的概念，开始重新思考身边的一切，思考自己的大脑，理性诞生在这种懵懂无知中，人类将它作为利器，制造了能自己思考的计算机，我想，距离真正的人工智能已经不远了。
哥德尔曾经将人类的大脑与计算机做类比：人类的大脑是否等同于计算机？如果答案是确定的，那用计算机模拟出人类的大脑只是时间问题，但如果是否定的，那说明有某种独立于物理人体之外的东西存在，这显然违背了唯物论的思想，因此，可以乐观的认为能自主思考的计算机终有一天会出现。
参考文献
[1]马丁·戴维斯.逻辑的引擎.湖南科学技术出版社,2005
[2]fwjmath.计算的极限
[3]Luc de Brabandere.Homo informaticus
[4]wikipedia