按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
在物理学中，眼见为实；而在数学中，就不够了。霍夫曼和米克斯看到了对称图形之后，把图形搁置一边，仅根据方程就证明了曲面本身不相交。出乎他们意料，竟然发现了第四种无限小曲面，这种曲面由两个悬索曲面和一个平面构成，整体像从“瑞士硬干酪心”中发出来似的。3个月后，他们证实了存在着无限多的这种曲面，每一个曲面在拓扑学上都与带几个把手的3孔空心球形等价。
在霍夫曼和米克斯发表第一个新曲面核心的图片之后，英国剑桥大学的一位生物学家就和他们联系，他认为，发育中的胚胎可能呈现这种形状。最小面积曲面往往会自然地存在于有机与无机材料之间的界面中，因为这样的曲面可使表面张力降到最低程度。美国纽约市的一位牙外科医师打电话给霍夫曼，并且说明该图形看来正好像他们用于移植在假牙上固定假牙的骨质物，霍夫曼说，他认为“极小曲面的破坏性较小，因为它与骨质物的接触面较小。而且，还有许多‘把手’为骨质物履行使命”。
即使极小曲面在现实世界中未得到应用，而霍夫曼与米克斯的发现仍然是不朽的。不过它却暴露出有关无限小曲面的最新知识是多么的贫乏，而且它也证实了可以在纯数学研究中利用计算机。但对于将近200年来搞不清楚的问题，很难对其在计算机帮助下所取得的惊人进展提出异议。
第三篇 计算机在发现巨大素数、解阿基米德牛群问题、破译密码、证明四色地图定理以及发现新图形等问题上，计算机证明对数学家是有用的。然而在计算机能做些什么问题上，却还有难以捉摸的限制。
自20世纪30年代起，数学就面临着一场革命，如同物理学的两次革命——广义相对论与量子力学——一样重要，这两次革命动摇了物理学的基础，并且推翻了关于空间、时间与因果律的经典理论。数学的前景展望也由于美国纽约大学的莫里斯。克林提出了“必然的损失”的说法而完全改观。一种崭新的工作已不再注重于数学计算的能力，而是注重于计算的限制。有意义的计算问题被规定为原理上不能解的，或在原理上能解而实际上无法解的问题。
一个从原理上不能解的有意义的典型问题就是“停机问题”，它是艾伦。马西森。图灵于1936年提出的。图灵想到了计算机程序是否迟早会提供结果和停机的问题。停机问题已不仅是纸上谈兵的理论家所关心的问题，而且是很容易在实践中出现的问题。
美国麻省理工学院计算机科学理论学家迈克尔。锡普塞说道：“你可以想象，当你把程序编入卡片，然后提交给计算机中心时，尤其是在这几天里，你是多么想知道答案。他们总是整夜地进行运算，第二天就送回给你。比方说，你有一笔100美元的钱存在机内。有时，计算机程序会有一个无限的循环，而且会耗掉许多钱。由于它会陷入无限的循环，因此你从程序上得不到任何东西。不论是你帐上的钱都已耗费完，还是计算机以何种方式注意到机器运行了很长时间，计算机自己停了机。
“那么，你一定会想，为什么事先不检验程序，如果其中有无限循环，就不应该用它运算”。然而令人惊奇的是，这种自然的概念不能够实现，因为图灵证明了，没有一种检验方法能够适用于所有程序。
除了图灵所证明的停机问题是不可解的之外，1936年数学家向绝对数学知识的虚幻目标发动了另一次进攻。逻辑学家阿朗索。丘奇证明了所谓的判定问题也是不可解的：判定一个已知的语句是否表达一个算术的真值，决不可能有一般的过程。换句话说，能够输出所有算术真值的计算机是不存在的。至于你所给的每一种可能想到的算术语句，计算机也是不能确定其真值的。的确如此，要求找出算术的真值是没有诀窍的。
近几年来，数学界的注意力已从理论上不能解的问题转向理论上能够解而实际上不能解的问题上。在这些问题中，最著名的就是美国国际商业机器公司（IBM）的拉里。斯托克迈耶称之为“内在困难”的问题，即委婉法问题，如果这也算是一个问题的话。他请你构想一部想象中的最大功率的计算机。这部想象的计算机，可以大到充满整个宇宙（直径也许为1，000亿光年）。它将由质子大小（直径为10…13厘米）的硬件构成，信号将以光速（每秒3×1010厘米）在硬件中疾驰通过。它可以就某个问题工作200亿年，它超过了宇宙的估计年龄。这个难题具有一个令人不知所措的特点，即它在原则上能够解决，但即使用可想象出的最大功率的计算机，按宇宙年龄再工作上千百万年也无法解决。
这类问题之一是下棋问题，它在棋盘不是普通的8×8，而是n×n（这里n表示任意大的数目），而且还有不限数量的棋子（但每方只能有一个王棋）。我们想有一种计算机程序，不论棋下到哪一步，不管我们是哪一方，比如说白子，它都可以用来确定是否能够赢。某种程序只在理论上可行而在实际中行不通，它需要考虑所有白方可能走的棋步，随后考虑所有黑方可能回应的棋步，还要考虑所有白方可能反回应的棋步，以此类推，考虑所有可能继续的棋步，直到结束时为止。
这种穷举搜索程序的缺点是速度太慢：有那么多可能继续的棋步，甚至理想的计算机也不可能在200亿年的时间内把所有棋步都考虑进去。1981年，美国耶鲁大学的戴维。利希滕斯坦和以色列的数学家艾维兹里。弗伦克尔证明了对于足够大的棋盘也没有更快的程序。换句话说，耗时的穷举搜索程序没有简捷的方法。这种下棋问题，即使我们知道已有解法，也总是会使计算机的分析落空。
下面4章，我们将从理论和实践两个方面考虑计算机的能力与局限性。
第八章 图灵的通用计算机艾伦。马西森。图灵是一位非凡的数学家、计算机科学的先驱者、破译纳粹的著名密码谜的关键人物。 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状态中开始，按照惯例，扫描纸带上最左边的符号（换句话说，扫描**号中的第一个*号）。程序表描述了计