读算法简史：从美索不达米亚到人工智能时代04计算机之梦.png

1. 计算机之梦

1.1. 机械的应用使工业生产水平出现了惊人的提高，对旧工艺流程的改进以及新工艺流程的发明

• 1.1.1. 托马斯·亨利·赫胥黎(Thomas Henry Huxley)

1.2. 手动执行计算缓慢而枯燥

• 1.2.1. 几千年来，发明家们一直在尝试设计能够加速计算的设备

• 1.2.2. 第一个成功的产出是算盘

  • 1.2.2.1. 公元前2500年左右，苏美尔人发明了泥板算盘，这是从用鹅卵石计数和沙子书写演变而来的

    1.2.2.1.1. 为了更快速地计算，他们在泥板表面蚀刻了线条和符号

  • 1.2.2.2. 珠轨算盘是在中国发明的，然后经由古罗马人在欧洲普及开来

• 1.2.3. 第一个机械计算器是在17世纪由法国人和德国人各自独立发明的

  • 1.2.3.1. 由手动曲柄驱动，通过杠杆、轮齿和齿轮的运动来完成加法和减法运算

1.3. 18世纪末和19世纪初发生了工业革命

• 1.3.1. 工程师们设计出以蒸汽和水流为动力的机器，取代了传统的手工生产方式

• 1.3.2. 劳动力从农村转移到城镇，在嘈杂、黑暗且危险的工厂里与机器一起劳作

• 1.3.3. 雅卡尔的织布机可以被编程(programmed)，以生产不同织法的纺织物

• 1.3.4. 到19世纪早期，欧洲已经有了手摇驱动的计算器和蒸汽驱动的可编程织布机

2. 最早的程序员

2.1. 科学论文是研究的命脉

• 2.1.1. 一篇论文是描述一个新想法的报告，它有实验结果或数学证明作为支撑，理想情况下两者兼有

• 2.1.2. 科学依赖于证据，证明必须经过验证，实验必须是可重复的

• 2.1.3. 论文由同领域的专家评审

• 2.1.4. 只有最好的论文才会被发表

• 2.1.5. 在期刊或会议上发表文章，可以向科学界有兴趣的各方传播新观点

• 2.1.6. 发表一篇论文是一个学者职业生涯的里程碑，这表明他们在该领域具备了实力且站稳了脚跟

2.2. 查尔斯·巴贝奇

• 2.2.1. Charles Babbage

  • 2.2.1.1. 1791年出生在英国萨里郡的沃尔沃思

• 2.2.2. 在巴贝奇的年代，由于缺乏公共基金，只有少数几所大学和少数富有的科学爱好者能开展科学研究

  • 2.2.2.1. 科学论述常常发生在富人的沙龙里，甚至连“科学家”这个词都是新出现的

• 2.2.3. 1828年，巴贝奇最终被任命为剑桥大学卢卡斯数学教授

• 2.2.4. 基于他已发表的论文的诸多贡献，巴贝奇被选为英国皇家学会会士

• 2.2.5. 主要天赋在于发明机械设备

  • 2.2.5.1. 设计了一种蒸汽动力机械，可以自动计算和打印表格

    2.2.5.1.1. 十进制数字由轮齿、齿轮和杠杆的位置来表示

  • 2.2.5.2. 巴贝奇差分机

    2.2.5.2.1. 项目失败了

  • 2.2.5.3. 分析机

    2.2.5.3.1. 分析机将是机械的，用蒸汽驱动，以十进制运算

    2.2.5.3.1.1. 它还是完全可编程的

    2.2.5.3.1.2. 这种新机器借鉴了雅卡尔的织布机，可以从打孔卡片上读取指令和数据

    2.2.5.3.1.3. 结果也是通过打孔卡片呈现

    2.2.5.3.2. 分析机将成为第一台通用计算机

    2.2.5.3.2.1. 分析机被设计用来执行算术运算，但所使用的符号可以代表其他形式的信息

    2.2.5.3.3. 分析机明显具备了现代计算机的所有要素，仅一个要素除外：分析机是机械的，而不是电子的

    2.2.5.3.3.1. 商业化生产的电灯泡是托马斯·爱迪生在巴贝奇死后发明的

    2.2.5.3.3.2. 巴贝奇留给计算机界的遗产是洛芙莱斯的论文

2.3. 艾达·洛芙莱斯

• 2.3.1. 原名奥古丝塔·艾达·拜伦(Augusta Ada Byron)

• 2.3.2. 生于1815年，是拜伦勋爵和拜伦夫人的女儿

