悦读人生

标题: 图灵的秘密 - 书评 [打印本页]

作者: 连接你我他 时间: 2013-6-12 23:53
标题: 图灵的秘密 - 书评
　　图灵机是英国数学家阿兰图灵提出的一种抽象计算模型，本书深入剖析了图灵这篇描述图灵机和可计算性的原始论文《论可计算数及其在判定性问题上的应用》。书中在详解论文的同时，也附带了大量的历史背景资料、图灵 ...

此主题为自动生成的书评内容贴，书籍链接地址: http://www.dothinkings.com/forum.php?mod=viewthread&tid=20559

书评内容会自动聚合在本帖中

作者: Silver 时间: 2013-7-24 07:48
　　鉴于是科普向就不发博客了..
　　
　　微积分发明后, 全欧洲的数学物理学家们疯狂的享受这种方法带来的方便. 那时的数学是带有浓厚的应用目的的, 几乎所有数学都是为解物理问题而存在, 人们用微积分求解物体间的作用, 天体的运动, 却未顾及方法的严谨性. 即使有怀疑的声音, 人们还是随意对无穷进行运算, 对级数进行求和. 直到这股声音越来越大, 19世纪前中期, 以Weierstrass为代表的严格派, 将所有微积分知识用严格的数学定义给出, 包括极限的epsilon-delta定义, 级数的收敛与一致收敛的区别. 至此,  分析学有了严格基础, 人们认识到严格的必要性.
　　
　　公理的出现可以追溯到Euclid的几何原本, 其第五公设一直让人不爽. 无数人试图证明它, 其中有不少人甚至已经在努力中触到了非欧几何的大门. Gauss就是最早的这些人之一, 但以他当时显赫的地位, 依然不敢深入研究发表其结论. 勇士Lobachevsky站了出来, 宣传非欧几何, 给19世纪中叶带来了怀疑公理的思想风暴. 天才Riemann真正看清楚了这一切, 自<论奠定几何学基础之假设>这次演讲后, Riemann将几何统一到了Riemann几何的框架内, 让人们看到其实一直以来, 旧的公理所决定的几何只是一些微不足道的特例. 当然, Riemann几何真正得到应用是在Einstein之后, 他能够在19世纪中期就得到认可, 表明那时的数学已渐渐独立于物理世界, 开始变得抽象了.
　　
　　另一个不得不提的人是天才Galois, 在他死后20年, 他的群论这一伟大想法为世人所知, 从此初等算术走向了现代的代数. 通过抽象化, 人们能够跳出对具体数学对象的研究, 而得以研究对象的群体: 它们的结构, 变化, 甚至群体的运算.
　　
　　至此,十九世纪中后期, 代数, 几何, 分析这三大根基已奠定, 严格化, 公理化, 形式化思想的重要性被认可, 数学即将赢来根本上的变革.
　　
　　引发这场风暴的是Georg Cantor, 人类历史上第一个理解了无穷的人. 他告诉人们, 实数的无穷与整数, 有理数, 代数数的无穷有着本质上的不同, 这得到了许多人, 包括他的老师Kronecker, 数学大师Poincare的反对. 他的思想撼动了许多基础的数学哲学观念, 包括定义实数存在的意义,  对实数连续性的理解.
　　
　　Cantor为此给出的第二个证明, 就是传说中的Diagonalization, 对角线法. 其思想非常简单, 至多只需要如今的初中水平就可以看懂其证明.
　　对角线一词, 原本是指证明中寻找"第k个数的第k位", 画出了一条对角线. 但其本质是"将一个变量放在两个意义不同的位置", 或者更深入的描述为"将一个函数作为自己的参数". 之后这一类的方法都被称作对角线法, 尤其是被Godel与Turing所采用.
　　
　　公理化还在继续发展. Cantor之后, 19世纪初Russell悖论的出现和解决使得集合论得到了更加严密的公理化. 这时, Hilbert振臂一呼, 提出了Hilbert's Program: 我们要将数学彻底的形式化, 并且要证明它的公理是独立的, 且系统是完备的, 一致的, 可判定的.
　　
　　Hilbert开始研究逻辑, Godel与Turing的工作无疑都受到了这个时期Hilbert工作的影响. 当Hilbert自信满满的退休后不久, 第二个震惊世界的人, Kurt Godel, 发表了Godel1931, 声称:
　　
　　算术系统不可能同时是完备且一致的.
　　(推论)算术系统的一致性不能在系统内证明.
　　
　　Godel的证明中关键一步也是对角化: 他将一个命题的描述作为这个命题的变元, 构造出了自我矛盾的命题.
　　
　　此时, 完备与一致的问题已被解决, 对于"真"的可判定性也已经不可能了. Hilbert的唯一希望在于, 对于"可证明"的命题, 是否可以有方法加以判定.
　　
　　1936年, Turing与Church独立的粉碎了Hilbert计划.
　　
　　-----------------------------------好像历史有点多-----------------------------
　　
　　Turing1936这篇文章, 也即本书的内容, 大致可概括如下:
　　
　　首先定义出了一种机器, 在纸袋上根据其方格中的符号及自己的状态执行固定的操作, Turing称能被这种机器计算的数叫做"可计算数".
　　
　　Turing证明了这台机器的能力: 它能计算的数超级多, 基本包括我们所能用得到的所有数, 但可计算数却是可数的, 只是实数中的一小部分. 可数性的证明依赖于将机器的有限描述映射到整数上.
　　
　　Turing构造的证明了一台机器可以模拟另一台机器的运行.
　　
　　如果仅仅到此, Turing提出的计算模型及可计算数的概念, 已经足够伟大了, 然而精彩的还在后面.
　　
　　Turing证明了这台机器不能做什么: 他不能不加模拟的预测另一台机器的行为, 例如是否停机.
　　
　　这一证明依然用到了对角线方法. 事实上, Turing正是从"将Cantor对角线证明应用于可计算数上"这一方法出发, 给出了这一命题的第一个证明. 随后他又给出了一个更为直接的证明, 其中他继续使用对角线思想, 将一个机器作为这台机器自己的输入, 构造出了矛盾.  因此他才会说"得到了与Godel相似的结果".  另外, Church的lambda calculus也利用了对角线法, 将lambda函数作为自身的参数.
　　
　　Turing试图说服人们, Turing机的思考能力与人是相同的, 或者至少是与人的数学推理是相同的.
　　
　　最后, 作为一个其思想的应用, 他证明了谓词演算系统中的命题可解判定蕴含了停机问题可判定. 因此否定了Hilbert判定性问题.
　　
　　--------------------------------这本书讲了这么多东西--------------------------
　　
　　Cantor, Godel, Turing, 探索了无穷, 可知, 可解的极限. 这是近100多年来人类最深刻且严谨的哲学思考.
　　
　　最终两人精神病, 一人自杀, 即使如此, 他们的工作也不能不让人心生崇拜.
　　
　　我想拿@玑衡的一篇我极爱的文章<面对面的办公室>的最后两段结尾:
　　
　　那时候，普林斯顿大学的数学楼和物理楼有一座天桥相连。爱因斯坦教授精神很好，每天穿梭天桥许多次在数学和物理之间来回奔跑。那是一个离我们遥远的伟大的科学年代，基础学科之间有许多天桥和地道相通，科学家从一个学科开始挖凿，最后挖到另一个学科的金矿。希尔伯特在世纪之初的著名演讲为几十年内的数学突飞猛进提供了指路牌，爱因斯坦1915年的广义相对论带来了一个崭新的宇宙观，一个个新化学元素接踵而至犹如上天的惊喜。集合论不过半个世纪，拓扑学才三十几年，量子力学二十年……在这个幸福的基础科学的时代，犹太人冯诺伊曼和同性恋图灵坐在面对面的办公室里，这两种备受歧视的身份将困扰他们一生，可是此时，他们心无旁骛只有一个愿望：做一个数学家、数学家、数学家。
　　
　　幸福的数学家。

