計算

導論 ....................................................................................................................................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