计算

计算已经成为人们生活中不可或缺的组成部分，人类社会享受了计算技术的红利得以飞速发展。可以说当今的计算机科学和产业应用的成就是人类文明有史以来所有智慧的结晶。解释、澄清和发展“计算”这一重要概念，即本书之写作目的。本书从探索数学的起源开始，细数了数学史上三次危机的来龙去脉，逐渐引出计算理论的诞生和发展，以及这些过往是如何影响当今计算机科学最前沿方向的。最后本书从哲学层面探讨了计算的边界，将其视为人类需要继续探索的未解之谜。本书横跨了人类3000年的文明史，综合了数学、哲学、物理学、计算机科学、人工智能、复杂系统科学等多门学科，呈现出一种独特的计算主义的世界观。

吴翰清，毕业于西安交通大学少年班。清华大学创新领军工程博士（人工智能方向，在读）。2005年加入阿里，创建了阿里巴巴、淘宝、支付宝的安全体系，也是阿里云初创团队成员，是阿里安全从无到有、从有到强的亲历者。2017年开始致力于城市大脑的研究与建设，专注于构建机器智能系统。2017年入选 MIT 全球青年科技创新人才榜，是中国互联网安全领域入选 TR35 的第一人。2019年入选「大数据文摘」评选的「30位新生代数字经济人才」。2019年当选中国青年科技工作者协会第六届理事。公益项目“计算图书馆”发起人。目前正致力于人工智能的研究和创业。

