计算机科学史

最早用于计算的已知工具是算盘，出现于公元前2700-2300年间的苏美尔。苏美尔人的算盘由一系列连续的栏组成一张表，这些栏将其分隔为连续的以六十进制数为基础的系统。^[3] 它最初的用法是用鹅卵石在沙子上画线。具有更现代化设计的算盘今天仍然被用作计算工具，比如中国算盘。^[4]

在公元前5世纪的古代印度，语法学家Pāṇini在3959个被称为Ashtadhyayi的规则中制定了梵文语法，该规则是高度系统化和技术性的。Panini使用元规则、转换和递归。^[5]

安提基特拉机构被认为是早期的机械模拟计算机。^[6] 它被设计用来计算天文位置。它于1901年在凯西拉岛和克里特岛之间的希腊安提凯塞拉岛的安提凯塞拉沉船中被发现，并且已经追溯到公元前100年左右。

一千年后，机械模拟计算机设备再次出现在中世纪的伊斯兰世界，并由穆斯林天文学家开发，如阿贝沙恩·阿尔布尔日^[7] 的机械齿轮星盘和贾比尔·伊本·阿弗拉赫^[8]的扭矩盘。 根据西蒙·辛格的说法，穆斯林数学家在密码学方面也取得了重要的进展，例如阿尔金达斯对密码分析和频率分析的发展。^[9][10] 可编程机器也是由穆斯林工程师发明的，例如巴斯兄弟的^[11] 自动长笛演奏者和阿尔-贾扎里的可编程仿人自动机和城堡钟，后者被认为是第一台可编程模拟计算机。^[12] 14世纪欧洲出现了类似复杂程度的技术人工制品，有机械天文钟。^[13]

当约翰·耐普尔在17世纪早期发现用于计算目的的对数时，随后，发明家和科学家在制造计算工具方面取得了相当大的进步。1623年，威廉·希克卡德设计了一台计算机，但当他开始建造的原型在1624年被一场大火摧毁时，他放弃了这个项目。大约在1640年，法国著名数学家布莱士·帕斯卡根据希腊数学家亚历山大的英雄所描述的设计，建造了一个机械加法装置。^[14] 然后在1672年，戈特弗里德·威廉·莱布尼茨发明了阶梯计算器，并于1694年完成。^[15]

1837年，查尔斯·巴贝奇首次描述了他的分析引擎，这被认为是现代计算机的第一个设计。分析引擎具有可扩展的内存、运算单元和逻辑处理能力，能够解释带有循环和条件分支的编程语言。尽管从未建造过，但该设计已经被广泛研究过，并被理解为图灵等效物。分析引擎的内存容量将小于1千字节，时钟速度将小于10赫兹。

在设计出第一台现代计算机之前，数学和电子学理论需要相当大的进步。

1702年，戈特弗里德·威廉·莱布尼茨通过他关于二进制数字系统的著作，发展了形式上的数学意义上的逻辑。在他的系统中，1和0也代表真值和假值或者开和关状态。但是过了一个多世纪，乔治·布尔才在1854年发表了他的布尔代数，并建立了一个完整的系统，允许对计算过程进行数学建模。^[16]

这时，已经有人发明了由二元模式驱动的第一个机械装置。工业革命推动了许多任务的机械化，其中包括纺织。穿孔卡片在1801年控制了约瑟夫·玛丽·贾卡的织布机，卡片上穿孔表示二进制1，未穿孔点表示二进制0。贾卡的织布机远非电脑，但它确实说明机器可以由二进制系统驱动。^[16]

20世纪20年代以前，计算机(computers或者computors)是执行计算的人类职员。他们通常由物理学家领导。成千上万台计算机被用于商业、政府和研究机构。这些计算机大多是女性。^{[17][18][19][20]} 有些人为日历进行天文计算，有些人为军队进行弹道计算。^[21]

20世纪20年代以后，计算机这个词指的是任何能完成人类计算机工作的机器，尤其是那些符合丘奇-图灵理论有效方法的机器。这篇论文指出，如果一种数学方法可以被列为一个指令清单，并且人类职员可以用纸和铅笔在必要的时间内，在没有独创性和洞察力的情况下遵循，那么它就是有效的。

用连续值计算的机器被称为模拟型机器。他们使用代表连续数值的机器，比如轴旋转的角度或电势差。

与模拟相比，数字机器能够呈现数值状态并存储每个数字。在更快的存储设备发明之前，数字机器使用不同的引擎或继电器。

20世纪40年代后期，随着电子数字机器的出现变得普遍，计算机(computing machine)这个词逐渐让位于计算机(computer)。这些计算机能够执行以前人类职员所做的计算。