作者: shanxi 时间: 2013-7-25 07:46
　　单纯的直觉终究不能令人信服，数学家讲究的是逻辑和证明。而要证明通用图灵机的存在，最直接的方法莫过于直接给出一个通用图灵机的实例。这并不简单，如果读者想尝试一下的话，我建议先尝试构造一个能做二进制加法的图灵机。为了降低难度，可以假设纸带上有第三种符号，表示空白，但即使如此，要构造一个能做加法的图灵机，远比想象中的困难。可想而知，通用图灵机的构造肯定更为复杂繁琐。即使是图灵，他在一开始给出的构造也是有问题的，而这些问题甚至在后来的勘误中也没有成功修正。比构造更麻烦的是证明给出的图灵机的确是一台通用图灵机，在图灵解决希尔伯特可判定性问题的论文中，有关通用图灵机的构造和证明占了相当大的篇幅。这部分非常繁复琐碎，而且其中还有错误，如果细细研读的话，绝对有诱发剧烈偏头痛的危险。
　　
　　幸运的是，无论细节多么复杂，图灵的想法还是被逻辑学家们接受了。一旦领会到图灵机的能力，接受了通用图灵机的构想，再检查几个能完成基本任务的图灵机之后，大部分数学家都会认为通用图灵机的确存在，尽管他们并不一定会细看图灵的详细构造。而现代电子计算机的发展，更是验证了通用图灵机的存在：每一台电脑都相当于一台通用图灵机。

作者: Marius 时间: 2013-8-4 11:51
　　《图灵的秘密》是关于图灵1936年那篇开创性论文的解读，内容很多很难，需要的背景知识包括数理逻辑，lambda演算，以及一些基本的数论。读完的笔记也许都会比原书多，这里想简洁或者宏观性地谈谈几个主角之间的“故事”。
　　
　　实际上说争论更准确。
　　
　　初（我目前所知道的），大神莱布尼兹有两个及其宏大，甚至伟大的想法（若能实现，即使代价是将微积分其拱手让给牛顿，莱布尼兹绝对认为也值）：
　　
　　1. 创造一种通用语言可以描述所有的数学问题
　　2. 找到一种解决用这种语言描述的问题的方法
　　
　　“元”语言似乎是第一个问题的方向，比如集合论和谓词逻辑。第二个问题更难，从某种哲学的角度来看，问题的表述与问题的解答是相关的 —— 描述好，答案自然好得出（这种观点被有限的事实证实，但显然无法被证明正确。实际上，这就像人身体吸收营养一样：身体无法直接吸收大白菜或者蛋白质，而是需要先分解，将其转换成为身体能够吸收的物质。对于知识或者想法也是一样，你从阅读中获得的只能成为信息，或者说是某种符号排列，想让它们变得对自己有意义，需要主动的思考，或者准备将是同构 —— 写作正是同构最有效的手段。理解就是变得有意义，一串对自己有意义的符号需要自己对原符号的主动重新的编排，好的编排就是好的写作，就是好的理解。写作是记忆，更是理解。），而最好的描述可以对其进行有限的，近乎机械式的转换而得到结果。这就是这个想法的伟大之处。
　　
　　这也是我们对“智慧”的终极拷问。这种自动推断答案的系统是否真正具备人类的智能？就像几个世纪前人们喜欢问人脑是内燃机一样，也许几个世纪以后的人会用同样的眼光看我们。类似的问题有类似的两派观点：
　　
　　1. 这种完全不知所谓的，只知道机械地进行符号操作的机器，虽然最终得出了答案，但它本身是机械的，根本不具备人类的智慧。
　　2. 你敢确定，人类的智慧不是类似的符号替换操作。
　　
　　在电脑之前我们认为象棋是人才能做的事情，是人聪明智慧的象征，但随着计算机技术的发展打败最厉害的人类已经不需要最厉害的计算机了。这也许不是说明象棋很简单，而是说明人类的智慧多么幼稚。我们很难将智能与简单的符号处理联系起来，也许因为它们根本就不是一回事，也许我们根本就没发现。大神们试图利用这套符号系统解决具体的数学问题，这个至少比象棋更能印证人类智慧的活动，真是伟大的尝试！
　　
　　但是，一般而言，伟大的另一层含义是不可能。
　　
　　希尔伯特继承了莱布尼兹的光荣传统，甚至接近了最终那个伟大的答案，然而就在一切似乎都已完满的前夜，哥德尔，一个在哥廷根上空徘徊的幽灵出现了。他认为 —— 其实是证明了通过1)创造出来的系统中，存在无法用2)解决的问题。鱼和熊掌不可兼得就是这个意思。具体而言，哥德尔证明下面两条定理：
　　
　　1. 任何相容的形式体系，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中既不能证明也不能否证的命题（即体系是不完备的）。
　　2. 任何相容的形式体系，只要蕴涵皮亚诺算术公理，它就不能用于证明它本身的相容性。
　　
　　如果说哥德尔是给希尔伯特的首次致命打击，那么图灵便是第二次致命打击，图灵认为 —— 其实也是证明了，不存在通用的过程来判定任一命题在一阶谓词逻辑系统是否可证。如果想象这四位主角之间的穿越体对话，可能会是这样：
　　
　　莱布尼兹：我有一个想法，不，事实上是两个，尽管本质上可能是一个：一套完美的语言系统能陈述并解决所有数学问题。
　　
　　希尔伯特：我完全认为你不是在说疯话，我几乎快要实现了你的想法，也许只差那么一点点了…，形式化公理系统不是人类的发明，而是上帝的发明，人类的发现。
　　
　　　哥德尔：希总，其实情况不是酱紫的…，这个系统中存在不能被证明的命题。
　　
　　希尔伯特：你说什么！？
　　
　　　哥德尔：…
　　
　　希尔伯特：… 好吧，你的论文没错。尽管如此，我们一定有能找到这种变态命题的方法，我的意思是，你懂的，一般性的方法。这样就能识别出这样的变态问题。
　　
　　　　图灵：没有。我是说，没有这样的通用方法。
　　
　　希尔伯特：wtf!!
　　
　　　　图灵：如果我们朝好的方向看，有一类问题是完全可以解出的，而且有通用解法。这样，莱两点至少部分被解决了。
　　
　　莱布尼兹：我部分接受，剩下的，家祭无忘告乃翁。
　　

作者: 无敌北 时间: 2013-8-19 02:25
　　这本书对我来说真的很难读懂。看到大段大段的各种稀奇古怪的数学符号我就发求。但是这并不妨碍我从另一个角度来重新了解了图灵、数学、计算机….去年的时候曾听过Jeff讲过的一个session:《世界及宇宙的终极答案》。我敢确定至少一半的内容都是来自这本书。
　　图灵在论文中描述了一个想象出来的机器，用来论证数理逻辑中的一个问题，论文题目叫:<论可计算数及其在判定性问题中的应用>（On Computable Numbers, with an Application to the Entscheidungsproblem）。这个想象出来的机器被后人成为图灵机。
　　
　　
　　图灵在论文中让图灵机使用二进制，仅是觉得方便论证。后来研制的计算机有的使用十进制，有的使用二进制，直到冯诺依曼发表了一片论文论述了计算机使用二进制的可行性与优势后，二进制逐渐成为标准。
　　
　　如果一个集合可以与自然数意义对应起来，那么我们可以说这个集合是可数的。
　　正整数和偶数个数那个多些？答案是一样多。因为他们都是可数的。
　　那么有理数和无理数那个多？答案是无理数。因为无理数是不可数的。
　　
　　无理数属于实数的一部分。所以实数也是不可数的。这可以用对角线法来证明。
　　这是一个反证法。
　　我们假设实数是可数的。那么将0和1之间所有的实数都按照从小到大的顺序列出来。然后我们取第一个数的第一位、第二个数的第二位、第三个数的第三位…..即取对角线的数组成一个新的数。然后对这个数的每一位都加1,如果该位的值是9再加1后变成0。我们看看这个数是不是在已经枚举出来的列表中。列表中的第一个不是它，因为它比第一个数的第一位大1，第二个数也不是它，因为它比第二个数的第二位大…….这样遍历了整个列表发现这个新的数并不在列表中，也就是说我们根本无法将0和1之间的所有实数列举出来，因为我们总可以通过这个方法来找到一个新的实数。
　　
　　实数是无穷的。我们可以这样理解，世界上有数不清的数字，我们恰好找到了一些，并给它们起了一些名字，如整数，实数，有理数，但还有更多的数我们并不知道它们的存在，就算发现一个也算是意外。
　　
　　
　　一个图灵机无法通过程序判断另一个图灵机在限定的时间内停机。停机问题说明了图灵机的局限性，这也被很多人作为程序无法没有bug的借口。你无法写一个程序，来判断一段程序中是否没有任何bug。
　　
　　我们可以预知未来吗？根据图灵机理论，如果我们可以用确定的不含糊的步骤来描述出宇宙的发展，那么我们就可以将其作为输入到图灵机，得到未来。问题是我们如果要构造这个输入，差不多等于构造了一个新宇宙。
　　

