论可计算数

克里斯•伯恩哈特是美国费尔菲尔德大学数学系的一位教授，他从数学的角度入手，研究图灵的可计算数理论及现代计算的诞生，堪称图灵理论最深入的研究者。

1936年，24岁的图灵发表了现代计算领域奠基性的论文《论可计算数及其在判定问题上的应用》。这篇论文堪称图灵一生中最重要的贡献。然而，大众对图灵的了解多停留在破解德国的著名密码系统Enigma，帮助盟军取得二战的胜利上。对于数学家图灵，人们往往知之甚少。 在本书中，作者深入分析了图灵的这篇论文，读者只需具备高中水平的数学知识，即可轻松读懂这篇划时代的论文，了解其对现代计算发展的杰出贡献。正如人工智能之父马文•明斯基所说，图灵的论文有着超乎寻常的简洁性及数学之美。任何希望深入了解图灵及其工作的读者都不该错过这本书！

前 言 // 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