你在这里

第八章 图灵的通用计算机

主标签

  • 第八章 图灵的通用计算机

艾伦·马西森·图灵是一位非凡的数学家、计算机科学的先驱者、破译纳粹的著名密码谜的关键人物。 1952年 2月,他以“粗野的下流言行,触犯了1885年刑事法修正条例第八条”的罪行,在英国曼彻斯特市被捕。在此之前不久,图灵的家被盗,盗窃犯是他的朋友阿诺德·默里,一位19岁的无业青年,图灵与他曾有过性关系。当图灵向警察报告盗窃案时,曾把他与默里的关系告诉了警察,他天真地认为,皇家委员会即将使同性恋合法化。两个月后,他因6次进行性骚扰受到审讯,并因总共 6次的性骚扰被判有罪,将送往监狱。他接受定期服用两性化女性激素药物的方案,进行“有机疗法治疗”,因此给他一年缓刑。1954年6月7日,41岁的图灵吃了半个浸在氰化物溶液中的苹果自杀。

在人工智能领域,图灵取得了基本概念方面的两项不朽成就:图灵检验法和图灵计算机。图灵检验法是他确定计算机能否思考的方法。检验要求把计算机和任意选出的人与提问者分开,提问者要通过中间物向他们提出数量不限的问题。图灵认为,如果提问者未能区别两者之间是计算机还是人,那么就意味着计算机正在思考。换句话说,如果计算机被认为是有智能的,那么它就是智能型计算机。

要对图灵通用计算机的概念进行解释,需要一些基础概念。当图灵在英国剑桥大学时,1935年他就是在那里成为英国皇家学院的一名研究员,他受到了物理学革命性发展的影响,该发展推翻了因果律和决定论的传统概念。按照牛顿的世界观,如果在自然体系方面掌握了足够的知识,那么整个未来都将是可以预测的。

1795年,法国数学家、同时又是牛顿迷的皮埃尔-西蒙·拉普拉斯是这样论述智能的:“假如某一时刻有一种智能,这种智能可以包含所有的力量,并由此使自然界生气勃勃,而且使组成自然界的各种生命都有各自的位置——智能的强大足以使许许多多数据服从于分析——它可以使最大物体的运动与最轻原子的运动都包含在同一公式之内;对于智能来说,没有不能断定的事物,而且未来也和过去一样,都将出现在其眼前。”

然而,本世纪初,量子力学的提出,使未来完全根据现在和过去来决定的说法宣告结束。在30年代,由于量子力学,特别是由于观察者总是影响着观察结果的原理,使哲学界发生了大混乱,而英国剑桥大学正处在这种混乱的中心。图灵发现这种概念是不稳固的,而且他也被引向数学,因为看来它所涉及的是绝对的实体,与观察者无关。正如剑桥大学数论学家G.H.哈迪所说的,317是一个素数,不是因为我们想它是个素数,或者说我们的想法是以某种方式而不是另一种方式形成的,而是因为它就是一个素数,因为数学的实体性就是那样建立的。

图灵致力于解答某个疑难问题的工作,该问题切中了数学实体性的本质核心:是否有一机械方式确定数学中任何已知语句是正确的还是错误的?为了回答这个问题,他终于提出了“通用计算机”,即图灵计算机的概念,这种概念可以例行地回答数学的问题。图灵引入了能够运算数学的计算机概念,目的在于强化数学作为与人类事物无关的学科的地位。然而可笑的是,图灵发现,数学的某些问题是不能由计算机或人用机械的方法来解题的,例如,涉及非重复小数的数产生问题。

图灵计算机是一个非凡的概念。不过从其一系列性能的观点来看,它却是非常有限的。即使你对计算机的程序设计一无所知(或许整个主题会使你吃惊),但图灵计算机的如此有限性能,也会使你很快地理解它的“内部”工作情况,从而高兴地为它编写程序。然而,从计算的观点看,它是能够进行任何运算的,换句话说,数学家能够进行的任何运算,想象的最大功率计算机也能够进行运算。如果说,这种说法不是相当惊人的话,那么让我再隐晦地补充一句:图灵计算机,不管它叫什么名字,不一定是一部计算机。它可以是一个人或一组人。

那么,这种图灵计算机的基本原件是什么?首先,它有一条长带,设想它是一条窄窄的纸带,纸带上划有许多竖线,把它分成许多方形单元。