作者: beride 时间: 2013-8-19 03:43
　　之所以没有选力荐不是因为书不够好，而是这本书对于大部分人来说很难全部读懂，我算是一个数学爱好者，虽然自己数学能力已经完全处于大学以下水平了。读这本书需要很多思考，毕竟他不是传记，不是故事，而是对一个完整的知识体系的详尽分析和解读，多谢作者在前面写了大量的补习知识，让读者可以先预热一下，而后一章一章的详细分析，就需要有足够的耐心和愿意深入思考才能跟上作者的思路以及论文里的细节。反正我看到子函数之后就开始觉得不容易了。后面已经开始速读之后再回头细看了。
　　
　　好东西，要耐心阅读。

作者: 飞林沙 时间: 2013-9-2 09:53
　　其实这本书我并没有读完，因为到了第二部分，即使有了作者的解释和注释，图灵的论文也确实超出了我的能力范围之外了，把“可计算函数”一章的前半部分仔细读了三四遍之后还是读不懂之后，我不得不放弃了。但是这并不影响我仍然给这本书打五星力荐。
　　
　　先说这本书，我想如果没有Charles出这本书，没有苦口婆心地几乎是一行一行地去讲解图灵的论文，几乎没有人，至少没有一个程序员会去回过头来看这篇已经几十年前的充斥着自定义符号，甚至连数学符号都少见的论文。那么从这个角度来说，作者已经做出了极大的贡献。
　　
　　然后说图灵的论文，我想包括我在内，在读这本书之前，至少有90%的程序员只是听说过图灵，也许知道图灵测试和图灵机，但是并不知道图灵的论文中究竟写了什么内容，究竟在论证什么？当然，判定性问题，我更愿意把它归结到数学哲学的范畴，对于大多数程序员而言，数学和他们的关系都不大，更不用说数学哲学了，而对于一些经常和数学打交道的程序员来说，我想就我自身的经验，也完全不需要学什么数学哲学这类的东西。但是就像网上辩论数学的作用常说的，也许数学对大家的作用在于开阔思路和逻辑思维。
　　
　　在这里，我并不想去辩论程序员到底需不需要学数学，如果你觉得我不需要学数学，那么你可以把这本书束之高阁；如果你觉得学数学只是为了工作，例如算法啊，数据挖掘之类，那么你也可以把这本书束之高阁。如果你是真的喜欢数学这门学科，想感受数学之美，想通过数学来锻炼自己的逻辑思维，想培养自己对数学的兴趣，那么我郑重推荐这本书，而且是这本的纸质书，因为实在是需要反复地前后翻阅，电子书确实在这点上并不方便。
　　
　　最后，特别希望大家读完之后可以帮我把判定性问题的部分讲一讲，至少是大家一起讨论一下，因为我确实没有读懂。至于地址么。。。就在这篇书评下把。

作者: Entele 时间: 2013-9-9 00:12
　　今年是图灵诞辰100周年，全世界都在发起纪念图灵的活动，接连不断的纪念活动把这位孤僻、低调而伟大的天才置于聚光灯下，而近日霍金、马丁里斯等11位著名科学家致函英国首相卡梅伦，再次要求为图灵1954年的同性恋罪行平反。图灵的一生如此短暂，为什么却迸发出了这么耀眼的光芒，乃至100年后还有如此大的影响？
　　图灵的研究跨越多个领域，作为计算机、人工智能、复杂性理论等问题的开山鼻祖，功不可没，其中《论可计算数及其在判定性问题上的应用》一文可谓计算机领域的奠基之作，文中提出的图灵机模型为计算机的问世奠定了理论基础，本书就对图灵这篇描述图灵机和可计算性的原始论文进行了深入剖析。人是不是仅仅是一台计算机而已？这是图灵始终关心的问题，在之后的《计算机和智能》一文中图灵提出关于机器思维的问题和图灵测试的概念，至今仍有广泛的意义和影响。本书围绕图灵在计算、人工智能等主题上的贡献结合自己的思考做了延伸性的介绍，开阔视野，发人深思。
　　从利兹大学纪念图灵的网站上，人们可以看到图灵涉猎领域之广，影响范围之大。以目前人工智能、心理学、神经科学、心灵哲学等交叉领域最热门的意识研究相关问题为例，在今年6、7月份在加拿大蒙特利尔举办的纪念图灵的“意识的进化和功能”会议上，就吸引了Roy Baumeister等著名心理学家，Antonio Damasio、Wolf Singer等著名神经科学家以及Dennett、Searle等著名哲学家，大家齐聚一堂，畅所欲言，既是为了缅怀这位百年前诞生的天才，也是继续沿着他所奠基的道路探寻求索，永不停止地去追问“计算的本质是什么”“思维的本质是什么”“意识是什么”“宇宙是不是一台巨型计算机”、、、
　　除了在计算理论领域做出的卓越贡献，图灵还学以致用，小试牛刀，在二战期间破译了德军密码，这为盟军的胜利立下汗马功劳，同时他文武双全，是位奥运级别的马拉松健将，图灵的一生是解谜的一生，与谜相伴，他绞尽脑汁去解开计算之谜，思维之谜，也许还有那无法言说的爱情之谜，但同时他本身就是一个迷，在创造力正值巅峰之时突然离世，天妒英才，让人唏嘘。
　　了解图灵的秘密，走进图灵谜一样的思想世界，就从《图灵的秘密》这本书开始吧。

作者: 小凤 时间: 2013-9-26 05:44
　　图灵是一个有爱、但遗落了爱的人，普通而悲情，坚定而脆弱。
　　
　　就像文章所言：“图灵将人与机器关联了起来”，这是当今人们记住他的最大原由。实际上，图灵的成就实在是影响巨大，任何赞美之词都可以毫无保留地送给他。
　　
　　图灵的归宿是如此悲情，为助力人类由工业时代迈向信息时代而做出卓越贡献的一代伟人，最终如此殒落，1万年后仍会让后人唏嘘不已。
　　
　　任何一个码农，都应该好好认识、了解图灵，这本《图灵的秘密》，在阿兰·图灵诞辰百年之际由图灵出版中文版，意义凸显。《图灵的秘密》带你了解图灵的生平及影响、创造和成果，作者是大牛Charles Petzold，大牛同样也是图灵崇拜者，在Charles Petzold的描述中，将带你穿越图灵的秘密，并长久驻足、瞩目于揭开了秘密的图灵世界。
　　
　　任何的伟大性创造、创新，都来自于不平凡的性格与经历，图灵为人类带来了巨大贡献，人们却把他推向绝路。真心希望，有谁能轻轻拿走那个苹果，如果图灵能像正常人那般活到80年代，相信他对世界的贡献将更多。生命只有一次，但多么希望可以重来。
　　
　　本文由2gua老师发表在图灵社区的文章节选
　　http://www.ituring.com.cn/article/17973