由于数字机器存储的数值不像ADI公司那样受物理属性的限制，基于数字设备的逻辑计算机能够做任何可以被描述为“纯机械”的事情。艾伦·图灵创建的理论图灵机是一个假设的装置，其理论化是为了研究这种硬件的特性。

4.1 查尔斯·巴贝奇和阿达·洛芙莱斯

查尔斯·巴贝奇经常被认为是计算的第一批先驱之一。从19世纪10年代开始，巴贝奇就有了用机械计算数字和表格的愿景。把这变成现实，巴贝奇设计了一个计算器来计算长达8位小数的数字。随着这一想法的成功，巴贝奇致力于开发一种可以计算最多20位小数的机器。到了19世纪30年代，巴贝奇设计了一个计划，开发一种可以使用穿孔卡片进行算术运算的机器。机器将把数字存储在存储单元中，并且会有一种顺序控制的形式。这意味着一个操作将在另一个之前进行，这样机器将产生一个答案而不会失败。这台机器被称为“分析引擎”，它是现代计算机的第一个真正代表。^[22]

阿达·洛芙莱斯(奥古斯塔·爱达·拜伦)被认为是计算机编程的先驱，被认为是数学天才，这是她年轻时母亲给她安排的繁重的数学辅导课程的结果。洛夫莱斯在巴贝奇研究他的第一台机械计算机“分析引擎”时，开始和查尔斯·巴贝奇一起做助手。^[23] 在与巴贝奇共事期间，阿达·洛芙莱斯成为第一个能够计算伯努利数的计算机算法的设计者。^[24] 此外，洛夫莱斯与巴贝奇的合作导致她预测未来的计算机不仅能进行数学计算，还能操纵符号，不管是不是数学符号。^[25] 虽然她从未能看到自己工作的成果，因为“分析引擎”不是在她有生之年创造的，但从19世纪40年代开始，她在晚年的努力并没有被忽视。^[26]

4.2 艾伦·图灵和图灵机

库尔特·哥德尔用他的不完全性定理(1931)开始奠定现代计算机科学的数学基础。在这个定理中，他表明在一个形式系统中可以证明和证明的东西是有限度的。这导致哥德尔等人定义和描述这些形式系统，包括像μ递归函数和λ可定义函数这样的概念。

1936年，艾伦·图灵和阿隆佐·邱奇独立地，也一起，引入了一种算法的形式化，对可以计算的东西加以限制，以及一种“纯机械”的计算模型。这成为了丘奇-图灵论文，一个关于机械计算设备性质的假设，例如电子计算机。这篇论文声称，只要有足够的时间和存储空间，任何可能的计算都可以由运行在计算机上的算法来执行。

1936年，艾伦·图灵还发表了他关于图灵机的开创性工作，图灵机是一种抽象的数字计算机，现在简称为通用图灵机。这台机器发明了现代计算机的原理，是几乎所有现代计算机都使用的存储程序概念的发源地。^[27] 这些假设的机器被设计成从数学上正式确定可以计算什么，同时考虑到计算能力的限制。如果图灵机能完成任务，它被认为是图灵可计算的，或者更常见的是图灵完备。^[28]

洛斯阿拉莫斯物理学家斯坦利·弗兰克尔在一封信中描述了约翰·冯·诺依曼对图灵1936年论文的根本重要性的观点:^[27]

我知道大约在1943年或1944年，冯·诺依曼非常清楚图灵1936年论文的根本重要性……冯·诺依曼向我介绍了那篇论文，在他的敦促下，我仔细研究了它。许多人称赞冯·诺依曼为“计算机之父”(现代意义上的计算机之父)，但我确信他自己永远不会犯那个错误。也许他很可能被称为助产士，但他坚定地向我强调，也向其他人强调，基本概念是图灵提出的...

4.3 中岛彰和开关电路理论

直到20世纪30年代，电气工程师能够建造电子电路来解决数学和逻辑问题，但大多数都是以临时的方式进行的，缺乏任何理论上的严密性。20世纪30年代，随着日本电气公司工程师中岛昭夫(Akira Nakashima)的开关电路理论，这种情况发生了变化。从1934年到1936年，中岛发表了一系列论文，表明他独立发现的二值布尔代数(直到1938年他才知道乔治·布尔的工作)可以描述开关电路的操作。^{[29][30][31][32]} 。利用电开关的特性进行逻辑运算的概念是所有电子数字计算机的基本概念。开关电路理论为现代技术几乎所有领域的数字系统设计提供了数学基础和工具。^[32]

中岛的工作后来在克劳德·艾尔伍德·香农1937年开创性的硕士论文《继电器和开关电路的符号分析》中被引用和阐述。^[31] 在参加本科哲学课程时，香农接触了布尔的工作，并认识到它可以用来安排机电继电器(然后用于电话路由开关)来解决逻辑问题。第二次世界大战期间和之后，他的论文在电气工程界广为人知，成为实用数字电路设计的基础。