如果已知某单元不是空白的,那么它就含有有限字母符号中的某一种符号。图灵计算机,能够一次扫描纸带的一个单元,通常都是从含有符号的最左边单元开始。如果所扫描的单元是空白的,那么计算机就会让单元的空白留下,或者在单元中打印一个符号。如果所扫描的单元含有符号,那么计算机就可以让单元的符号留下不变,擦掉该符号并在该符号的位置上打印另一个符号,或者擦掉该符号并让单元留下空白。然后计算机停机,或者立即扫描到左边或右边的单元。

计算机对所扫描的单元要做些什么,下一个要扫描的是两个相邻单元的哪一个,这取决于计算机的状态或内部构形,状态数与符号数一样,必须是有限的。计算机的状态像一种思维状态,即计算机在“思维”些什么。要了解图灵计算机的运算,用不着对其状态的本质进行精确的、形而上的思考(或更抽象定义)。计算机的“程序表”规定了计算机对于符号与状态的每一种可能组合将要做出的反应。

举两数相加一例,将会非常清楚地阐明这些抽象概念。假定我们以“一元”的记号写出一些数字,其中整数 n用一串 n个*号来表示,在n个相连的单元内每单元一个*号。据此,**号表示2,*****表示5。一元记号的优点是只有一种符号*号,不需要10个不同的数字来表示任何已知的正整数。若要2加5,只要把**号和*****号打印在纸带上,它们之间有一个空白单元,这样两串*号就可以区别开。

带有图解的程序表说明了计算机如何进行两数相加的运算。但在讨论程序表的特点之前,先要概括地描述加法的过程。聪明的计算机先找到两个数之间的空白单元,在空白单元打印一个* 号(那么在纸带上留有一串的8个* 号),而后继续下去,找到一串* 号的结束单元,并擦除掉最后一个* 号。这样,在纸带上就留有*******号,按一元记号,它就是7,即2加5的和。

现在让我们再来看程序表。计算机的状态通常列在最左边的一栏内。在这个程序表内,共有3个状态,编号分别为0、1和2。符号(和表示空白单元的词“空白”)通常横列在程序表的上方。在这个表内只有一个符号*号。

计算机在0状态中开始,按照惯例,扫描纸带上最左边的符号(换句话说,扫描**号中的第一个*号)。程序表描述了计算机如何运算状态0与符号*号的组合。计算机让符号留下不变,扫描到右边的下一个单元,并停留在状态0中,那么,计算机如何运算这个单元?由于计算机仍然处在状态0中,而且单元中的符号还是一个*号,计算机仍按前面所述进行运算:只让符号*号留下,扫描到右边的下一个单元,并停留在状态0中。

阿基米德的报复 成长吧啊

现在换到空白单元。程序表中状态0与空白符号的组合说明了计算机是如何进行运算的。它打印了一个*号,再扫描到右边的下一个单元,即进入状态1。这时,这个单元中还是一个*号,而状态1和符号*号的组合就描述出计算机的行为:扫描到右边的下一个单元,并停留在状态1中。这个步骤要重复4次,因为每次都是一个*号继续出现。当计算机扫描到一串5个*号结束处的空白单元时,它会回到左边的一个单元,并进入状态2。这个单元中有一个*号,计算机会擦掉它。然后计算机停机,处于一种完成状态。这种方法的作用是:相同的程序表都可以生成任何两数的和,无论数的大小如何,只要以一元的记号写出,两数间有一个空白单元,就能算出。在状态0,计算机只是扫描第一个数的每个单元,一直扫描到空白单元,再在其上打印一个*号。在状态1,它则是扫描第二个数的每个单元,直到空白单元,再回扫,并停留在最后一个*号的单元上。在状态2,它只是擦掉这个*号。于是,纸带上就立即有了答案。

这种加法是众所周知的有限数法,因为程序表包括数量有限的状态和数量有限的符号。然而这种有限数法却可以生成范围无限的数。图灵计算机要运算可以想象的任何数之和,纸带的长度就必须是无限的,也就是说,如果纸带仅有1,000个单元长,而它就不能运算大于1,000的数。