作者: 小凤 时间: 2013-10-7 06:47
　　读书写读后感或者微博转发就有机会获得水杯和图书哦！赶快来参加！
　　地址：http://www.ituring.com.cn/activity/17811
　　
　　
　　英国著名数学家、逻辑学家，阿兰图灵（1912—1954）是计算机和计算机科学的理论奠基人。他出生于1912年6月23日，被称为计算机科学之父、人工智能之父，提出了“图灵机”和“图灵测试”等重要概念。今年是他诞辰100周年。为了纪念他对计算机科学的伟大贡献，从年初到年底世界计算机界举行了一系列的纪念活动，并称2012年是图灵年（Alan Turing Year）。
　　
　　　　为此，图灵教育今年也特别推出了一本《图灵的秘密》并谨以此书纪念图灵诞辰百年，这本书深入剖析了图灵这篇描述图灵机和可计算性的原始论文《论可计算数及其在判定性问题上的应用》。书中在详解论文的同时，也附带了大量的历史背景资料、图灵的个人经历，以及图灵机对于人们理解计算机、人类意识和宇宙所产生的影响。适合所有计算机科学专业的学生、程序员或其他技术人员，同时也适合欲了解图灵生平及其构建图灵机的思维的读者阅读。
　　
　　　　学习计算机有关专业和学科的学生，不应该不知晓图灵，在这个领域更应该出一个获得图灵奖的中国人！但令我们中国人感到遗憾的是我们国内培养成长的专家至今还没有一个在获奖名单中出现，获图灵奖的唯一一位华人是2000年得主姚期智博士(Chi-Chih Yao)。
　　
　　　　很多人都在思考：为什么我们培养不出高水平的能获得诺贝尔奖和图灵奖的科学家？今年在诺贝尔文学奖上，我国的著名作家莫言，一雪前耻，为我国夺得了诺贝尔文学奖，相信在不远的将来图灵奖也将会在中国诞生！
　　
　　　　现在《图灵的秘密》终于出版上市了，我们特举办一届“民间图灵奖”以鼓励广大计算机有关专业的人士等早日获得真正图灵奖，为国争光！