• 2.3.3. 数学方程的序列只能由人来完成

  • 2.3.3.1. 打孔卡片上的指令可以由分析机高速自动执行

• 2.3.4. 洛芙莱斯的执行追踪与古巴比伦人带有实例的算法展示遥相呼应

• 2.3.5. 程式错误(bug)

• 2.3.6. 论文题为《分析机概述》(Sketch of the Analytical Engine)，是一篇颇具远见的文章

  • 2.3.6.1. 在论文中包含的一个程序列表中发现了一个错误：在应该是4的地方出现了3

    2.3.6.1.1. 这是第一个软件版本里的第一个程式错误

    2.3.6.1.1.1. 此后许多同类问题的先祖

2.4. 巴贝奇、梅纳布雷亚和洛芙莱斯的精彩论文是一门新科学的第一缕曙光

• 2.4.1. 把算法、程序设计和数据联系起来的科学，就是计算机的科学

• 2.4.2. 又过了100年，这一领域才被承认并命名为计算机科学

3. 艾伦·图灵

3.1. 计算机科学界的最高荣誉被命名为ACM图灵奖（简称图灵奖）

• 3.1.1. 每年100万美元的奖金由美国计算机协会(Association for Computing Machinery，ACM)提供，以表彰“具有持久且重大技术价值”的贡献

3.2. 1912年，图灵出生于英国伦敦

• 3.2.1. 图灵被授予大英帝国勋章，以表彰他在二战时的贡献

3.3. 图灵和戈登·韦尔什曼(Gordon Welchman)开发了一台特殊用途的计算机，以协助破解德国的恩尼格玛密码

• 3.3.1. “炸弹”(The Bombe)破译机是一种机电计算装置，于1940年建成

3.4. 1952年

• 3.4.1. 图灵被指控犯有“严重猥亵罪”

  • 3.4.1.1. 法院判决图灵接受激素“疗法”——化学阉割的委婉说法

  • 3.4.1.2. 2013年，英国女王伊丽莎白二世赦免了图灵的同性恋“罪行”

3.5. 图灵的孤僻以及他坚持从第一性原理出发思考问题，给他的工作注入了罕见的新颖度

3.6. 图灵在一篇杰出的科学论文中提出了三个重要的思想

• 3.6.1. 正式定义了算法

• 3.6.2. 定义了通用计算机必须具备的功能

• 3.6.3. 用这些定义证明了有些函数是不可计算的

3.7. 图灵从没想过他的机器会被造出来

• 3.7.1. 相反，图灵机一直被认为是计算机的一个抽象模型——一个能够促进计算理论发展的构想

• 3.7.2. 图灵设想由人类程序员编写程序供机器执行

3.8. 图灵机

• 3.8.1. 由无限长的纸带、纸带带头、存储器和一组控制机器运行的指令组成

  • 3.8.1.1. 存储的值称为机器的当前状态(state)

• 3.8.2. 在图灵机中，每条指令由1个前置条件和3个动作组成，如果前置条件满足，则执行动作

  • 3.8.2.1. 前置条件取决于机器的当前状态（存储器中的值）和当前位于带头下方的符号

  • 3.8.2.2. 如果当前状态和符号与前置条件中指定的值相匹配，则执行与前置条件相关联的动作

• 3.8.3. 体现了计算机的所有必备功能

  • 3.8.3.1. 读取和写入数据

  • 3.8.3.2. 执行易于修改的指令

  • 3.8.3.3. 处理表示信息的符号

  • 3.8.3.4. 根据数据做出决定

  • 3.8.3.5. 重复指令

• 3.8.4. 图灵机可以操作符号

  • 3.8.4.1. 图灵机没有专门的算术指令（也就是加、减、乘、除）

  • 3.8.4.2. 算术运算是通过执行程序来实现的，这些程序处理纸带上的符号，从而达到算术运算的效果

• 3.8.5. 算法是图灵机可以通过编程来执行的一系列步骤

  • 3.8.5.1. 通用计算机是指能够执行程序的机器，且这些程序与图灵机所能执行的程序等同

• 3.8.6. 图灵机的一个基本特性是它能够检查数据并决定下一步执行什么操作

  • 3.8.6.1. 这种能力使计算机比自动计算器更高级

    3.8.6.1.1. 计算器不能做决定

    3.8.6.1.2. 计算器可以处理数据，但不能对数据做出响应

  • 3.8.6.2. 决策能力赋予了计算机执行算法的能力

• 3.8.7. 图灵机仍然是所有计算机比较的基准，通过图灵测试已经成为人工智能一直以来的目标之一

