按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
计算机在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）。
第九章 威利。洛曼无辜地死去了吗？
从某种基本意义上讲，计算机和数学家只是不容易识别的图灵计算机，知道这一点也许令人泄气。但在另一方面，从表面上看过于简单的图灵计算机，由于证明能够解各种各样的计算问题，从而又可被认为是鼓舞人心的。数学家与计算机之间理论上的相似性不仅适用于他们能解出的各种问题，而且也适用于他们不能解出的各种问题。
工业上每天都出现许多计算问题，若用任何已知的方法去解，则太费时间，现在都例行地由计算机去着手解决。然而工业需要的是对这些问题的解法，而计算机常常牵扯到程序设计人员的水平，他们往往不能编出最佳程序。其中有许多是众所周知的使旅行推销员感到为难的问题；已知一个城市与公路网络，要找一条推销员在往返旅程中到每个城市去一次的最短路线。仅有一种已知的算法用来解这种旅行推销员问题，就是可靠的逐步试探法，这种方法费力，缺乏预见性，只是对每一种可能性都进行尝试。看来，数学并未减轻威利。洛曼的烦恼。
过去15年内，数学家们都感到迷惘，他们寻求巧妙的、较快的算法都告失败，这是由于他们无知呢，还是这种问题本身存在内在的困难？按照当前的知识水平，暂时还没有较快的算法，甚至在理论上也没有。目前还没有人能够证明这一点。对证明的研究已是理论计算机科学中最为热门的课题，而且在这个领域中工作的数学家已被公认为是复合型理论学家。
当数学家们谈到保证解题方法时，他们的意思就是指算法。不要由于“算法”（algorithm）这个英语单词的发音令人生畏而摈弃它，它是9世纪波斯数学家阿布。贾法尔。穆罕默德。伊本穆萨。阿尔霍瓦里米的姓氏音译转讹而来的，他的语义遗产还包含有单词代数（algebra）在内。算法的音难读但不难懂。你早已了解什么是算法的直观概念。
你可曾记得，在你读小学时，你的英语老师让你制定出一整套令人厌烦的规定，去做诸如系鞋带一类枯燥无味的琐事，然后老师叫约翰尼。怀斯盖严格按照你的规定去系他的鞋带（与此同时，这个讨厌的老师还会让你大声念你的那一套规定）。
当然，他会立即出错——而且是个大错——因为你没有考虑一些看来好像是理所当然不成问题的基本步骤，就像系鞋带时理所当然要握住鞋带的塑料包头，而不是握住它的中部一样。如果你详详细细地写出，那么你就会得到一个有关系鞋带的规则系统，而这个规则系统不过是一个循序渐进的程序，在这个程序中，每一步都说得很明确，你可以按部就班地解决每个问题。每个步骤都要规定得清清楚楚，其间不允许留下任何靠可能、直觉、经验、解释或想象等方法来处理的细节。
当然，数学家们对于计算问题的算法要比系鞋带更感兴趣。两个整数相加的算法，根据小学老师教给我们的方法，是用纸和铅笔按照如下的明确步骤进行：把整数写成一行，一个数写在另一个数的上方，两数右端对齐，在它们下方划一横线，从右到左地进行计算，有时还“进位”1，而且照此步骤计算许多其他数的相加，也是不成问题的。这种算法应该包括如下法则，像“如果一个数2在另一个数4的上方，可在其下写一个数6”和“如果一个数3在另一个数6的上方，可在其下写一个数9”等法则。
算法的功能之一是其能用于一个问题的所有实例。例如加法算法可以算出任何两个整数的和。你虽然花费时间去详尽写出一种算法的全部细节，但你却得到了一种能够保证工作的方法。计算机的程序或是单一的算法或是系列的算法。如果没有指令告诉该算法的每一步骤应该做些什么，那么计算机就同不能模拟系好鞋带一样，也不能进行两数相加的计算。程序设计员的作用在于编好完整的指令，换句话说，要编好完整的算法。当程序设计员责怪其程序中的错误时，他的意思是指在编写详尽算法或把算法译成计算机语言时，他犯了一个错误。
必须强调的是，算法的用户不管是一部机器还是一个人，不需要对算法做出判断。例如，加法算法的使用，不需要“什么是数字”这一概念。要应用算法时，你可以盲目地按照法则进行。比方说，你不必知道，5是跟在4之后，7是大于3等等，甚至你也不必知道你是在使用十进制的数制。哲学文献中已有许多篇幅谈论过，就计算机的思考能力而言，缺乏判断会意味着什么。但是，探讨这样一个引人兴趣的说法则使我们离题太远了。
数学家们都不大关心旅行推销员这一专题。对于一系列较小的城市与公路网络，由于没有多少可能的路线需要审查，因而找到解法是很容易的。甚至对于大的城市与公路网络，那也可能幸运地或者偶然地找到最佳的路程。当数学家们宣称某问题实际上是不可解时，他们的意思是，仅仅知道保证解法的许多方法，就像穷举搜索所有可能性的方法一样低效，即使对于最高级的超级计算机来说，这种穷举搜索法也是太慢的。
数学的行家对于快速（与可用）的算法和慢速（与不可用）的算法都有严格的确定方法。假设数字n是某问题大小的量度（对于旅行推销员问题，n是城市与公路数目的量度）。对于快速的算法，随着计算问题规模的增大，完成算法所需的时间的增长不会大于n（表示计算规模）的某个多项式。多项式是一种数学函数，诸如2n（加倍）、3n（3倍）、n2（平方）、n3（立方）、3n10和64n100等。而对于慢速的算法，例如用于解旅行推销员问题的穷举搜索法，则其执行时间将按问题规模增加的指数增加，即2n、6n或12n等。
当n的值小时（也就是说，对于简单的问题），已知的多项式函数可以等于甚至超过已知的指数函数，但是当n的值大时，任何指数函数都将迅速地超过任何多项式函数。例如，当n等于2时，多项式函数n2等于4，它等于指数函数2n。但当n等于10时，n2只等于100，而2n却会像火箭上天那样猛增到1，024。毫无疑问，指数函数的增加会大大超过多项式函数的增加，这曾使托马斯。马尔萨斯感到忧虑，因为他发现人