图灵的远见
豆瓣
Turing's Vision: The Birth of Computer Science
[美] 克里斯·伯恩哈特 卢斌 / 张小敏
简介
图灵，一个计算机界家喻户晓的名字。1936年，他24岁时，发表了一篇题为《论可计算数及其在判定问题上的应用》的论文，由此奠定了他在计算机领域的地位。
本书为想要了解图灵所构建的现代计算机基础理论的深邃思想的读者而写。书中从图灵的理论基础出发，逐步推导出那些出人意料的结论，并尝试将图灵的工作置于其自身历史脉络中理解它。为此，本书将谈及图灵论文发表前后的历史背景和发展。
读者无须深厚的数学背景，高中数学知识足矣，但需要一定的悟性和努力。本书值得细读，一些章节可能需要反复咀嚼。毕竟，图灵所阐述的并非关于计算的浅显之谈，而是深邃且突破直觉的洞见。
目录
第一章 背景
数学的确定性
布尔逻辑
数理逻辑
确立数学基础
希尔伯特的方法
哥德尔的研究成果
图灵的研究成果
第二章 不可判定的判定问题
埃米尔·波斯特
波斯特对应问题
希尔伯特第十问题
停机问题
剑桥时期的图灵
第三章 有限自动机
引言
有限自动机
我们的第一台机器
字母表和语言
有限自动机和回答问题
略去图示中的陷阱
一些基本事实
正则表达式
有限自动机的局限性
磁带和配置
与对应问题的联系
第四章 图灵机
图灵机实例
可计算函数与计算
邱奇－图灵论题
计算能力
永不停机的图灵机
第五章 其他计算系统
λ演算
标签系统
一维元胞自动机
第六章 编码与通用计算机
有限自动机编码方法
通用机器
设计通用计算机
现代计算机即通用计算机
冯·诺伊曼架构
随机存取机
用图灵机模拟RAM
其他通用机器
将〈M〉输入M会发生什么？
第七章不可判定问题
反证法
罗素的理发师悖论
不接受自身编码的有限自动机
不接受自身编码的图灵机
“图灵机输入其自身编码后发散吗？”是不可判定的
接受、停机和空白带问题
不可计算函数
图灵的方法
第八章康托尔对角论证法
基数
等势的有理数子集
希尔伯特旅馆
减法定义不清晰
一般对角论证法
实数的基数
对角论证法
连续统假设
计算的基数
可计算数
一个不可计算数
可计算数的可数性
可计算数不可有效枚举
第九章 图灵的遗产
图灵在普林斯顿
第二次世界大战
20 世纪40年代计算机的发展
图灵测试
图灵逝世
道歉与赦免
拓展阅读
参考文献
