論可計算數：圖靈與現代計算的誕生

前言 // VII

第一章背景
數學的確定性 //004
布爾邏輯//008
數學邏輯//010
邏輯機器//011
保衛數學基礎//012
希爾伯特的方法//014
哥德爾結論//016
圖靈的結論//016

第二章一些不可判定的判定問題

埃米爾•波斯特 // 025
波斯特的對應問題 // 026
一個算法 // 030
含有更多符號的對應問題 // 032
希爾伯特的第 10 個問題 // 034
停機問題 // 036
劍橋的圖靈 // 036

第三章有限自動機
有限自動機 // 043
我們的第一個機器 // 044
字母表和語言 // 046
有限自動機和回答問題 // 049
問題的否定 // 051
忽略圖表中的陷阱 // 052
一些基本事實 // 054
正則表達式 // 057
有限自動機的瓶頸 // 062
同樣數量的0 和1 // 063
平衡括號 // 064
磁帶和配置 // 065
聯系對應問題 // 067

第四章圖靈機

有限自動機 // 043
我們的第一個機器 // 044
字母表和語言 // 046
有限自動機和回答問題 // 049
問題的否定 // 051
忽略圖表中的陷阱 // 052
一些基本事實 // 054
正則表達式 // 057
有限自動機的瓶頸 // 062
同樣數量的 0 和 1 // 063
平衡括號 // 064
磁帶和配置 // 065
聯系對應問題 // 067
圖靈機的例子 // 079
可計算函數和計算 // 088
邱奇—圖靈論題 // 090
計算能力 // 092
多項式時間 // 093
非確定性圖靈機 // 095
不會停機的機器 // 097

第五章其他計算系統
λ積分 // 106
皮亞諾算術 // 108
λ積分和函數 // 109
算術 // 110
邏輯 // 112
標簽系統 // 114
一維元胞自動機 // 119


第六章編碼和通用機器
編碼有限自動機的方法 // 129
通用機器 // 133
設計通用機器 // 136
現代計算機是圖靈機 // 138
馮•諾依曼結構 // 140
隨機存取機器 // 142
圖靈機能夠模擬RAM // 145
其他通用機器 // 147
當我們把〈M〉輸入M的時候會發生什麼 // 149


第七章不可判定的問題

矛盾證明法 // 155
羅素的理發師 // 158
不接納自己的編碼的有限自動機 // 161
不接納自己的編碼的圖靈機 // 162
「圖靈機是否會在自己的編碼上偏離」是不可判定的 // 164
接納、停機和空白磁帶問題 // 166
一個不可計算函數 // 168
圖靈的方法 // 170

第八章康托爾的 對角論證法

基數 // 177
有理數的子集擁有相同的基數 // 179
希爾伯特旅館 // 182
定義不完善的減法 // 184
一般對角論證 // 184
康托爾定理 // 186
實數的基數 // 189
對角論證法 // 193
連續統假設 // 195
計算的基數 // 195
可計算數 // 197
一個非可計算數 // 198
存在可數數量的可計算數 // 199
可計算數無法有效枚舉 // 200

第九章圖靈的遺產

圖靈在普林斯頓大學 // 206
克勞德•香農 // 208
第二次世界大戰 // 209
20 世紀 40 年代的計算機發展 //213
克蘭德•楚澤 // 214
莫奇利和艾克特 // 214
馮•諾依曼 // 215
圖靈測試 // 218
隕落 // 221
道歉和赦免 // 223

拓展閱讀 // 227
注釋 // 231