作者: 小凤 时间: 2013-11-11 13:49
　　阿兰图灵（1912—1954）是英国数学家、逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。为纪念他在计算机领域的卓越贡献，美国计算机协会于1966年设立图灵奖，此奖项被誉为计算机科学界的诺贝尔奖。
　　
　　　　　　　　　　
　　
　　　　在数字计算机出现之前，阿兰图灵就预想了它们的功能和通用性……也证明了哪些事是计算机永远做不了的。对于计算机科学专业的学生、程序员或其他技术人员等，都应当了解一下图灵的生平以及他构建图灵机的思维过程，恰逢图灵诞辰百年之际，《图灵的秘密》恰好带你了解他的生平、他的思想以及他的论文。
　　
　　　　《图灵的秘密》由Windows编程大师Charles Petzold耗时多年编写的这本书剖析了现代计算机原理开山之作、阿兰图灵流芳百世的论文 “On Computable Numbers, with an Application to the Entscheidungsproblem”。图灵在其中描述了一种假想的计算机器，探索了其功能和内在的局限性，由此建立了现代程序设计和可计算性的基础。这本书也像是一本小说，行文间穿插讲述了图灵的成长经历和教育背景，以及他跌宕起伏的一生，包括破解德国恩尼格密码的传奇经历，他对人工智能的探索，他的性取向，以及最终因同性恋的罪名而在41岁时自杀的悲惨结局。全书完整揭示了阿兰图灵非凡、传奇而悲剧的一生，是了解图灵的思想和生平的极好著作。
　　
　　　　　　　　　　　　
　　
　　精彩样章抢先看：
　　
　　第四章：图灵的学业
　　
　　阿兰·图灵10岁时得到一本埃德温·坦尼·布鲁斯特所著的《每个儿童应该知道的自然奇观》。图灵后来说，这本书开启了他的科学视野，并对他理解人与机器之间的关系产生了更深刻的影响。“显然，人体也是一台机器。”那本书对此解释道：
　　
　　它是一台极其复杂的机器。虽然比任何手工制作的机器都要复杂千万倍，但其本质上仍然是一台机器。有人曾将人体比作一台蒸汽机，但那时我们还不太了解它的工作原理。现在，我们会把它比喻为一台内燃机，就像是汽车、轮船和飞机的内燃机一样。
　　20世纪初，“人体是机器”的想法被看成是非常无知的，就像现在儿童读物里很幼稚的想法一样。但事实并非如此。在阿兰·图灵出生前200年，法国医生兼哲学家朱利安·奥佛雷·拉·美特利（1709—1751）在其1747年的争议性作品L’Homme Machine（《机械人》）中，毫不掩饰地描述了人体甚至思维的机械般的工作机制。阿兰·图灵从小就觉得自己的身体也是一台机器，后来也因探索机器和人类间的联系而被世人铭记。
　　
　　阿兰·麦席森·图灵于1912年6月23日出生在伦敦帕丁顿的疗养院里。他的父亲曾在印度公务署为英帝国效力，母亲出生在马德拉斯，外祖父是一位在印度修建桥梁和铁路而赚了大钱的工程师。1907年，图灵的父母在一艘从印度到英国的船上相遇，同年他们在都柏林结婚。1908年年初，他们回到印度。阿兰是他们的第二个男孩，他母亲1911年在印度怀上了他，但他出生在英国。
　　
　　在幼年，阿兰和他的哥哥约翰被留在英国，由一对退休夫妇照顾，而他们的父母住在印度，这在当时很常见。1922年，阿兰进入肯特的哈兹勒赫斯特预备学校学习。他最初的兴趣是地图、国际象棋和化学。 1926年，他被一所最古老的英国公立学校舍伯恩录取。图灵在舍伯恩第一学期的第一天被大罢工所阻，不能乘火车去学校。于是，阿兰决定骑车60英里上学，这一壮举被当地的报纸所报道。
　　
　　在舍伯恩，阿兰没能与其他男孩打成一片。他害羞、孤独，似乎总是衣衫不整、墨迹斑斑。“他的所有特征都容易成为笑柄，尤其是他那害羞、犹豫、尖细的声音——不完全是口吃，而是吞吞吐吐，就像在等待一个复杂的程序将他的想法转化成人类语言一样。”他本可以在学习上表现优异而弥补自己的不足，但事实并非如此。只有在数学上，他才表现出一些智力天赋的端倪。
　　
　　到了1929年，阿兰开始着迷于《物理世界的自然》（1928）一书。这是一本广为流行并极具影响力的书，由剑桥大学天文学家亚瑟·埃丁顿爵士所著，书中探讨了相对论和量子理论的新科学所带来的影响。阿兰同时和一个名为克里斯托弗·莫科姆的同学交往密切，他和阿兰在科学和数学上有着共同的兴趣，而且出生在一个比阿兰家更有意思并兼具科学气氛的家庭。克里斯托弗的外祖父是约瑟夫·斯万爵士，他在1879年发明了白炽灯泡，独立于爱迪生的发明。
　　
　　回想起来，阿兰·图灵很可能在那时发现了他的同性恋倾向，克里斯托弗是他的初恋。但是没有任何迹象表明，这两名青年之间发生了身体接触，他们一起做化学实验，交流数学公式，并探讨埃丁顿和剑桥大学另一位天文学教授詹姆斯·简爵士所著书中的新天文学和新物理学。
　　
　　剑桥大学是有抱负的英国科学家追逐向往之地，其在科学和数学上最享有盛名的学院就是三一学院。1929年12月，阿兰和克里斯托弗花了一周的时间到剑桥大学参加奖学金考试，一起沐浴在弗朗西斯·培根、艾萨克·牛顿、詹姆斯·克拉克·麦克斯韦母校的氛围中。他们回到舍伯恩一周后，考试结果公布在了《泰晤士报》上。阿兰没被录取，而克里斯托弗被录取了。克里斯托弗将前往三一学院，而阿兰最大的希望是能争取在下一年入学三一学院或者剑桥的其他学院。
　　
　　两个月后，克里斯托弗突然生病并在一周内去世，病因是他小时候所感染的牛结核病。他们舍伯恩的一位旧日同窗在信中写道：“可怜的图灵因为这个打击几乎崩溃，他们一定是极其要好的朋友。”虽然阿兰·图灵也与其他男人有着更亲密的性关系，但显然他对克里斯托弗的爱与崇拜是其他人所不能比的。
　　
　　1930年12月，图灵再次参加了三一学院的考试，但仍然未被录取。他的第二选择是剑桥大学国王学院。这一次，他决定专攻数学，全心钻研G. H. 哈代的经典著作《纯数学教程》（A Course of Pure Mathematics）备考，这本书在当时已经是第15版了。1931年秋，阿兰开始了他在剑桥大学国王学院的学习。
　　
　　接下来的一年，图灵研究起一本叫做《量子力学的数学基础》的新书，这本书由年轻的匈牙利数学家约翰·冯·诺依曼所著。20世纪20年代中期，冯·诺依曼曾与大卫·希尔伯特在哥廷根大学一起共事。绝大多数早期量子力学的数学研究工作都是在哥根廷大学进行的。20世纪30年代，冯·诺依曼移民美国并在普林斯顿大学任教，1933年成为普林斯顿高等研究院聘任的首批数学家之一。现在，在几个有趣的地方，约翰·冯·诺依曼和阿兰·图灵的生活有了交集。
　　
　　图灵与冯·诺依曼的第一次见面很可能是在1935年夏天，当时冯·诺依曼利用在普林斯顿大学的工作假期来到剑桥大学做关于殆周期函数的演讲。图灵已经熟知演讲的主题以及冯·诺依曼在这方面的研究工作。就在那年春天，图灵已经发表了他的第一篇论文，共两页，讨论了“左右殆周期性的等价性”（Equivalence of Left and Right Almost Periodicity，伦敦数学学会，1935），推广了冯·诺依曼在前一年发表的一篇论文。
　　
　　他们都没想到，两人会在次年于新泽西州的普林斯顿再次相遇。
　　
　　图灵对于数理逻辑这一精妙深奥领域的兴趣可能开始于1933年，当时他阅读了伯特兰·罗素1919年的作品《数学哲学导论》。书的末尾写道：
　　
　　如果有学生因为这本书而迈入数理逻辑的大门，并进行认真的研究，那么这本书就达到当时写作的初衷了。
　　1935年的春季学期，图灵修读了“数学基础”课程，授课人是麦克斯韦·赫尔曼·亚历山大·纽曼（1897—1984），其姓名缩写M. H. A.。纽曼更为人熟知，人们常亲切地称他麦克斯。麦克斯·纽曼名声在外的是他在组合拓扑方面的工作，不过他也可能是剑桥大学在数理逻辑方面最有见识的人。纽曼整个课程的高潮是对哥德尔不完备性定理的证明。（研究生水平的数理逻辑导论课程至今仍然采用类似的结构。）
　　
　　此外，纽曼的课程也涵盖了尚未解决的判定性问题。“是否有一种确定的方法，或者纽曼所说的‘机械过程’，它可以应用于一个数学命题，并得出该命题能否被证明的结论？”当然，对于“机械过程”，纽曼指的不是一台机器。机器也许能够进行简单的算术，但几乎不能解决实际意义上的数学问题。纽曼暗指的是后人称为“算法”的一类过程——用于解决某个问题的一组明确（但无意识的、非智能的）指令集。图灵开始研究判定性问题很可能是在1935年初夏。那时，他已经获得了剑桥大学奖学金，每年300英镑。图灵后来说，想到判定性问题的解决思路时，他正躺在格兰切斯特草坪上，这是剑桥学生很喜欢的一个休闲场所，距国王学院大约两英里。
　　
　　到1936年4月，图灵把论文“论可计算数及其在判定性问题上的应用”的草稿交给了纽曼。
　　
　　图灵的论文采用了一种不同寻常的数学证明方法。一开始，他描述了一个虚构的可以做一些简单操作的计算机器。尽管这个机器很简单，但是图灵断言它在功能上等价于一个进行数学运算的人。他设置好这些机器来计算数字。作为示例，图灵给出的第一台机器可以计算1/3的二进制形式（.010101…），第二台机器可以计算一个无理并很可能也是超越数的数（.001011011101111…）。他说服我们，还可以定义出机器来计算π、e及其他有名的数学常量。图灵甚至创造了一个通用机器，它能模拟其他任何一台计算机器的操作。
　　
　　然而，图灵机——这些假想装备的后来叫法——无法计算每个实数。他设计的机器只能进行有限数量的操作，通过用数字表示这些操作，他指出每一台机器唯一地用一个整数来描述，我们把这个整数称为描述数（Description Number）。因此，图灵机是可数的，可计算数——图灵机可以计算的数——也一定是可数的，但实数是不可数的（从康托尔的证明中可知）。可计算数当然包括代数数，而且还包括π和e等超越数，但由于可计算数是可数的，因而它们根本无法涵盖所有的实数。
　　
　　图灵机也是会出错的，我们完全可以定义一个根本不会正确工作或者不会做任何有意义工作的图灵机。图灵将他定义的机器分为“符合要求的”和“不符合要求的”两种。
　　
　　由于图灵机完全由描述数定义，我们也许有可能创造一台这样的图灵机，它能够分析这些描述数，以确定某一特定的机器是否是符合要求的。图灵证明了这是不可能的：没有一种判定图灵机是否符合要求的通用过程。一台图灵机可以分析另一台图灵机的唯一方式，是一步一步地跟踪机器的操作。总之，你必须实际运行一台机器，以确定它接下来会干什么。
　　
　　图灵机的这些性质也适用于计算机程序。一般情况下，一个计算机程序不可能分析另一个计算机程序，除非一步一步地模拟它的运行。
　　
　　图灵还证明了，我们甚至无法定义图灵机去做一些看似简单的事，例如确定另一台机器是否会打印数字0。在其论文的最后一节（将在本书第三部分讨论），图灵构造了一个数理逻辑上的命题，它等价于判定一个特定的图灵机是否将会打印数字0。由于他已经得出这样的“判定”是不可能的，所以这个命题在逻辑上是不可证明的，因此“判定性问题不可解”（图灵论文第262页，本书263页）。
　　
　　大约在麦克斯·纽曼阅读图灵论文手稿的同一时间，他又收到美国数学家阿隆索·邱奇寄来的短论文“判定性问题的笔记”的单行本。基于已刊出的另一篇论文，邱奇的文章同样做出了判定性问题不可解的结论。
　　
　　别人比图灵捷足先登了。这通常意味着他的论文不能发表，注定要被遗忘。但麦克斯·纽曼意识到，图灵的方法更具创新性，并且与邱奇的方法有着很大的差异。他仍然建议图灵向伦敦数学学会提交论文发表。（从发表的论文看，该学会于1936年5月28日收到它。）图灵在5月29日给他母亲的信上对此做出了解释：
　　
　　现在，有一篇论文同时在美国发表，作者是阿隆索·邱奇，他和我做的事相同，只是方法不同。尽管如此，纽曼先生和我觉得，截然不同的方法完全能够让我的论文得以发表。阿隆索·邱奇住在普林斯顿，所以我已经相当确定，我将去那里。
　　
　　5月31日，麦克斯·纽曼同时写信给阿隆索·邱奇和伦敦数学学会的秘书长。在给邱奇的信中，他写道：
　　
　　在你送给我的论文单行本中，你定义了“可计算数”（Calculable Numbers），并指出了希尔伯特逻辑上的判定性问题是无法解决的，这一问题也是另一位年轻人所苦苦思索的。这个年轻人就是阿兰·图灵，他正想发表一篇论文，其中出于同样的目的定义了“可计算数”（Computable Numbers）。在他的处理方法中，涉及一种能产生任何一个可计算序列的机器，这与你的方法很不同，但看上去优点很多。我觉得如果可能，明年他应该和你在一起研究。
　　
　　在给伦敦数学学会秘书长F. P. 怀特的信中，纽曼写道：
　　
　　我想你已经知道了图灵关于可计算数的论文。正当这篇论文完成并准备发表时，我收到了来自普林斯顿的阿隆索·邱奇的单行本，这篇文章在很大程度上率先给出了图灵论文的结果。
　　
　　尽管如此，我仍然希望你们能发表图灵的论文，因为他们的方法极其不同。而且，由于这个结果非常之重要，因而我们应该关注不同的处理方法。邱奇和图灵的论文的主要结果就是希尔伯特的追随者们研究了多年的判定性问题，即找到一种机械的方法以判定一行给定的符号所表述的是否是一条可由希尔伯特公理证明的定理，它的一般形式是不可解的。
　　
　　图灵增加了一个附录，主要阐述他的计算性（Computability）理念和邱奇的“有效计算性”是等价的。伦敦数学学会于1936年8月28日收到这个附录。
　　
　　图灵的论文发表在伦敦数学学会1936年11月和12月的论文集里，1937年12月发表了一份三页纸的修订稿。阿隆索·邱奇在1937年5月的《符号逻辑杂志》（Journal of Symbolic Logic）中针对这篇论文写了一篇只有四段的评论，其中写道：“一位持有铅笔、纸和一串明确指令的人类计算者，可以被看做是一种图灵机。”这是已知的“图灵机”一词最早见诸文字的地方。
　　
　　图灵的论文分为11章及一个附录。论文开头的引言直接开始描述图灵构想的这一类新的数。
　　
　　图灵只考虑实数集，他指出，可计算数是实数集的一个子集，这也意味着存在一些不可计算的实数。当然，这一点并不显然。
　　
　　对于“小数表达式”，图灵意指1/3应该表示为0.33333…，π应该计算成3.14159…，这乍看起来与他的“有限步骤”这一理念相冲突。显然，我们永远不能真正算完1/3或π的小数。然而，在图灵的论文中，“步骤”并不是指确定数位的实际过程，而是指确定数位的方法。用诸如“下一位是4，下一位是7，下一位是0……”的方法，显然可以计算任何实数，但这不是一个有限的方法。1/3和π都可以用一套算法计算出来（其中一个的算法更简单一些），我们计算它们所采用的步骤（长除法或更复杂的方法）只用到有限数量的规则。
　　
　　尽管从表面上看本论文的主题是可计算数，但是我们很容易用几乎相同的方法定义和研究关于整数变量，或者实数、可计算数变量的可计算函数，可计算谓词等，每种情况下涉及的基本问题都一样。我选择可计算数进行具体的研究，是因为它所涉及的技术细节最简单。我希望可以很快就给出可计算数、可计算函数等之间的关系，这将包括一套用可计算数表示实变函数的理论。
　　图灵并未按其论文说的继续写下去。哥德尔也打算续写自己关于不完备性的著名论文，甚至预先在标题里加了罗马数字Ⅰ，但他从未写过续篇，因为他的论文很快就被接受了，超出了他的预想。图灵则是因为后来开始关注其他事情了。
　　
　　图灵用下面这句陈述总结了论文的第一段。
　　
　　根据我的定义，如果一个数的小数形式可以被机器写下来，那么它就是可计算的。
　　在1936年，这样的说法非常奇怪，因为当时并不存在一般意义上图灵所要求的那种机器。
　　
　　图灵很可能知道英国数学家查尔斯·巴贝奇（1791—1871）的一些研究。巴贝奇曾设计了一个“差分机”（Difference Engine）用来计算对数表，然后大约在1833年放弃了这个项目，转而研究一种更像通用计算机的“分析机”（Analytical Engine）。巴贝奇也曾在剑桥工作，其未完成的机器上的零件在肯辛顿的科学博物馆展出过。不过，图灵似乎一点都未受到巴贝奇的概念或术语的影响。
　　
　　图灵可能知道微分分析仪（Differential Analyzer），也可能不知道。自1927年起，万尼瓦尔·布什（1890—1974）和他在MIT的学生开始研制这台机器。但是，这个模拟的（非数字式的）计算机主要用来解决工程应用中的微分方程。从数学或工程角度来讲，图灵或许会对这台机器感兴趣，不过这台机器并不能为这一特定问题提供很大帮助。
　　
　　很难想象在20世纪30年代中期，图灵如何能知道其他的早期计算机项目。图灵肯定不知道工程专业学生康拉德·楚泽（1910—1995）自1935年起开始在其父母位于柏林的公寓里建造计算机。乔治·斯蒂比兹（1904—1995）曾利用他从贝尔实验室拿回家的一些电话继电器搭接二进制加法器，不过这已经是1937年图灵论文发表之后的事情了。也是在1937年，哈佛大学研究生霍华德·艾肯（1900—1973）开始探索自动计算，从而促使哈佛大学与IBM合作，创造了哈佛马克一型计算机（Harvard Mark I）。
　　
　　这个时期，在解决可计算性问题和希尔伯特的判定性问题的先驱中，图灵是其中之一，其余人包括阿隆索·邱奇、埃米尔·波斯特（1897—1954）、斯蒂芬·克莱尼（1909—1994）。在20世纪30年代中期研究自动计算的那些人里，图灵也算其一。
　　
　　图灵总结了出现在论文后面章节中的部分结论，他写道：
　　
　　在§9、§10中，我会给出一些论证，说明可计算数也包括那些理当被认为是可计算的数。特别地，我会指出有几大类的数都是可计算的，例如所有代数数的实部、贝塞尔函数零点的实部、数π和e，等等。
　　“理当被认为是可计算的数”就是人们实际生活中计算的，并且存在相应算法的数。图灵根本不屑提及所有的有理数都是可计算的，因为这是显而易见的。他很快便把代数数也加进了可计算数的行列（他认为只有代数数的实部符合要求，因为代数方程的解有可能有实部和虚部两部分，而他已经限制了可计算数为实数）。
　　
　　图灵断言了代数数是可计算数，随后开始在超越数领域讨论这一问题。不过，他说只有某些超越数是可计算的。贝塞尔函数是特定形式的微分方程的解。零点就是函数取值为0的点。它们曾被刊印成表，因此被认为是可计算的。（现在，需要用这些数时，一般可以用计算机程序来计算。）虽然图灵没有提到，但三角函数和对数函数的一般取值都是超越数，这些数也是可计算数。同样，π、e等常数也如此。
　　
　　图灵并没有声称所有的超越数都是可计算的，否则可计算数就会和实数一样了。
　　
　　尽管如此，可计算数并不完全包括所有可定义的数，我们将给出一个可定义的却不可计算的数。
　　
　　我们就先在这儿留下一个悬念吧。到时候图灵将定义一个他（以及他的机器）不能计算的数。
　　
　　现在，图灵谈及了实数与可计算数之间差异的关键。
　　
　　尽管可计算数如此之多，并且在很多方面与实数相似，但它是可数的。
　　可计算数是可数的。可计算数的可数性显示了它们与实数的不同，因为实数是不可数的。
　　
　　在§8中，我将仔细考察几个论证，它们似乎能证明出与此相反的结论。正确地应用其中的某个论证，可以得到与哥德尔的结论大致相似的结论。
　　这就是著名的哥德尔不完备性定理。注意，图灵的脚注引用的是哥德尔论文的德文标题，英文译本直到1962年才出版。
　　
　　这些结果的应用价值很大。特别地，它表明希尔伯特的判定性问题是无解的（§11）。
　　这是接下来的18页论文中最后一次提到希尔伯特。
　　
　　图灵在了解了阿隆索·邱奇的证明，并断定两种方法是等价的之后，觉得需要为他的论文增加一个附录。引言的最后一段也是在那时加进来的。
　　
　　阿隆索·邱奇在其近期的论文中引入了“有效可计算性”（effective calculability）的概念，这和我的“可计算性”（computability）是等价的，但定义方式十分不同。邱奇也就判定性问题得出了相同的结论。关于“可计算性”和“有效可计算性”的等价性证明将在本文的附录中给出。
　　这是图灵的论文，接下来的28页中最后一次提到判定性问题。《牛津英语字典（第2版）》指出，除了1889年的一本字典，上述文字首次使用了“可计算性”一词。自那之后，30多本书的书名中使用了“可计算性”，第一本书是马丁·戴维斯的《可计算性和不可解性》，由McGraw-Hill出版社于 1958年出版。
　　
　　图灵的论文有11节，第1节现在开始。
　　
　　1.计算机器
　　
　　我们已经提到，可计算数是那些小数表达式可以通过有限步骤计算出来的数。这一概念需要更加明确的定义。在§9之前，我们不会真正尝试证明这个定义的合理性。就目前而言，我只能说，合理性的证明依赖于人类记忆的有限性。
　　图灵曾说可计算数就是那些可以被机器写下来的数，而现在又用人类记忆的有限性来解释定义中的“有限步骤”。将人与机器随意地关联起来，这种做法是图灵研究的一大特点。
　　
　　图灵最初说，可计算数是可以通过有限步骤计算出来的，当时听着确实很有道理。但是，现在他要通过人类思维的有限性来解读它，这就提出了关于数学真实性的本质问题。我们称实数为“实”数，尽管事实上绝大多数的数从没有人见过。此外，图灵还将在论文中指出，大部分实数都不能通过有限的算法计算出来。实数究竟在什么意义上存在呢？这是个哲学问题，对此，图灵也只是在其论文的修订版中模糊地提及（见本书第16章）。
　　
　　人类思维的状态是离散的。据此，图灵将人与机器关联了起来。
　　
　　我们可以将一个正在进行实数计算的人比作一台只能处理有限种情况q1, q2, q3, …, qR的机器，这些情况称为“m-格局”。
　　这里，m代表机器（machine），一台机器有有限个格局，并根据当前格局做不同的事情。更现代的术语则是状态（state），后来图灵引用“思维状态”来类比这些机器状态。举个例子，一台简单的洗衣机有注水、洗涤、漂洗、甩干四个状态。作长除法同样也涉及一系列不同的大脑格局或者思维状态：“现在要作乘法”、“现在要作减法”、“现在要借位”。机器的运转实际上就是在不同的格局间来回切换，通常以一种重复的方式进行。
　　
　　该机器配有“纸带”（可以与纸类比）。纸带穿过机器运转，同时被分成一个个区段（称作“方格”），每个方格中都可以放置一个符号。
　　图灵说这种纸带“可以与纸类比”，因为人就是在纸上计算数字的。图灵机中的纸带往往被想象成真的纸带，但如果真要构建一台图灵机，那么这张纸带或许会是上了磁的，或者仅仅是计算机内存中的一块。
　　
　　人类通常使用二维的纸张，而图灵限制他的机器只能用分成一格一格的一维纸带。方格中的字符可以是十进制的0到9，或者可以包括字母表中所有的英文字母，抑或键盘上的所有95个字符。（正如你将看到的，图灵甚至允许一个“符号”包含多个字符。）
　　
　　为了在这一节论文中表示这些符号，图灵使用了大写的德文哥特式字体S（意指“symbol”），它看起来是这样的：。你将不止一次看到这个符号。
　　
　　任何时刻，只有一个方格，比如说第r个，它里边的符号 (r)是“在机器里”的。
　　这里，图灵假设纸带的方格可以通过编号来识别。例如 (3451) 代表纸带第3451个方格上的符号。如果那个方格中包含字符“A”，那么 (3451) 就是“A”。但是严格地说，纸带的方格并没有被编号，机器也并不通过编号来找到特定的方格。（换言之，方格没有一个具体的地址。）
　　
　　图灵说，在任何时候，纸带上只有一个方格“在机器里”，并可以被机器检测。
　　
　　我们可以称这个方格为“扫描格”，扫描格中的符号可以称为“扫描符”。可以这么说，“扫描符”是机器当前唯一可以“直接感知”的符号。
　　机器不能一次“看到”整个纸带，它每次只能“看”纸带中的一个方格。
　　
　　尽管如此，通过调节m-格局，机器可以有效地记住之前“看到”（扫描）的字符。
　　一台机器可以从一种m-格局转换到另一种m-格局，这是由当前的扫描符决定的。例如，在特定的m-格局q34下，如果扫描符是“A”，它可能转换到m-格局q17；如果扫描符是“B”，它可能转换到m-格局q123。因此，m-格局q17就“知道”前一个扫描符为“A”，m-格局q123就知道前一个扫描符为“B”。（这并不完全正确，其他格局也可能转换到q17和q123，但是从机器的设计意图来看，q17和q123应该对之前的情况了解足够多，从而可以继续工作下去。）
　　
　　机器在任何时候可能的行为都是由当前的m-格局qn和扫描符(r)决定的。这对qn与(r)的组合称为“格局”。因此，格局决定了机器可能的行为。
　　m-格局可以是q1、q2等，当m-格局与一个扫描符配对时，图灵简单地称之为格局（configuration）。
　　
　　图灵已经暗示，机器会根据扫描符在m-格局之间的切换。这个机器还能做些其他什么呢？能做的并不多。
　　
　　在某些格局里，扫描格为空（即里边没有符号），机器会在这个扫描格写下一个新的符号，在其他格局中则会擦除这个扫描符。机器也可以改变正被扫描的方格，但只能移到左边或右边一格。
　　如果我把这个读写符号的机制叫做机器的读写头，我想我并没有违背图灵的意思。就好像录音机或录像机，读写头与纸带只在一个点相接触。图灵的读写头可以从纸带读取一个符号或者擦除一个符号，或者在其上写一个新的符号。它也可以向左或向右移动一格。（尽管读写头很可能是固定的，移动的是穿过机器的纸带，最好还是将读写头想象成是相对纸带移动的。）
　　
　　除了这些操作外，m-格局也可能会变化。有一部分写下的符号将组成一串数字序列，即被计算实数的小数表达；另一部分则是用来“协助记忆”的草稿。只有这些草稿才可以被擦除。
　　因为图灵希望他的机器能计算数，因此机器需要打印出数字，并且一般情况下，要打印一个无限长的数字序列。为了帮助这个过程本身顺利进行下去，机器可能需要把纸带的一部分作为某种便笺来使用。
　　
　　图灵机是什么样子的呢？你可以想象一些模样古怪的机器，不过更好的方法则是去照照镜子。正如一部著名科幻影片的高潮所说，“图灵机就是人”——以一种非常受限却又十分精确的方式进行算法运算的人。
　　
　　我的观点是：这些操作包括了在计算数字中用到的所有操作。
　　也就是说，人在计算数字中用到的所有操作。如果你觉得这台机器缺少一些基本的算术运算，比如加法或减法，那你说得一点没错。加法运算和减法运算没有内建在图灵机里。不过，只要有了正确的格局，图灵机便可以执行相应的算术运算。
　　
　　读者熟悉这一机器理论后，将会更容易理解我的这一观点。因此，下一节我将开始探讨这一理论，假设你已经知道了“机器”、“纸带”、“扫描”等词的含义。
　　大家或许已经准备好要看一些真正的机器了，但图灵还不想让我们如愿，他想先抛出一些定义。
　　
　　2. 定义自动机
　　
　　如果机器在每一阶段的动作（在§1的意义下）完全由格局所决定，我们称这样的机器为“自动机”（或a-机器）。
　　
　　我们也可能出于某些目的，使用那些格局只能部分决定动作的机器（选择机或c-机器）。（因此，我们在§1里用了“可能”一词。）
　　当描述格局如何决定一台机器的行为时（本书第61页），图灵的表述是“机器可能的行为”。行为的描述可以是不完整的，因为在一些机器中，行为会因人的交互动作（机器之外的“操作者”）而改变。
　　
　　当这样的一台机器达到某种模糊的格局时，除非有机器之外操作者给出选择，否则它不会继续工作。我们用机器来处理公理系统时就会出现这种情况。在本文中，我只讨论自动机，因此会经常省略前缀a-。
　　图灵对自动机和选择机的划分，某种程度上使我们联想到划分程序的一个传统方法：将程序分为批处理的和交互式的。现在，我们进行交互计算的经历如此之多，以至于可能会忘记仍然有许多不需要等待用户的键盘输入和鼠标点击就能运行的计算机程序。
　　
　　选择机虽然可能很有趣，但是它们在图灵的论文中无足轻重。图灵论文中自动机的行为完全由其自身的格局决定。
　　
　　计算机器
　　
　　如果一台自动机（a-机器）打印两种符号，第一类符号（称为数字）完全由0和1组成（其他符号称为第二类符号），那么这样的机器就称为计算机器。
　　在展示样机之前，图灵就已经把机器限制为只打印数字0和1，这也是用来表示二进制数的两个数字。使用二进制数是明智之举，但这一点对于1937年的大多数读者来说远没有我们今天所想的那么显而易见。克劳德·E. 香农（1916—2001）在其1937年麻省理工学院的硕士论文《继电器与开关电路的符号分析》中描述了电路与布尔代数的等价性，他一定很推崇选择二进制。但在早期的计算机中使用二进制并不普遍，尽管康拉德·楚泽使用了二进制，但艾肯和斯蒂比兹的机器都是基于十进制的，ENIAC（1943— 1945）也是一台十进制机器。直到香农1948年的一篇论文里，bit（比特，binary digit的缩写）一词才首次出现。
　　
　　图灵并不打算论证在其机器中使用二进制数的合理性，使用它的好处直到论文的第245页（本书第146页）才显现出来。但为了让大家尽快放下这些疑问，我将在下一章比较一些简单的二进制机器和十进制机器。
　　
　　如果给机器装上空白纸带，并且从正确的初始m-格局开始运转，那么机器打印出的第一类符号组成的子序列就叫做“机器计算出的序列”。
　　一台装有空白纸带的机器开始运作，打印出0和1（第一类符号）以及其他的符号（第二类符号）。这些0和1组成了计算出的序列。图灵将计算出的序列与计算出的数区分开来了。
　　
　　在这个序列的最前面加上一个十进制小数点（decimal point），并把它当作一个二进制小数（binary decimal），所得的实数就称为机器计算出的数。
　　某种程度上，这句话读起来有点费力，因为里面的术语并不完全正确。但是，我们需要原谅图灵用词的混淆，因为那时的人们根本不习惯讨论二进制数。即便在今天，那些熟悉二进制的人一般也不善于面对二进制小数。即使把Windows的计算器设为科学模式也没有用：把一个数转成二进制时，它会直接去掉小数部分。
　　
　　“十进制”的英文“decimal”是从拉丁文的“ten”演变而来的，这个单词的使用仅限于十进制数。下面是十进制小数：
　　
　　.25
　　
　　.5
　　
　　.75
　　
　　十进制小数点（decimal point）把整数部分（如果有的话）和小数部分分开。
　　
　　上面三个数的二进制表示为：
　　
　　.01
　　
　　.1
　　
　　.11
　　
　　那个点不是十进制的小数点，实际上应该称为二进制小数点（binary point）。
　　
　　正如二进制整数部分的每一位上的数字代表2的幂，小数部分的每一位二进制数字代表2的负幂。
　　
　　
　　
　　等价于十进制的21/32或者.65625。和十进制中一样，许多二进制的小数部分也是循环的。下面是1/3的二进制表示：
　　
　　.01010101…
　　
　　2/3是：
　　
　　.10101010…
　　
　　类似地：
　　
　　1/5 是 .001100110011…
　　
　　2/5 是 .011001100110…
　　
　　3/5是 .100110011001…
　　
　　4/5 是 .110011001100…
　　
　　图灵的措词更加准确：“在这个序列的最前面加上一个十进制小数点（decimal point），并把它当作一个二进制小数（binary decimal），所得的实数就称为机器计算出的数。”
　　
　　趁现在还在解释这块，我们来进一步审视这句话：“用机器计算出来的数是一个以二进制小数点开头的序列表达出来的二进制小数。”
　　
　　例如，如果有一台图灵计算机器只打印出一个0和一个1，没有其他字符，那么“机器计算出的序列”就是
　　
　　0 1
　　
　　而“机器计算出的数”就是一个以二进制小数点开头的序列
　　
　　.01
　　
　　这就是1/4的二进制形式。
　　
　　因为二进制小数点总是位于计算出的序列之前，所以图灵的机器将只会计算介于0与1之间的二进制数，不过这么小的范围已经足够用来研究可数性了。
　　
　　在机器运转中的任何阶段，被扫描方格的标号、纸带上所有符号构成的序列以及m-格局，共同描述了这个阶段的完全格局。
　　这是图灵从不同角度讨论这些机器时出现的“格局”一词的第三种用法，将它们理清楚是很重要的：
　　
　　m-格局是机器的一种状态；
　　
　　格局由一个m-格局和一个扫描符组成；
　　
　　完全格局是整个纸带在某一时刻的“快照”，加上当前的m-格局及读写头的位置。
　　
　　在相邻的两个完全格局之间机器和纸带发生的变化，称为机器的“移动”。
　　
　　下面两个定义在论文的后面才用到。
　　
　　循环机和非循环机
　　
　　如果一台计算机器只能写下有限个第一类符号，它就被称为是循环的（circular），否则称为非循环的（circle-free）。
　　如果一台机器运行到了某个不能移动的格局上，或者它能继续移动并有可能打印出第二类符号但永远不能打印出第一类符号了，那么它就是循环的。我们将在§8中解释“循环”这个概念的重要意义。
　　
　　我之前提到一台仅打印了0和1、不再打印其他字符的机器。它只打印了有限个数字，根据图灵的定义，它属于循环机。这台机器会在某处卡住并且不能再打印数字，这不是件好事。图灵希望这台机器能永不停息地打印数字。
　　
　　非循环机是好的机器。一台只打印一个0和1、不再打印其他东西的机器不是非循环机。如果机器真的想要计算1/4的二进制形式，它就必须在打印完0和1后继续不停地打印0。
　　
　　尽管图灵没有提到这个问题，但是他好像在暗示他的计算机器是从左至右打印数字的，正如我们从二进制小数点后读数字一样。
　　
　　可计算序列和可计算数
　　
　　如果一个序列可以被非循环机计算出来，那么它就是可计算序列。如果一个数与非循环机计算出来的数只相差一个整数，那么它就是可计算数。
　　图灵在这里区分了序列和数。一个可计算的序列是：
　　
　　010000…
　　
　　对应的可计算数是：
　　
　　.010000…
　　
　　数
　　
　　1.010000…
　　
　　也可以认为是可计算的，因为它与机器计算出来的数只相差一个整数。数
　　
　　10.01000…
　　
　　也是如此。同样，负数也是可计算的。
　　
　　为了避免混淆，我们会更多地提及可计算序列，而非可计算数。

