论可计算数：图灵与现代计算的诞生

图书标准信息

• 作者 [美]克里斯·伯恩哈特（Chris Bernhardt） 著；雪曼 译
• 出版社 中信出版社
• 出版时间 2016-09
• 版次 1
• ISBN 9787508666105
• 定价 49.00元
• 装帧 精装
• 开本 32开
• 纸张 胶版纸
• 页数 284页
• 正文语种 简体中文

【内容简介】

　　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