在图灵计算机用这种方法完成两数相加的运算时,纸带将只有答案,而没有原来的两个数。如果有人试图编写一个带有原来两数的程序表,那么他一开始就应该想到,图灵计算机需要“计算”在两串*号中的8个*号。然而令人感到意外,图灵计算机不能进行这种计算。设想它扫描第一个*号时,就会跳入状态1。每当它扫描另一个*号时,就会跳入下一个状态。这样下去,在它扫描第五个*号后,计算机就已处在状态5中,扫描第二十三个*号之后,就处在状态23中。看来用这种方法,图灵计算机似乎能够计算任何*号的数;即当它扫描完所有*号时,它的状态数就相应于它的*号数。但是,这种方法是行不通的。你知道这是为什么吗?

问题就在于这个方法不是有限数法。这种方法需要数目无限的状态。比方说,如果计算机仅有5个状态,那么它就不能计算多于5个的*号,因此它将被限制在和为5或小于5的数之内。如果它有50,000个状态,它也不能计算多于50,000个的*号。换句话说,对于有限数状态n,它不能计算多于n的*号。这种方法行不通,是因为我们所要寻找的是在任何情况下都可用于任何加法的方法。

如果允许数字状态是无限的(或者符号数是无限的),那么程序表就编写不出来。而要求编写出有限数字的程序表,按照惯例,需要用机械的方式。

现在需要探讨一个令人感兴趣的说法,即图灵计算机不必是一部机器,而是程序表(如果你愿意的话,可以叫它软件),那就是图灵计算机的定义。任何一个实体,它可以是一部计算机、一个人、一条美人鱼、一个游魂、或是克里姆林宫,只要它能够按照程序表进行运算,就是一部图灵计算机。如果你能够按照加法图表中的程序表在纸带上进行两数的加法运算,那么你就是一部图灵计算机。在一篇卓越的论文中,图灵在理论上和实践中已经能够证明;图灵计算机无法做到的,数学家和计算机都无法做到。一部超级计算机能够非常迅速地解出的问题,动作迟缓的图灵计算机也同样能够做出解答。

掌握图灵计算机的实质和具备有限数法的解题能力,最佳的方法是自己编写程序表。我想提出一个建议,请你编写一种程序表,使它可以用于图灵计算机的一元记号的减法运算。但要提醒你,在编写程序表时,应让计算机以某种方式知道它已完成计算,并把该方式写入程序表中。否则,由于纸带的长度可以任意长,常常可能使计算机一直连续扫描许多空白单元。下图显示出了减法用的程序表。当然,其他程序表也可以进行运算。

阿基米德的报复 成长吧啊

第二个问题是为计算机编写一种程序表,可用于检验编写在纸带上的符号P和Q顺序是否是回文式的,即正读与反读的顺序都一样。一种方法就是使计算机能够对第一个符号与最后一个符号进行比较,第二个符号与倒数第二个符号进行比较,以此类推。但要记住,这种方法必须是有限数字。如果顺序是回文式的,可以让计算机打印一个Y,如果不是,则打印一个N。这种方法是安德鲁·霍奇斯在为英国《新科学家》周刊撰写的一篇文章中采用的。这种方法如图所示。

阿基米德的报复 成长吧啊

霍奇斯方法的缺点是,尽管程序表只有6个状态,但计算机要浪费许多时间沿一串符号来回移位。如果计算机在拿第一个符号与最后一个符号进行比较之后,拿倒数第二个符号与第二个符号进行比较(而不是拿第二个符号与倒数第二个符号进行比较),然后拿第三个符号与倒数第三个符号进行比较,再拿倒数第四个符号与第四个符号进行比较,以此类推,那么它就可以节省时间。这种方法的程序表如下图所示,它需要 10个状态。要缩短计算时间,必须以较长的程序作为代价。

阿基米德的报复 成长吧啊

阿基米德的报复 成长吧啊

最后一个建议是为图灵计算机编写一种程序表,可供计算机用于检验由空白单元分开的两串P和Q符号是否变移位置式的。而且,Y符号同样代表“是”,N符号代表“否”。这里需要提示一下,在计算机解题时,计算机会打印出一个假符号字母R。有一种可能的答案似乎是正确的。

_______

① 关于图灵最后几年的悲剧性详情,在安德鲁·霍金斯著的同情性传记文学曾做报道,《艾伦·图灵:谜》(西蒙-舒斯特出版社,纽约, 1983)。