作者: 里予 时间: 2013-11-13 02:12
　　艾伦麦席森图灵（Alan Mathison Turing）1912年6月23日生于英国伦敦梅达维洛（Maida Vale, London），今年正好是他100周年诞辰。这位英国皇家学会会员、数学家、逻辑学家，被国际公认为计算机科学与人工智能之父。正当他具有奔流不息的思维源泉和将其付诸实践的巨大热情时，1954年6月7日图灵在英国柴郡的韦姆斯洛（Wilmslow, Cheshire）住所不幸意外辞世，差半个月才满42岁，一代科学巨星陨落。
　　
　　长期以来，人们把图灵看得很神秘、很古怪、很遥远，令人敬畏而难以理解。褒者认为他是奇才，贬者认为他是畸才。事实上，他的确是涉猎广泛的科学天才，不仅对数学及计算科学，而且对物理学（量子力学与相对论）、化学（类似炼金术士般着迷）、生物学（生物形态及数学生物学）都有浓厚的兴趣与创新。他看似对人漫不经心，但极其友善诚恳。他是世界级的马拉松运动员，却陷于同性恋的惩罚与折磨。真是人无完人、金无足赤，我们知道达芬奇也是同性恋者，艾萨克牛顿曾是隐秘而执著的炼金术士。伟大的科学家并不是神，我们应该把图灵还原成真实的人。
　　
　　深入阅读：http://www.ituring.com.cn/article/16335

欢迎光临悦读人生 (http://www.dothinkings.com/)