计算

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

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

1.“计算”是科技的引擎和所有科技热点的中心，全球首度以此为线索的硬核科普读物。
2.作者曾是阿里云初创团队成员之一，也曾是阿里巴巴杰出青年科学家中的翘楚，在书中的观点新锐又深邃，博古通今又主线鲜明，史实珍稀又富含洞察。
3.科技与互联网公司一众与计算生态息息相关的业者，可以通过这本书及这个系列，理解计算的深邃内涵与历史沿革，以及关键命脉与终极归宿。

后记
这本书我足足写了 3 年。
3 年前，新冠疫情刚刚暴发的时候，我被隔离在家。闲来无事，难得清静，就想把自己多年的所学所思总结下来。想必 1665 年牛顿因为瘟疫而休学返乡时，也是这种情形。于是我开始动笔构思了第一版提纲，并写下最初的 2 万多字。原计划用一年左右的时间写完这本书，但是越写越觉得需要交代清楚来龙去脉的地方太多，在几次修改提纲后，原计划一本就写完的书变成了 3 卷的大部头写作计划。这 3 卷我打算分别谈一谈计算原理、计算技术和计算经济。而 3 年前起草的那 2 万多字反倒变成了第三卷的内容。如此看来，3 卷写完怕不是得超 100 万字。
细心的读者可能会注意到，本书洋洋洒洒 30 多万字，却连计算机都还没造出来（真想打个捂着脸的表情）！因为冯·诺依曼、香农等人，ENIAC、EDVAC 等早期计算机项目，按规划是要到第二卷才登场的！所以本书名叫《计算》，只好让冯·诺依曼很委屈地担任了配角。还好关于计算原理的一切，我想表达的在本书中都已经充分表达了！
按照我目前的速度，第二卷可能会再写 3 年，第三卷嘛，10 年内能写出来就不错啦。
其中的主要困难在于，要驾驭这么大的命题，对我自己来说也是不小的挑战，有许多需要学习和思考的地方。为了写好第一卷，我把市面上能买到的计算机书基本上都买遍了，家中因此多了一座图书馆。后来我在这个过程中发现自己受益良多，干脆心一横，发起了一个名为“计算图书馆”的公益项目，由一个 AI 助手“魁星”担任图书管理员，成为每位读者的“外脑”。“计算图书馆”号召对计算感兴趣的读者们坚持“每天阅读一小时”。我希望“计算图书馆”可以在全国遍地开花，成为工程师们的精神家园。而“计算图书馆”的总馆，我希望未来有一天可以找个赞助它的地方，建成全国最大的工程师图书馆—因为恰好发现还真没有！
对于这 3 卷书，我是抱着不留遗憾的心态来写的，是我生命意义的一部分。2017 年，我被 MIT 的 Technique Review 杂志评为全球 35 岁以下的 35 人（TR35），这一荣誉 Facebook的创始人扎克伯格也曾获得过。这让我倍感惶恐，也不断地激励着我必须做点事情来配得上这项荣誉。我之所以能成长到今天，是因为得到过许多人的帮助，消耗了很多社会资源，所以我有必要做一些事情来回馈社会。在公司上班所做的工作再怎么高尚，最终也难以回避主要目的是帮公司赚钱，所以我觉得应该做点工作之外的事情来承担我的社会责任。以我的能力来讲，把毕生所学倾注在书里，留下思想的火种，是我力所能及的事情，何乐而不为？
我的成长经历很特别，我从小就生活在岳麓书院的后院，门牌号是“岳麓书院 44 号”，终日在院子里的一棵亭亭如盖的 200 多岁大樟树下仰望岳麓书院的红墙绿瓦。现在曾经住过的老房子已经拆迁，被圈进了扩建后的岳麓书院里，成为它的一部分。所以，我从小耳濡目染的就是书院的儒家文化，熟读岳麓书院学规，从读小学开始就经常抱着《大学》《孟子》等书在家一知半解地啃读，有着“修身、齐家、治国、平天下”的抱负。北宋张载的横渠四句始终铭刻在我心头：“为天地立心，为生民立命，为往圣继绝学，为万世开太平。”
我立志写这 3 卷书，算是做到了“为往圣继绝学”。希望自己百年之后，能给这个世界留下一点儿东西，也就没有白费社会对我的栽培。从这个角度讲，我定个小目标，希望本书的读者数能比我曾经工作过的公司阿里云①的用户数多一点，本书的寿命能比阿里云的寿命长一点，一两百年后还有人在读，那就善莫大焉了。如果你也觉得理当如此，那就请帮忙把本书推荐给需要它的人，也算是帮我一起完成了这个小目标。
写书的过程是痛苦的，但最终让我下定决心完成它的，是我在工作中不断受到的刺激。我发现大部分人对“计算”的理解是狭隘的，对话很困难。在一家以计算为使命的公司中，依然存在大量不理解什么是计算的人。这些人的傲慢与偏见刺激了我，我一定要把这本书写出来，“弱小和无知不是生存的障碍，傲慢才是”。一些很重要的事情或许正在被多数人遗忘，那么社会还怎么进步？对我来说，不为争论对错，能否实现计算的梦想才是最重要的！
计算机的发明，让机器模仿人的思维过程，是一个巨大的进步，其意义不亚于人类发现了火的用途。促使我投身于这一领域的，是好奇心。我也希望自己的书能够激励更多的年轻人。若是在某个阳光明媚的午后，一个年轻人在草地上阅读这本书时产生了一丝对计算的好奇，对我来说就是值得的。因为说不定那就是下一个图灵呢！
计算，为了可计算的价值！

导论 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