《计算》吴翰清 | PDF下载|ePub下载

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