• 3.8.8. 通用计算机的标志是图灵完备(Turing complete)

  • 3.8.8.1. 可以模拟图灵机的运行

  • 3.8.8.2. 纸带符号当然可以用其他物理量代替，例如现代计算机中使用的电子电压电平

  • 3.8.8.3. 所有现代计算机都是图灵完备的

  • 3.8.8.4. 如果它们不是图灵完备的，那它们就不是通用计算机

3.9. 有些函数是不能用算法计算的

• 3.9.1. 停机问题(halting problem)

  • 3.9.1.1. 停机问题展示出了编程中的一个实际困难

  • 3.9.1.2. 程序员如果犯了错误，很容易编写出某些步骤永远在重复的程序

    3.9.1.2.1. 这种情况被称为无限循环(infi nite loop)

• 3.9.2. 基于悖论的证明方法

  • 3.9.2.1. 取一个你想证明为假的陈述

  • 3.9.2.2. 现在，假设这个陈述是真的

  • 3.9.2.3. 在该假设基础上，建立逻辑线

  • 3.9.2.4. 如果得出的结论是一个悖论，而且逻辑线是正确的，那么这个假设肯定是无效的

• 3.9.3. 图灵用一个悖论来证明停机问题不存在解

  • 3.9.3.1. 解决停机问题的检查算法确实存在

  • 3.9.3.2. 这种假定的检查算法能显示一个程序是否停止

    3.9.3.2.1. 如果被检查的程序停止运行，那么检查算法输出“停止”

    3.9.3.2.2. 否则，检查算法输出“不停止”

  • 3.9.3.3. 检查算法

    3.9.3.3.1. 以一个程序作为输入

    3.9.3.3.2. 如果程序总是停止，那么输出“停止”，否则输出“不停止”

  • 3.9.3.4. 重复以下步骤

    3.9.3.4.1. 将检查算法作为输入，运行检查算法

    3.9.3.4.2. 如果检查算法输出“不停止”，那么停止重复

    3.9.3.4.3. 如果检查算法输出“不停止”，那么循环终止，程序停止

    3.9.3.4.4. 如果检查算法输出“停止”，那么程序将无限次重复因而不会停止

    3.9.3.4.5. 检查算法检查的是算法自己

    3.9.3.4.5.1. 只有当检查算法没有停止时，检查算法才会停止

    3.9.3.4.5.2. 相反，如果检查算法停止，检查算法就不会停止

    3.9.3.4.5.3. 两种结果都是自相矛盾的

3.9.3.4.5.3.1. 悖论

• 3.9.4. 对于有些函数，即使有了完整的认识，也是无法计算的

  • 3.9.4.1. 计算是有限度的

3.10. 许多有用的函数（从输入值映射到输出值）都是可计算的

• 3.10.1. 困难在于如何提出有效的算法来执行所需的映射

3.11. 比他的发明更重要的是他那些散布在一篇篇论文中的零散想法

• 3.11.1. 那些看似漫不经心的思考为后来追随他脚步的人开辟了未来探索的道路

• 3.11.2. 撰写了一系列关于计算机可能的应用前景的科学论文

• 3.11.3. 提出，计算机可以预测分子在生物系统中的行为，这为现代生物信息学埋下了伏笔

• 3.11.4. 认为计算机可以解决迄今为止需要人类智能才能解决的问题

• 3.11.5. 推测，到2000年，人类询问者将不可能辨别出与其交流的文字信息是来自人类还是计算机

4. 康拉德·楚泽

4.1. 在柏林，德国工程师康拉德·楚泽(Konrad Zuse)建造了一系列基于继电器的机电计算设备

4.2. 可编程且全自动的Z3计算机于1941年建造完成

4.3. Z4计算机最终于1950年交付给苏黎世联邦理工学院

5. 霍华德·艾肯

5.1. 在美国，第二次世界大战对初代计算机的研发是一个福音

• 5.1.1. 到巴贝奇差分机示范模型的启发，霍华德·艾肯(Howard Aiken)在哈佛大学设计出了一台电子计算机

5.2. 这台名为“哈佛马克1号”的计算机（又名自动化循序控制计算器）由IBM公司资助和承建，于1944年交付

• 5.2.1. 这台机器是完全可编程的和自动化的，可以在没有干预的情况下连续多日运行

• 5.2.2. “哈佛马克1号”缺乏决策能力，因此不是图灵完备的，所以它不算一台通用计算机

5.3. 世界上第一台可操作的数字通用计算机在美国宾夕法尼亚州建成

• 5.3.1. 这台机器由美国陆军提供资金，具有明确的军事用途，于1946年向媒体公开