2012年的6月23日，将迎来图灵100岁诞辰。届时，全球计算机界必将掀起盛大的纪念活动。鄙人作为小角色自然没资格去参加那些大腕们的高层次聚会了。因此只好赶个大早，躲在角落处提前撰文，以此来纪念计算机界的鼻祖--图灵先生。 图灵先生的照片来自网络 阿兰.图灵(Alan Turing)，1912年出生在英国伦敦周边一个名叫曼达威尔的小镇。他从小爱好数学，后来考入剑桥大学，他读大学时展现了其优秀的数学天赋，获得了数学奖学金，并于1938年在普林斯顿大学获得博士学位。图灵博士毕业后回到英国，继续从事数理逻辑方面的研究工作。二战爆发后，他协助英国军方进行通信方面的工作，并成功的破解了德国纳粹的军事密码。 在1936年，图灵的经典论文《关于可计算数，及其在决策问题中的应用》( Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem" . Proceedings of the London Mathematical Society . 2 42 : 230–65. 1936–37. )，公开发表，此文提出了“图灵机”的概念，将一个数学问题是否可解，最终等价为“图灵机”是否停机的问题。（关于“图灵机”的具体概念，可以参考郝克刚教授的博文） 这篇经典的论文，为计算机的制造，奠定了理论基础。也正是因为图灵的伟大贡献，计算机界的最高奖项被命名为“图灵奖”。 鄙人作为计算机行业的一名小学生，始终认为 图灵先生是最伟大 的。何为伟大？ 伟大就是做出了巨大的成就，而并不为人所注意，我们普通人享受着他的伟大成果，却甚至都没有感受到他的存在 。我在此敲击的键盘，看着计算机显示器上的字符图画，尽情在网络上挥洒着自己的想法，但什么时候会去细想这计算机的工作细节，什么时候会去思考奠定计算机工作原理的图灵机是怎么被发明出来的。估计像我一样的绝大多数博友们都在享用着计算机和网络的好处，却早已忽略了图灵的存在了..... 想想我们脚下的大地；天上的太阳；以及呼吸的空气吧。我们时时刻刻的享受着她们，却甚至早已忽略了她们的存在。我们甚至肆意的毁坏蹂躏她们，却甚至将她们对我们的宽厚包容视为软弱可欺。 大地、阳光、空气，这难道不是最伟大的东西吗？ 图灵先生是在1954年去世的，死时年仅41岁。普遍的说法是因为他误食了沾有氰化钾的毒 苹果 ，而死亡的具体细节在学术史界还有争论。人们在惋惜他英年早逝之余，也不禁感叹： 看来苹果真的是会造就伟人的，无论是亚当和夏娃偷吃的那一个，砸中牛顿头的那一个，还是被乔布斯咬了一口的那一个......
图灵（ Alan Turing ）的伟大贡献 -- 纪念图灵诞辰 100 周年（ 7 ） 西北大学 郝克刚 7） 图灵测试，计算机的智能 电子计算机诞生以后，人们惊奇地发现它的能力大大超出原来的预期。计算机不仅可以做大量的计算，还能进行复杂的推理。于是就把它同人的大脑进行比较，提出“计算机能思维吗”的问题。这里涉及到对“什么是思维”的理解和界定，涉及哲学、认知学以及社会学等各个方面，相当复杂众说纷纭，很难有一个统一的标准。图灵 1950 年 10 月在英国曼彻斯特大学发表论文 “ 计算机和智能 ” ，巧妙地把这个问题转化为一种可操作的方法，那就是测试。后来被称为图灵测试。简单说就是与其争论什么是“思维”，不如我们去做实验测试。通过了测试就叫计算机能思维，否则就说还达不到思维的水平。 图灵测试是这样设计的。测试分测试人员和被测试方两部分。被测试方由 A 和 B 构成， A 和 B 分别是一个人和一台被测试的计算机。测试人员和被测试方是分开的，提问和回答是通过一些中间设备实现的。测试人员并不知道 A 和 B 那个是人那个是计算机。测试时由测试人员分别向 A 和 B 提问，由被测试的人或者计算机回答问题。通过一系列的提问后，如果测试人员能够通过问题的回答，正确地分出 A 和 B 谁是人谁是机器，说明计算机还没有达到人的水平，那机器就没有通过图灵测试，如果测试人分不出 A 和 B 谁是机器谁是人，那这个机器就通过图灵测试。图灵指出： “ 如果机器在某些条件下，能够非常好地模仿人回答问题，以至提问者在相当长时间里误认它不是机器，那么机器就可以被认为是能够思维的。 ” 当时的计算机根本无法通过这一测试。图灵预言， 50 年内 ， 即在 20 世纪末会有计算机通过图灵测试。图灵测试没有规定问题的范围和提问的标准，如果想要制造出能通过试验的机器，必须在电脑中储存人类所有可以想到的问题，储存对这些问题的所有合乎常理的回答，并且还需要理智地作出选择。这几乎是不可能的。到目前为止还没有电脑能通过图灵测试。但是如果限制在一定的领域和范围之内通过图灵测试是完全有可能的。 人工智能专家经过多年的努力，开发了不少智能软件，在理论和实践上取得了很大的进步。 1997 年 5 月 3-11 日， IBM 的计算机深蓝（ Deep Blue ）以 2 胜 1 负 3 平的成绩第一次战胜国际象棋冠军卡斯帕罗夫大师。在世界引起轰动。也可以说在一定意义下实现了图灵的预言。 自然对于图灵测试的理解以及它的作用等方面，学界也有各种不同的争论。而正是由于有这些争论才推动了科学技术的发展。 （未完待续）
那么，图灵机是啥样子的呢？它其实非常简单。图灵的主要构思之一，是考虑人在进行数学或者逻辑演算的时候是如何工作的。把人按照既定规则做计算和推理的这个操作过程加以最简化而得来的。具体而言，图灵机有下列零部件。 首先是一根一维的 带子 ，可以把它想象成一根纸带。带子分成确定的格子，每个格子里面可以写上记号，比如0和1，也可以为空，就是说没有写记号或者记号给抹掉了。这根带子是图灵机输入和输出的来源，也是图灵机记录中间结果的存储器。所以，这个带子的角色就好像一个人做算术或者逻辑推理时用的草稿纸那样。通常的草稿纸是二维平面的，比如除法演算的规则就告诉我们除数写在被除数左边，商写在被除数上面的横线之上，余数写在被除数相应位的底下，如此等等。但是按照图灵的分析，这种二维的安排，并不是必需的，因为只要有办法把哪个数写在哪里给有章有序地归置好，一维的带子就应该够用了。同时，也不需要太多种类的记号，因为更复杂的记号总可以由简单的给组合出来。比如，0、1和空白，就可以在二进制下做任何运算了。 人做计算时用纸，自然是为了看清纸上的数字，把下一步的结果用比较原子性的操作（比如一位数的加减乘除）一个个算出来，写到纸上，如此一步一步反复直到得到结果。所以就需要和草稿纸交互作用的机制，这在人就是用眼睛看，用手写。同样，图灵机的带子也有相应的读和写的机制。读在这里的意思，就是把带子上特定空格的 记号 给区分出来：0就是0，1就是1，空白就是空白；写的意思，就是在带子的特定空格放上个0或者1，替换掉了那里原来的记号，或者把那个格子抹成空白。我们平时做算术，在任何一个时刻，要么读和要么写，总是只在一个位置发生，比如读出被除数的某一位，或者写上商数的新的一位。即使我们有可能同时注视或者写出多位数，但这也可以分解成单独注视或者写出某一位。同样，在图灵机里，读和写在任何时间，只在一个空格进行。这样，我们就可以说有个 读写头 ，它就好像磁带录音机的磁头那样，在任何特定的时间总是在带子的一个特定的格子上方。要改变位置的话，就需要沿着带子挪动读写头，每次或左或右挪动一格。同样，如果需要挪多格的话，总可以通过反复挪动来实现。 有一点要说明的，就是图灵机的带子是没有头的，读写头向左或者向右都可以无穷无尽的走下去。更准确地讲，这个意思不是说在任何时候带子的长度是无限的，而是说在任何时候假使读写头往以便走到了带子在当前长度下的最后一格，那么总可以在头上再接上一段带子，让机器继续运行下去。这就好像草稿纸用完了，总可以再添一张。 有了带子（草稿纸）跟读写头（眼睛和铅笔或者说磁头），还缺负责计算的组织运作的东东。完成这个事情的，就是所谓控制器。这个可以想象成一个小盒子。盒子有特定的有限数目的状态。在不同的盒子状态下，机器可以有不同的行为，所以这个盒子才叫做控制器。具体状态在盒子里面是如何实现的不重要，比如可以用指针的位置或者用算盘珠子的位置，重要的是状态和状态之间可以分得一清二楚不会混淆。 艺术化的图灵机 ［原图取自： Wikimedia Commons ］ 有了这些基本零部件，我们就可以讨论如何让图灵机干活了。在任何一步上，决定图灵机做什么事情的有两方面的情况：（1）控制器现在的状态（这可以对应于现在的任务做到哪一步了（比如在做加法的话，可以是刚写了和，现在该写进位了），（2）读写头下面是什么；图灵机可以做三方面的事情：（3）从当前状态转移进入下一状态，与此同时（4）在当前格子上写个什么记号（包括用空白抹掉当前记号），并（5）让读写头在带子上左移一格、右移一格或是原地不动。所以，图灵机每一步做的事，就是根据它的（1）当前状态qi跟（2）当前读出的记号sj，决定（3）下一状态qij，（4）写出的记号sij，和（5）读写头的移动方向dij。 这样，图灵机的任何一步都可以用一个五元组来描述：( q i ，s j ， q ij ， s ij ， d ij )。这里的下标 i 表示控制器的当前状态 q i 是所有可能状态之一，下标 j 表示当前读到的记号sj是所有的可能记号之一。两个合在一起的 ij 就表示新的状态 q ij ，写出的记号 s ij ，移动的方向 d ij 是由 q i 和 s j 共同决定的，或者说这三者分别都是 q i 和 s j 的函数。给定特定的一组( q i ，s j ， q ij ， s ij ， d ij )，就是给定了图灵机在 q i 和 s j 下的行为，所以可以这样的五元组叫做图灵机的指令。当 q i 和 s j 不同的时候，就是说处于不同状态，读取不同记号的时候， q ij ， s ij ， d ij 相应地也可以取不同的（或者相同的）值，这样我们就有一些不同的五元组。把这些五元组都合到一起，就得到了决定了机器行为的 指令表 。我们通常想象指令表是存储在控制器里的，读写头是连在控制器上的。这样，在任何时刻，控制器就可以根据它的当前状态和带子上当前格子里的记号，决定图灵机的行为。 这里，有必要强调说明一下图灵机 彻底的离散性 。具体说来，带子是离散的：一格就是一格；记号是离散的：一个就是一个；控制器的状态是离散的：此状态非彼状态。读操作的区分和写操作的改变是离散的：读写头下面的是0，读到的就是0，写出的是1，格子上面出现的就是1，读的是啥、写的是啥不会有任何模糊之处。读写头移动是离散的：一格就是一格。状态转换是离散的：从状态甲到状态乙，没有中间状态可言，不会有混淆，不会有交叠。时间是离散的：读写操作、读写头移动、状态转化都是原子性的，一步完成，一步就是一步，没有完成了一半这样的说法。 举个具体的例子：二进制串奇偶性的检查。这里所谓的奇偶性是指二进制串里面有奇数个还是偶数个1。二进制串奇偶性这个概念挺有用。比如你和朋友之间发送消息，事先约定所有的消息都是7位，比如0101010，1110110，1111110，如此等等。这三个串里面，前两个有奇数个1，是奇串，后一个有偶数个1，是偶串。假设你们进一步约定，在发送消息前，每个7位的消息串尾巴上再增加一位，叫做校验位。这个校验位根据消息串的奇偶性来设置：如果消息串是奇，校验位就是1，否则就是0。这样，上面三个消息串在增加了奇偶校验位之后，就分别是01010101，11101101，11111100。然后你的朋友再把这样的包含校验位的8位的串，比如11101101，发送给你。如果传输正常，那么不管你的朋友发的是那个消息，这个8位的串都应该是偶串。这样，当你每收到一个串的时候，就可以对它进行 奇偶性检验 。如果你收到了一个偶串，比如11101101，那可能就没有问题（当然也可能有，比如，本来传输的是00101101，结果半路上前两位给反转而变成了11101101）。但是，如果你收到的是个奇串，比如10101101，那你就知道这中间肯定出问题了，至少有一位的0和1（一定有奇数个0和1）给反转过来了。于是，你就可以要求你的朋友重新传一次。通过这种奇偶校验，就可以抓住传输中发生的错误。 这个很有用的奇偶性检验，可以用图灵机来实现。把一个二进制串，放到带子上，串的两头的格子都是空白，读写头对准最左边的那一个非空白的数字（0或者1）。机器的任务是扫描并抹掉整个串，如果是个偶串，就在结束运行之前在带子上留下个0，如果是个奇串，就留下个1，而带子的其他格都是空白。 下面这个指令表，就能让图灵机实现奇偶性检验。在运行开始是，初始状态为偶。表中的H的意思是HALT，就是停机。遇到这个状态，机器就不再运行了。（所以，H不出现在 q i 那一列里面）。 ────────────────────────── ─── ─ ─── q i s j q ij s ij d ij ────────────────────────── ─── ── ─ ─ 偶 0 偶 空白 右 ────────────────────────── ─── ─ ─── 偶 1 奇 空白 右 ────────────────────────── ─── ─ ─ ── 偶 空白 H 0 - ─────────────────────────── ─── ─ ─ ─ 奇 0 奇 空白 右 ──────────────────────── ─── ───── ─ 奇 1 偶 空白 右 ─────────────── ── ─ ────────────── ─ 奇 空白 H 1 - ───────────────────── ─── ──────── ─ 下面看看为什么这个指令表能够完成任务。根据读写头当前所遇到的符号sj，首先，如果遇到0，就不改变状态：偶还是偶（第1行），奇还是奇（第4行）；其次，如果遇到1，就改变状态，从偶到奇（第2行），从奇到偶（第5行）；最后，如果遇到空白，读写头下面的不再是0或者1了，说明整个串都检查完了，这时，就可以根据状态输出0（第3行），或者输出1（第6行），并进入停机状态H。请注意，在整个过程中，除了进入停机状态H的时候，读写头不移动之外，读写头总是在向右移动；此外，除了进入H的那次，每读完一格，就把那格擦掉，所以 s ij 总是空白。 那么，我们通常所谓这个或者那个图灵机，就是指给定了一个如上表那样的指令表。给定了指令表之后，带子上的输入可以变，只要满足初始状态设置和读写头初始位置的条件，一个图灵机就应该可以对任何合法的输入串进行指令表所实现的处理。 跟学习编程序一样，学习理解图灵机如何运作的最好办法跟踪执行一些指令表和自己构造一些完成各种简单任务的指令表，比如做二进制加法、判断一个串是不是回文等等。 ［声明：此处的图灵机，细节上不同于Turing于1936年提出的，属于现在比较通用的改进型。这里是基于明斯基的Computation: Finite and Infinite Machines。奇偶校验的例子，来自该书第120页。］
（1）图灵小时候说过的一句话： 我似乎总是想以最节能的方式，用自然界里最平常的东西来造各种东西。 I seem always to want to make things from the thing that is commonest in nature and with the least waste of energy. 见图灵妈妈Sara Turing的图灵传第23页。 （2）图灵被逮捕之后写下的三段论： 图灵相信机器会思维 图灵跟男人睡觉 所以机器不会思维 Turing believes machines think Turing lies with men Therefore machines do not think 出自：Andrew Hodges的Turing: Natural Philosopher （3）来自未现世界的消息之三 宇宙不过是大爆炸之光锥的内部。 The universe is the interior of the light cone of the Creation. 来自未现世界的消息是图灵自杀前三个月写给学生和朋友Robin Gandy的一组明信片的标题。详见Andrew Hodges的Alan Turing: The Enigma第513页。此处按照Hodges的解释把the Creation译作大爆炸。 （4）来自未现世界的消息之四 科学是微分方程。宗教是边界条件。 Science is a differential equation. Religion is a boundary condition. 这图灵对爱丁顿关于科学与宗教关系观点的概括。 （5）来自未现世界的消息之八 制定［泡利］不相容原理纯粹是为了电子们自己好， 如果让它们自由来往的话，它们恐怕会腐败堕落（而变成妖魔鬼怪）。 The Exclusion Principle is laid down purely for the benefit of the electrons themselves, who might be corrupted (and become dragons and demons) if allowed to associated too freely. 别忘了电子们是同性的，呵呵。
标签: 图灵