导论 ....................................................................................................................................1 第一部分 计算的诞生 第 1 章 毕达哥拉斯的困惑..............................................................................................24 数的计算 .......................................................................................................................24 从数觉到计数 .......................................................................................................24 文明古国的计算 ...................................................................................................28 毕达哥拉斯学派 ...........................................................................................................30 柏拉图的理想世界 .......................................................................................................40 第一次数学危机 ...........................................................................................................44 无理数的发现 .......................................................................................................44 芝诺悖论：无穷之辩 ...........................................................................................46 演绎推理：逻辑学和几何学 .......................................................................................51 亚里士多德的逻辑学 ...........................................................................................51 欧几里得的《几何原本》 ...................................................................................55 悖论：推理的暗面 ...............................................................................................59 第 2 章 计算之术 ............................................................................................................62 代数：字符的计算 .......................................................................................................62 符号与代数 ...................................................................................................................63 零的诞生 ...............................................................................................................63 言辞代数 ...............................................................................................................65 未知量的表示 .......................................................................................................68 还原与对消 ...........................................................................................................70 代数符号 ...............................................................................................................73 求解多项式方程 ...........................................................................................................77 从数值解到代数解 ...............................................................................................77 三次方程的求根公式 ...........................................................................................81 不可约：复数的发现 ...........................................................................................84 数系的扩张 ...........................................................................................................89 代数基本定理 .......................................................................................................92 代数的结构 ...................................................................................................................94 求解一元五次方程 ...............................................................................................94 方程根的结构 .......................................................................................................95 伽罗瓦的遗珠 .....................................................................................................101 计算工具 .....................................................................................................................108 人类计算员 .........................................................................................................109 面向机器的计算思维 .........................................................................................111 第 3 章 莱布尼茨的计算之梦 ........................................................................................116 数理逻辑的创立 .........................................................................................................117 人类思想字母表 .........................................................................................................120 思想的大衍术 .....................................................................................................121 计算之梦 .....................................................................................................................125 思维规律的研究 .........................................................................................................127 19 世纪数理逻辑的复兴 ....................................................................................127 布尔的逻辑代数 .................................................................................................129 第二部分 计算的数学基础 第 4 章 数学的基础.......................................................................................................136 第二次数学危机 .........................................................................................................136 微积分的发明 .....................................................................................................136 消失的鬼魂：贝克莱悖论 .................................................................................139 分析的严格化 .....................................................................................................140 集合论的诞生 .............................................................................................................142 无穷大有多大 .....................................................................................................142 对角线方法 .........................................................................................................146 康托尔的超穷数 .........................................................................................................148 超穷基数与超穷序数 .........................................................................................148 连续统假设 .........................................................................................................152 算术的逻辑化 .............................................................................................................156 弗雷格的“概念文字” .....................................................................................156 自然数的定义 .....................................................................................................159 第 5 章 第三次数学危机 ...............................................................................................163 危机：罗素悖论 .........................................................................................................163 集合论悖论 .........................................................................................................163 自我指涉 .............................................................................................................165 悖论的解决方法 .................................................................................................168 逻辑主义进路 .............................................................................................................169 直觉主义进路 .............................................................................................................173 公理集合论进路 .........................................................................................................176 ZFC 公理集合论.................................................................................................177 选择公理 .............................................................................................................180 NBG 公理集合论................................................................................................182 第三部分 计算理论的形成 第 6 章 计算理论的奠基：希尔伯特进路......................................................................186 数学的无冕之王 .........................................................................................................186 希尔伯特问题 .............................................................................................................188 数学的世纪之问 .................................................................................................188 希尔伯特的第 10 个问题 ...................................................................................189 几何的算术基础 .........................................................................................................192 欧几里得的第五公设 .........................................................................................192 模型化方法 .........................................................................................................194 桌子、椅子和啤酒杯：形式系统思想..............................................................195 “形式主义”之父 .....................................................................................................196 有穷主义证明论 .........................................................................................................198 希尔伯特纲领 .............................................................................................................201 可判定性问题 .....................................................................................................201 王者的落幕 .........................................................................................................202 第 7 章 计算不能做什么：终结者哥德尔......................................................................204 昨日的世界 .................................................................................................................204 我们必须知道，我们必将知道 .........................................................................204 伟大的友谊 .........................................................................................................205 哥德尔的发现 .....................................................................................................207 编码思想：哥德尔数 .................................................................................................209 哥德尔证明 .................................................................................................................213 不完备性定理 .....................................................................................................213 塔斯基定理 .........................................................................................................215 希尔伯特计划的破灭 .........................................................................................216 哥德尔纲领 .................................................................................................................217 自亚里士多德以来 .....................................................................................................218 第 8 章 计算理论的诞生：图灵的可计算数 ..................................................................221 图灵的学业 .................................................................................................................221 图灵机.........................................................................................................................223 模拟人类计算员 .................................................................................................223 图灵机模型 .........................................................................................................224 可计算数 .............................................................................................................226 丘奇-图灵论题............................................................................................................229 判定性问题的证明 .....................................................................................................231 图灵的证明 .........................................................................................................231 停机问题 .............................................................................................................234 忙碌的海狸 .................................................................................................................235 快速增长函数 .....................................................................................................235 不可计算的函数 .................................................................................................238 图灵的命运 .................................................................................................................239 第四部分 计算的极限 第 9 章 计算复杂性.......................................................................................................242 难解的计算问题 .........................................................................................................243 旅行商问题 .........................................................................................................243 多项式时间与指数时间 .....................................................................................245 P/NP 问题....................................................................................................................249 NP 问题...............................................................................................................249 NP 完全问题.......................................................................................................251 柯尔莫哥洛夫复杂度 ........................................................................................254 库克-莱文定理....................................................................................................255 计算的局部性原理 .............................................................................................257 P=NP 吗 ......................................................................................................................257 P=NP 的世界.......................................................................................................258 认知的边界 .........................................................................................................259 P≠NP 的若干推论.............................................................................................260 站在两个世界之间 .....................................................................................................266 未分类的问题 .....................................................................................................266 因数分解问题 .....................................................................................................267 图同构问题 .........................................................................................................268 近似计算 .....................................................................................................................268 丹齐格的线性规划 .............................................................................................270 挑战旅行商问题 .................................................................................................272 PCP 定理与不可近似性 .....................................................................................281 并行计算 .....................................................................................................................284 计算的时空平衡性 .............................................................................................284 并行计算的极限 .................................................................................................285 挑战极限 .............................................................................................................287 第 10 章 量子计算 ........................................................................................................293 计算是数学的，更是物理的 .....................................................................................293 量子计算的启蒙 .................................................................................................293 量子的特性 .........................................................................................................295 计算的最小能量 .................................................................................................296 量子比特 .....................................................................................................................298 从经典比特到量子比特 .....................................................................................298 量子优势 .............................................................................................................300 量子门与量子线路 .............................................................................................300 量子算法 .....................................................................................................................303 从 BPP 到 BQP ...................................................................................................303 Shor 算法.............................................................................................................305 量子霸权 .....................................................................................................................307 量子计算机的实现 .............................................................................................307 展望量子霸权 .....................................................................................................308 第 11 章 复杂性计算.....................................................................................................310 什么是复杂 .................................................................................................................310 反馈与控制 .................................................................................................................312 现代复杂性研究思潮 .................................................................................................318 复杂性的简单算法 .............................................................................................318 生命游戏 .............................................................................................................321 涌现 .....................................................................................................................323 耗散结构 .............................................................................................................324 网络科学 .............................................................................................................326 进化计算 .....................................................................................................................330 生物系统的信息处理 .........................................................................................330 逻辑深度 .............................................................................................................334 企业的进化计算 .................................................................................................335 第 12 章 机器能思考吗.................................................................................................338 模拟大脑的结构 .........................................................................................................338 机器智能大论战 .........................................................................................................340 模仿游戏与中文屋 .............................................................................................340 符号主义与连接主义 .........................................................................................344 AlphaGo 与李世石..............................................................................................350 ChatGPT 与乌鸦.........................................................................................................355 人工智能的圣杯 .................................................................................................355 ChatGPT 的原理 .................................................................................................356 350 多年的等待 ..................................................................................................362 聪明的乌鸦 .........................................................................................................365 未来的方向 .........................................................................................................366 机器的意识 .................................................................................................................374 第 13 章 自然哲学的计算原理......................................................................................379 计算的边界 .................................................................................................................379 时空的桎梏 .........................................................................................................379 宇宙是一台计算机吗 .........................................................................................380 图灵极限 .............................................................................................................384 边界之外 .....................................................................................................................386 无穷时间的计算 .................................................................................................386 无穷空间的计算 .................................................................................................387 一种计算主义的世界观 .............................................................................................392 后记 ................................................................................................................................397 附录 A 科研范式进化史纲要.........................................................................................399 附录 B 提问与求解的艺术 ............................................................................................404 附录 C 世界需要什么样的智能系统..............................................................................416 附录 D 机器智能宣言 ...................................................................................................423 参考文献 .........................................................................................................................425