第一章 背景 4
数学的确定性 4
布尔逻辑 8
数学逻辑 10
逻辑机器 11
保卫数学基础 12
希尔伯特的方法 14
哥德尔结论 16
图灵的结论 16
第二章 一些不可判定的判定问题 25
埃米尔·波斯特 25
波斯特的对应问题 26
一个算法 30
含有更多符号的对应问题 32
希尔伯特的第10个问题 34
停机问题 36
剑桥的图灵 36
第三章 有限自动机 43
有限自动机 43
我们的第一个机器 44
字母表和语言 46
有限自动机和回答问题 49
问题的否定 51
忽略图表中的陷阱 52
一些基本事实 54
正则表达式 57
有限自动机的瓶颈 62
同样数量的0和1 63
平衡括号 64
磁带和配置 65
联系对应问题 67
第四章 图灵机 79
图灵机的例子 79
可计算函数和计算 88
邱奇一图灵论题 90
计算能力 92
多项式时间 93
非确定性图灵机 95
不会停机的机器 97
第五章 其他计算系统 106
λ积分 106
皮亚诺算术 108
λ积分和函数 109
算术 110
逻辑 112
标签系统 114
一维元胞自动机 119
第六章 编码和通用机器 129
编码有限自动机的方法 129
通用机器 133
设计通用机器 136
现代计算机是图灵机 138
冯·诺依曼结构 140
随机存取机器 142
图灵机能够模拟RAM 145
其他通用机器 147
当我们把〈M〉输入M的时候会发生什么 149
第七章 不可判定的问题 155
矛盾证明法 155
罗素的理发师 158
不接纳自己的编码的有限自动机 161
不接纳自己的编码的图灵机 162
“图灵机是否会在自己的编码上偏离”是不可判定的 164
接纳、停机和空白磁带问题 166
一个不可计算函数 168
图灵的方法 170
第八章 康托尔的对角论证法 177
基数 177
有理数的子集拥有相同的基数 179
希尔伯特旅馆 182
定义不完善的减法 184
一般对角论证 184
康托尔定理 186
实数的基数 189
对角论证法 193
连续统假设 195
计算的基数 195
可计算数 197
一个非可计算数 198
存在可数数量的可计算数 199
可计算数无法有效枚举 200
第九章 图灵的遗产 206
图灵在普林斯顿大学 206
克劳德·香农 208
第二次世界大战 209
20世纪40年代的计算机发展 213
克兰德·楚泽 214
莫奇利和艾克特 214
冯·诺依曼 215
图灵测试 218
陨落 221
道歉和赦免 223
拓展阅读 227
注释 231