论可计算数
出版日期:2016-9
ISBN:9787508666100
作者:[美] 克里斯•伯恩哈特
内容概要
克里斯•伯恩哈特是美国费尔菲尔德大学数学系的一位教授，他从数学的角度入手，研究图灵的可计算数理论及现代计算的诞生，堪称图灵理论最深入的研究者。
书籍目录
前 言 // 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
作者简介
1936年，24岁的图灵发表了现代计算领域奠基性的论文《论可计算数及其在判定问题上的应用》。这篇论文堪称图灵一生中最重要的贡献。然而，大众对图灵的了解多停留在破解德国的著名密码系统Enigma，帮助盟军取得二战的胜利上。对于数学家图灵，人们往往知之甚少。
在本书中，作者深入分析了图灵的这篇论文，读者只需具备高中水平的数学知识，即可轻松读懂这篇划时代的论文，了解其对现代计算发展的杰出贡献。正如人工智能之父马文•明斯基所说，图灵的论文有着超乎寻常的简洁性及数学之美。任何希望深入了解图灵及其工作的读者都不该错过这本书！
发布书评
精彩书评 (总计3条)
-
第一次知道图灵还是在大学学习计算机基础的时候，当时才知道虽然比尔盖茨靠电脑系统当上了世界首富，但是对电脑真正具有奠基地位的应该是图灵，负责最早的真正意义上的计算机——“曼彻斯特一号”的软件理论开发，成为世界上第一位把计算机实际用于数学研究的科学家。也才知道苹果公司的标志，那个被咬了一口的苹果是为了纪念图灵，1954年6月7日，图灵被发现死于家中的床上，床头还放着一个被咬了一口的苹果。警方调查后认为是剧毒的氰化物中毒，当时图灵41岁。图灵在他的《论可计算数及其在判定问题中的应用》一文中从一个全新的角度定义了可计算函数。他把计算归结为最简单、最基本、最确定的操作动作，用一种简单的方法来描述那种直观上具有机械性的基本计算程序，使任何可执行的程序都可以归约为这些动作。其实这也是计算机二进制算法的原型，当初刚学习二进制的时候确实比较吃力，原码补码反码什么的真的很长一段时间都分不清楚，以0和1两个数字就可以转换成其他各种形式的信息，确实给信息的传递带来了革命性的变化。可以说如果没有图灵的这个贡献，我们现在的计算机技术以及智能设备恐怕都会大不一样。图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究许多判定问题的基础，一般地，把一个判定问题归结为停机问题。所谓停机问题即是：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机？图灵证明，这样的算法是不存在的，即停机问题是不可判定的，从而使之成为解决许多不可判定性问题的基础。在判定问题上的另一成果是1939年提出的带有外部信息源的图灵机概念，并由此导出“图灵可归约”及相对递归的概念。运用归约和相对递归的概念，可对不可判定性与非递归性的程度加以比较。图灵在第二次世界大战中从事的密码破译工作涉及到电子计算机的设计和研制，很可能世界上第一台电子计算机不是ENIAC，而是与图灵有关的另一台机器，即图灵在战时服务的机构于1943年研制成功的巨人机，并且用它出色地完成了密码破译工作。图灵的一生真是充满了传奇，他对计算机的研制，以及对后世人工智能的发展都有重要的影响，可以说只要是学习计算机和人工智能的，图灵就是一座无法绕过的高山，如果不能正确认识图灵为这个世界所做的贡献，就没办法说真正了解人工智能。当图灵因为自身遭遇选择自杀的时候，那个被他咬掉一口的苹果，就如同他自己的一生，也许上帝正是看中了图灵智慧的果实，所以忍不住咬了一口。 -
图灵这个人之前在电影中了解过，卷福主演的《模仿游戏》，我开始对图灵有了初步的了解。这本书之所以吸引我，是因为这种人为我们的世界作出了无与伦比的贡献，并且他还是一个战争英雄，想像一下，不用上战场，就能打胜仗，是一件多么酷的事。这本书主要是围绕着图灵写的一篇名为《论可计算数及其在判定问题上的应用》的论文分析，是一本很有专业性的书。一般来说，这种学术类的书，尤其是这种使人眼花缭乱的题目都无法让读者顺畅的看下去，但这这本不用担心，的确是高中文化就能够看懂了。图灵发现任何计算都能拆分为一系列简单的步骤，从而造出了图灵机，同时提出了存储程序的概念。也就是说，如果没有这些研究成果，我们现在可能就不会用上电脑，顶多就是停留在手机的科技水平。他的发明是实用的，给我们的计算省下了很多麻烦，从而使得更多的实验和研究能够加速完成。广义相对论与量子力学都诞生于20世纪上半叶，这两大理论都建立在非常复杂的数学基础上，但是图灵的论文中并没有复杂难懂的细节，这不仅仅是一篇学术性论文，而且是一篇充满艺术美感的文章。其实图灵在过程中也经历了挫折，阿隆佐邱奇和图灵都得出了希尔伯特的结论是错误的结论，但是图灵似乎慢了一步，当前者已经发表论文的时候图灵还在写。不过，两人的论证过程完全不同，这也体现了过程的美大于结果的美。本书大致写的是戴维希尔伯特研究出了一个错误理论，图灵来证明它是错误的，并且得到正确的结论。书中介绍了图灵机的诞生和复杂程度，让我们对这台计算机有更深入的了解。还有许多其他的计算方法，书中都有详细的公式。这里还介绍了其他学者的证明，都是与之相关的，能够起到对比的作用。总结来说，这位计算机之父的一生在书面上呈现的是那么的辉煌，可是对于他本人，世界是不公平的。他的那些事迹竟然被埋没了那么就，这是一个多么可爱的人，直到死都值得我们尊敬。但是值得庆幸的是，最终我们还是知道了真像，还给图灵一个他应有的在历史的地位。如此年轻，就有如此造诣，真的是难得的。他是确确实实的天才，这本书是对图灵的致敬，是对于我们了解他的一个非常好的途径。这是一本描写一个了不起的人物的了不起的书！ -
第一章是从无理数讲起的，虽然只是为了带出来后来希尔伯特的第十问题，但是此处却暗含玄机，因为后面核心的主题就是由无理数证明出来的。当然在这一章里面，还引入很多的理论大牛作为背景，以待后面登场。第二章，简单的列举了三个不可判定问题，实际上只详细的讲了第一个post的问题，后面关于希尔伯特第十问题和停机问题只是简单列上了。然后关于这些不可判定问题怎么研究呢？ 先引入了一个功能相对弱一点的机器，叫有限自动机，实际上已经能够做不少的事情了。最起码所有的正则语言就解决了。但是这个机器好像不太够啊，看看更强大的机器， 图灵机，这就是第三章和第四章的内容，里面也提到图灵机所需要解决的对应的问题，就是可计算函数的问题，引出了非确定性图灵机和量子计算机问题，(虽然在数学上看来，非确定性图灵机和确定性图灵机是等价的，但是对于指数时间能够变到多项式时间，这里有个质的飞跃)接下来介绍了图灵机的几个等价计算系统，lambda计算，post系统，元胞自动机。其实本质上上是一样的。接下来是非常重要的，但是也是没有能够深入展开研究的就是关于通用计算机的问题，里面有个很深刻的问题，就是通用计算机可以运行自身的描述(仔细想想，生物系统就是这样演进的，我们生存就是为了构造自身的染色体，这是世界的本质体现之一)接下回到了书的最开始的问题，关于不可判定问题，有了这个机器以后，就可以回答前面的问题了，通过这个机器运行，说明这些问题确实是不可判定的，为什么是这样的呢？黄金的对角线法则出现了，这是整个可计算系统的问题的基石所在(在这里，我们不禁要怀疑，这样的无穷小的无理数，真正是确实能够存在实际的世界中吗？)，最后 一章，相当于电影的最后一幕，故事之后的故事，实际计算机的产生，图灵测试什么的，balabala之类，最后 收尾很有画面感，就是电影最后散场之前的那片字幕，英国政府最后终于承认的他们的错误，英雄得到了应有的尊敬什么的。曲终人散，故事谢幕。
精彩短评 (总计4条)
-
看得云里雾里，似懂非懂，糊里糊涂地读完了。一翻一大堆公式就已经露怯了，还是硬着头皮翻完了，总算星星点点采撷了一些精华，对这块有所认知。 -
能再 该通俗的通俗 该延伸的延伸一下就更好了 可计算即可实现 计算机原型理念 -
花一个晚上一口气读完了，这是一本很适合有计算理论基础的人看的书，换而言之，不是特别适合对于有限状态机， 对角线法则一无所知的人。这本书最大的好处在于条理比较清晰的从数学方面描述了整个从第十问题到通用图灵机深化过程，并介绍了等价的lambda、post等系统，很不错。推荐喜欢的人一读。 -
不知道英文原版如何，反正中文翻译之烂也是没谁了，Lambda积分、差异引擎这种无厘头的东西都出来，我还能说些什么？