4.4 早期计算机硬件

世界上第一台电子数字计算机——阿坦纳索夫-贝里计算机是由物理和数学教授约翰·阿坦纳索夫和工程研究生克利福德·贝里于1939年至1942年在爱荷华州校园建造的。

1941年，康拉德·楚泽开发了世界上第一台功能性程控计算机Z3。1998年，它在原则上被证明是图灵完备的。^[33][34] 苏泽还开发了S2计算机，被认为是第一台过程控制计算机。1941年，他创立了最早的计算机企业之一，生产Z4，成为世界上第一台商用计算机。1946年，他设计了第一种高级编程语言——普兰卡尔。^[35]

1948年，曼彻斯特宝贝完成；这是世界上第一台运行存储在内存中的程序的电子数字计算机，就像几乎所有现代计算机一样。^[27] 图灵1936年关于图灵机的开创性论文及其对该项目的逻辑数学贡献对马克斯·纽曼的影响，对曼彻斯特宝贝的成功发展都至关重要。^[27]

1950年，英国国家物理实验室根据图灵的哲学完成了小规模可编程计算机“王牌飞行员”(Pilot ACE)。飞行员模型ACE的工作速度为1兆赫，一度是世界上最快的计算机。^[27][36] 图灵对ACE的设计与今天的RISC架构有很多共同之处，它要求一个与早期麦金塔计算机容量大致相同的高速存储器，以他那个时代的标准来看，这是巨大的。^[27] 如果图灵的“宇宙飞船”计算机按计划完整建造，它将会与其他早期的计算机不同。^[27]

4.5 香农和信息论

克劳德·香农在1948年发表的题为《通信的数学理论》的论文中开创了信息论领域，该论文将概率论应用于如何对发送者想要发送的信息进行最佳编码的问题。这项工作是许多研究领域的理论基础之一，包括数据压缩和密码学。

4.6 维纳和控制论

通过解释雷达图像来探测敌机的防空系统实验，诺伯特·维纳从希腊语中创造了“操纵者”这个词。他在1948年发表了《控制论》，这影响了人工智能。维纳还将计算、计算机器、记忆设备和其他认知相似性与他对脑电波的分析进行了比较。

第一个真正的计算机错误是蛾。它被困在哈佛马克2号的继电器之间。^[37] 虽然“臭虫”一词的发明经常被错误地归咎于格蕾丝·赫柏，一位未来的美国海军少将，他被认为在1945年9月9日记录了“臭虫”，但大多数其他的说法至少与这些细节相矛盾。根据这些记录，实际日期是1947年9月9日，当时操作人员提交了这一“事件”——连同昆虫和注释“发现的第一个实际错误案例”。^[37]

4.7 约翰·冯·诺依曼和冯·诺依曼结构

1946年，出现了一个计算机体系结构模型，并被称为冯·诺依曼体系结构。自1950年以来，冯·诺依曼模型为后来的计算机设计提供了一致性。冯·诺依曼架构被认为是创新的，因为它引入了允许机器指令和数据共享内存空间的思想。冯·诺依曼模型由三个主要部分组成，算术逻辑单元(ALU)、存储器和指令处理单元(IPU)。在冯·诺依曼机器设计中，IPU将地址传递给内存，而内存将指令传回IPU(如果正在提取指令)，或者将数据传回算术逻辑单元(如果正在提取数据)。^[38]

冯·诺依曼的机器设计采用精简指令集计算体系结构，这意味着指令集总共使用21条指令来执行所有任务。(这与CISC的复杂指令集计算形成对比，后者有更多的指令可供选择。)对于冯·诺依曼架构，主存储器和累加器(保存逻辑运算结果的寄存器)^[39] 是被寻址的两个存储器。运算可以作为简单的算术(这些运算由算术逻辑单元执行，包括加法、减法、乘法和除法)、条件分支(这些现在更常见于if语句或while循环。这些分支起到go to语句的作用)，以及机器不同组件之间的逻辑移动，即从累加器到存储器的移动，反之亦然。冯·诺依曼架构使用数据和指令作为数据类型。最后，由于冯·诺依曼架构很简单，其寄存器管理也很简单。该架构使用一组七个寄存器来操作和解释提取的数据和指令。这些寄存器包括“IR”(指令寄存器)、“IBR”(指令缓冲寄存器)、“MQ”(乘数商寄存器)、“MAR”(存储器地址寄存器)和“MDR”(存储器数据寄存器)。^[38] “该架构还使用程序计数器(“PC”)来跟踪机器在程序中的位置。^[38]