《论可计算数》书评

【拾光书屋（书评）】上帝的苹果--图灵

第一次知道图灵还是在大学学习计算机基础的时候，当时才知道虽然比尔盖茨靠电脑系统当上了世界首富，但是对电脑真正具有奠基地位的应该是图灵，负责最早的真正意义上的计算机——“曼彻斯特一号”的软件理论开发，成为世界上第一位把计算机实际用于数学研究的科学家。也才知道苹果公司的标志，那个被咬了一口的苹果是为了纪念图灵，1954年6月7日，图灵被发现死于家中的床上，床头还放着一个被咬了一口的苹果。警方调查后认为是剧毒的氰化物中毒，当时图灵41岁。图灵在他的《论可计算数及其在判定问题中的应用》一文中从一个全新的角度定义了可计算函数。他把计算归结为最简单、最基本、最确定的操作动作，用一种简单的方法来描述那种直观上具有机械性的基本计算程序，使任何可执行的程序都可以归约为这些动作。其实这也是计算机二进制算法的原型，当初刚学习二进制的时候确实比较吃力，原码补码反码什么的真的很长一段时间都分不清楚，以0和1两个数字就可以转换成其他各种形式的信息，确实给信息的传递带来了革命性的变化。可以说如果没有图灵的这个贡献，我们现在的计算机技术以及智能设备恐怕都会大不一样。图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究许多判定问题的基础，一般地，把一个判定问题归结为停机问题。所谓停机问题即是：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机？图灵证明，这样的算法是不存在的，即停机问题是不可判定的，从而使之成为解决许多不可判定性问题的基础。在判定问题上的另一成果是1939年提出的带有外部信息源的图灵机概念，并由此导出“图灵可归约”及相对递归的概念。运用归约和相对递归的概念，可对不可判定性与非递归性的程度加以比较。图灵在第二次世界大战中从事的密码破译工作涉及到电子计算机的设计和研制，很可能世界上第一台电子计算机不是ENIAC，而是与图灵有关的另一台机器，即图灵在战时服务的机构于1943年研制成功的巨人机，并且用它出色地完成了密码破译工作。图灵的一生真是充满了传奇，他对计算机的研制，以及对后世人工智能的发展都有重要的影响，可以说只要是学习计算机和人工智能的，图灵就是一座无法绕过的高山，如果不能正确认识图灵为这个世界所做的贡献，就没办法说真正了解人工智能。当图灵因为自身遭遇选择自杀的时候，那个被他咬掉一口的苹果，就如同他自己的一生，也许上帝正是看中了图灵智慧的果实，所以忍不住咬了一口。

【拾光书屋（书评）】了不起的历史人物

图灵这个人之前在电影中了解过，卷福主演的《模仿游戏》，我开始对图灵有了初步的了解。这本书之所以吸引我，是因为这种人为我们的世界作出了无与伦比的贡献，并且他还是一个战争英雄，想像一下，不用上战场，就能打胜仗，是一件多么酷的事。这本书主要是围绕着图灵写的一篇名为《论可计算数及其在判定问题上的应用》的论文分析，是一本很有专业性的书。一般来说，这种学术类的书，尤其是这种使人眼花缭乱的题目都无法让读者顺畅的看下去，但这这本不用担心，的确是高中文化就能够看懂了。图灵发现任何计算都能拆分为一系列简单的步骤，从而造出了图灵机，同时提出了存储程序的概念。也就是说，如果没有这些研究成果，我们现在可能就不会用上电脑，顶多就是停留在手机的科技水平。他的发明是实用的，给我们的计算省下了很多麻烦，从而使得更多的实验和研究能够加速完成。广义相对论与量子力学都诞生于20世纪上半叶，这两大理论都建立在非常复杂的数学基础上，但是图灵的论文中并没有复杂难懂的细节，这不仅仅是一篇学术性论文，而且是一篇充满艺术美感的文章。其实图灵在过程中也经历了挫折，阿隆佐邱奇和图灵都得出了希尔伯特的结论是错误的结论，但是图灵似乎慢了一步，当前者已经发表论文的时候图灵还在写。不过，两人的论证过程完全不同，这也体现了过程的美大于结果的美。本书大致写的是戴维希尔伯特研究出了一个错误理论，图灵来证明它是错误的，并且得到正确的结论。书中介绍了图灵机的诞生和复杂程度，让我们对这台计算机有更深入的了解。还有许多其他的计算方法，书中都有详细的公式。这里还介绍了其他学者的证明，都是与之相关的，能够起到对比的作用。总结来说，这位计算机之父的一生在书面上呈现的是那么的辉煌，可是对于他本人，世界是不公平的。他的那些事迹竟然被埋没了那么就，这是一个多么可爱的人，直到死都值得我们尊敬。但是值得庆幸的是，最终我们还是知道了真像，还给图灵一个他应有的在历史的地位。如此年轻，就有如此造诣，真的是难得的。他是确确实实的天才，这本书是对图灵的致敬，是对于我们了解他的一个非常好的途径。这是一本描写一个了不起的人物的了不起的书！

一个脉络比较清楚的故事

第一章是从无理数讲起的，虽然只是为了带出来后来希尔伯特的第十问题，但是此处却暗含玄机，因为后面核心的主题就是由无理数证明出来的。当然在这一章里面，还引入很多的理论大牛作为背景，以待后面登场。第二章，简单的列举了三个不可判定问题，实际上只详细的讲了第一个post的问题，后面关于希尔伯特第十问题和停机问题只是简单列上了。然后关于这些不可判定问题怎么研究呢？ 先引入了一个功能相对弱一点的机器，叫有限自动机，实际上已经能够做不少的事情了。最起码所有的正则语言就解决了。但是这个机器好像不太够啊，看看更强大的机器， 图灵机，这就是第三章和第四章的内容，里面也提到图灵机所需要解决的对应的问题，就是可计算函数的问题，引出了非确定性图灵机和量子计算机问题，(虽然在数学上看来，非确定性图灵机和确定性图灵机是等价的，但是对于指数时间能够变到多项式时间，这里有个质的飞跃)接下来介绍了图灵机的几个等价计算系统，lambda计算，post系统，元胞自动机。其实本质上上是一样的。接下来是非常重要的，但是也是没有能够深入展开研究的就是关于通用计算机的问题，里面有个很深刻的问题，就是通用计算机可以运行自身的描述(仔细想想，生物系统就是这样演进的，我们生存就是为了构造自身的染色体，这是世界的本质体现之一)接下回到了书的最开始的问题，关于不可判定问题，有了这个机器以后，就可以回答前面的问题了，通过这个机器运行，说明这些问题确实是不可判定的，为什么是这样的呢？黄金的对角线法则出现了，这是整个可计算系统的问题的基石所在(在这里，我们不禁要怀疑，这样的无穷小的无理数，真正是确实能够存在实际的世界中吗？)，最后 一章，相当于电影的最后一幕，故事之后的故事，实际计算机的产生，图灵测试什么的，balabala之类，最后 收尾很有画面感，就是电影最后散场之前的那片字幕，英国政府最后终于承认的他们的错误，英雄得到了应有的尊敬什么的。曲终人散，故事谢幕。