皇帝新脑-17

n，它比n，n2，n3，n4以及n5中的每一个都大多了，甚至比带有任何固定指数r的nr都大），或者譬如讲N甚至近似地和22n（这又更大得多）成比例。当然，这些“步骤”的数目可依赖于实现该算法的电脑的类型。如果电脑为第二章描述的图灵机，那儿只有一盘磁带——这是相当低效率的——那数目N就会比允许两盘或三盘磁带的增加得更快速（也就是说机器会运行得更慢）。为了避免这类不定性，按照N作为n的函数增加的可能方式进行了宽广的分类，使得不管使用何种类型的图灵机，N的增加率的度量总是归到同一分类中去。一种称为P（说明“多项式时间”的分类包括了所有最多为n，n2，n3，n4，n5，.中的一个的固定倍数①的速率。也就是说，对P分类中的任何问题（这里我的“问题”的真正含义是具有解决它们的一个一般算法的一族问题），我们有N≤K×nr，①这是在39页提到的希尔伯特第十问题的负面答案。（例如，参见德弗林1988。）这里变量的个数是不受限制的。然而人们知道，为了使这种非算法性质成立，实际上需要变量的个数不超过九就可以。这儿K和r为常数（与n无关）。这表明N不比n的某一固定方次的某一倍数更大。两个数相乘肯定是属于P问题的简单类型。为了解释这一点，我必须首先描述数目n如何表征一对特殊乘数的尺度。我们可以想象每一个数都以二进位写出，而每一个数的二进位位数简单地为n/2，总共给出了n二进位数——也就是总共n比特。（如果一个数比另一个短，可以简单地从短的开始连续地在前头加上零使之和长的具有一样的长度。）例如，如果n=14，我们可以考虑1011010×0011011（就是1011010×11011，但是在短的数上添了一些零）。最直接进行乘法的方式是只要写出：记住，在二进位系统中，0×0=0，0×1=0，1×0=0，1×1=1，0+0=0，0+1=1，1+0=1，1+1=10。单独二进位乘法的次数为(n/2)×(n/2）=n2/4，并且可具有(n2/4-(n/2)次的单独的二进位加法（包括移位）。这样，总共有(n2/2)-(n/2)次的单独算术运算——我们必须包括一些涉及到移位的额外的逻辑步骤。总的步骤数为N=n2/2（忽略低阶项），这肯定是多项式的13。一般来说，对于一族问题，我们取这问题的“尺度”的测度n为需要指明该特别尺度的问题的自由数据所需要的二进位位数（或比特）的总数。这意味着，对于给定的n，在给定的尺度下问题会有多到2n种不同的情形（因为每一位可有两种可能性中的任一个，0或1，而总共有n位数），而这些都必须由算法在不多于N步骤下被一致地处理好。存在许多不属于P问题（的族）的例子。例如，为了进行从自然数r计算22 r]的运算，甚至只要写出这一答案就大约需要2n 步骤，且不说进行计算了。为在的二进位表示中的位数。计算r 222r的运算，只要写下就n需要22r步骤等等！这些比多项式大多了，所以肯定不在中！P在多项式时间内可以写下答案并甚至能检查正确与否的问题更为有趣。由此性质表征的（可算法地解出的）问题（的族）是一个重要的范畴。它们被称为NP问题（的族）。更精确地讲，如果在NP中的问题的族的个别问题有一解，那么该算法将给出这个解，并且它必须能在多项式时间内检验所设想的解确实是一个解。在问题没有解的情形下，算法会告诉我们这个，人们不必在多项式或别的时间内去检验的确没有解14。NP问题既在数学本身，也在实在世界的许多范围内出现。我只给出一个简单的数学例子：在一个图中寻找所谓的“哈密顿线路”的问题（一个极简单思想的吓唬人的名字）。用“图”来表示点或“顶点”的有限集合，一定数目的点对由称为图的“边缘”的线连接起来。（我们在这儿并不对几何或“距离”性质感兴趣，只对由哪一顶点连接到哪一顶点感兴趣。这样，所有顶点是否在一个平面上表出是无关紧要的，我们的边缘是否互相穿越还是处于三维空间中都是无所谓的。）哈密顿线路简单地就是一个只包括图的边缘的闭合圈，其中每一顶点只刚好通过一次。图4.14中画出了一个在上面标出哈密顿线路的图。哈密顿线路问题是去决定，对于任何给定的图是否存在哈密顿线路，只要存在就把它明了地画出来。图4.14带有（用稍粗一些的黑线）标出的哈密顿线路的一个图。还只存在另一条哈密顿线路，读者也许介意把它找出来。可以按二进位用不同方式来表述一个图。用何种方法关系不大。一个步骤是给顶点编上号1，2，3，4，5，.，然后以某种适当的固定顺序列出成对的顶点来：(1，2)，(1，3)，(2，3)，(1，4)，(2，4)，(3，4)，(1，5)，(2，5)，(3，5)，(4，5)，(1，6)，.然后我们做一个准确的0和1的搭配的表，当一对顶点对应于图的一个边缘时写上1，否则写0。这样二进位序列10010110110.表明顶点1接到顶点2、顶点4以及顶点5，.顶点3接到顶点4和顶点5，.，顶点4接到顶点5，.等等（见图4.14）。如果需要的话，哈密顿线路可由这些边缘的子集给出，它用具有比前述的更多个零的二进位序列来描写。检查过程是可以比开始找这些哈密顿线路更迅速地完成的事。人们所要做的一切，是检查提出的线路的确是一线路，也就是边缘须属于原先的图，而图中的每一顶点刚好只被用过两次，在两个边缘的一个顶点各一次。这一检验过程是某种可以在多项式时间内完成的事。事实上，这个问题不仅是NP的，而且被认为是NP完备的。这表明其他任何NP问题都可在多项式时间内转变成它。这样，如果某个足够聪明的人能在多项式时间内找到解决哈密顿线路的算法，也就是能显示哈密顿线路问题实际上是在P中！则其推论是任何NP问题都在P中！这样的事情会具有重大的含义。一般地讲，对于合情理大的nP中的问题被认为可以用一台快速的现代电脑“处理”的（也就是“在一可接受的”时间长度里是可解的）。而在NP中又不在P中的问题，对于合情理大的n被认为是“不可处理的”（也就是虽然在原则上可解，“在实际上是不可解的”），而不管我们将面临着何种可以预见的种类的电脑速度的增加。（对于大的n的不在P中的NP问题，需要的时间会急速地变得比宇宙的年龄还要长，这对于实际的问题没有什么用处！）任何在多项式时间内解决哈密顿线路问题的聪明算法都能转换成在多项式时间内解决任何其他NP问题的算法！另一个NP完备的15问题是“旅行推销员的问题”。这个问题和哈密顿线路问题很相像，除了在不同的边缘附上数字，人们寻求数（推销员走的“距离”）的和为极小的哈密顿线路。旅行推销员问题的多项式时间解会又一次导致所有其他NP问题的多项式时间解。（如果真的找到这样的一个解，将会变成头条新闻！尤其是好几年来提出了密码系统，该问题有赖于大整数的因子化问题，这是另一种NP问题。如果可在多项式时间内解决这一问题，那么这样的码就可能被强大的现代电脑所破。但是如果不能，这码就是安全的。参见伽特纳1989。）专家们普遍相信，不管用任何类图灵机的仪器，实际上都不可能在多项式时间内解决一个NP完备的问题。所以结论是，P和NP不是同样的这个信念很可能是正确的，虽然还没有一个人能证明之。这仍然是复杂性理论最重要的未解决问题。物理事物中的复杂性和可计算性物理事物中的复杂性和可计算性然而，关于复杂性作用的问题，我也很可能是错的。正如我将在后面（第九章464页）评论的那样，实在物理对象的复杂性理论也许和我们刚刚讨论的有显著的不同。为了使这种差异变得更明了，那就必须使用量子力学，这个原子、分子以及许多其他在大得多的尺度下重要现象行为的神秘而强有力的精确理论。在第六章我们将遇到这一理论。按照最近大卫·德义奇(1985)提出的一系列思想，在原则上可能建造“量子电脑”，存在不属于P的然而由这种装置可在多项式时间内解的问题的（类）。直到现在一点也不清楚，一个实际的物理仪器如何建造成行为可靠的量子电脑，而且迄今所考虑的问题的类肯定是很人为的——但是，我们似乎已经知道了用量子物理仪器改善图灵机的理论可能性。我在这里讨论时把它当作一台“物理仪器”的人类的头脑，尽管是设计得非常微妙精巧的，而且是非常复杂，它本身会从量子理论的魔术中得到好处吗？我们是否理解量子效应可以用于解决问题或作判断的方式呢？为了利用这种潜在的好处，我们也许必须“超越”现存的量子理论，这是可以理喻的吗？实际物理仪器真的很可能改善图灵机的复杂性理论吗？实际物理仪器的可计算性理论又是如何呢？为了研究这类问题，我们必须离开纯粹数学的领域，并在下面的章节中探求物理世界在实际上是如何行为的！注释1．在考虑其成员又为集合的集合时，我们必须小心地区别那个集的成员以及那个集的成员的成员。例如，假定S是另一确定的集T的非空子集的集合，而T的元素是一个苹果和一个桔子。T就有“二性”而非“三性”的性质；但是S实际上有“三性”的性质；S的三个成员是：一个只包括一个苹果的集合，一个只包括一个桔子的集合以及包括一个苹果和一个桔子的集合——总共有三个集，这就是S的三个元素。类似地，其成员只有空集的集合具有“一性”而非“零性”——它有一个成员，也就是空集！空集本身当然只有零个成员。2．事实上，哥德尔定理的推理可以用这种方式来表达，使之不依赖于诸如Pk(k)的命题“真理”的完全外在的概念。然而，它仍然依赖于某些符号的实在“意义”的解释：尤其是，“～”的真正意义是“不存$在（自然数）..使得..”。3．在下面用小写字母代表自然数，而用大写字母代表自然数的有限集合。令m-→〔n，k，r〕表示陈述“如果x=｛0，1.，m｝，它的k个元素的每一子集都被放到r个盒子里，则存在X的一个“大”的至少包含n个元素的子集Y，使得所有Y的k元素子集都被放到同一盒里去。”这儿“大”的意思是Y中的元素数目比作为Y中的元素的最小的自然数还大。考虑如下命题：“对于任何选取的k，r和n，存在一个m0，使得所有大于m0的m，陈述m-→〔n，k，r〕总成立。”J·巴黎斯和L·哈林顿(1977)指出这一命题等效于算术的标准的（皮阿诺）公理的哥德尔型命题。这一道命题是不能从那些公理证明得到的，但是关于那些公理作了某些“显然正确”的断言正也就是，在这种情形下，从公理推断出来的命题本身是真的）。4．其题目为《基于序数的逻辑系统》，而且有些记者将会熟悉我用在下角标示代表康托序数的记号。使用我在上面所描述的步骤得到的逻辑系统的等级由可计算的序数来表征。存在一些相当自然的和容易陈述的数学定理，如果人们试图用标准的算术的（皮阿诺）法则去证明，就需要使用在前面概述的“哥德尔化”步骤。这些定理的数学证明根本就不依赖于任何模糊或可疑的似乎处于正常数学论证的步骤以外那一类推理。参见斯莫林斯基(1983)。的最“极端的”的数学陈述（虽然人们还经常考虑比这更极端得多的陈述）。连续统假设，由于哥德尔本人和保罗J·柯亨确立了它实际上和集论的标准公理和步骤法则无关，而变得格外有趣。这样，对连续统假设的看法可用来区分形式主义者和柏拉图主义者。对于一个形式主义者而言，由于用标准的（策墨罗——弗兰克尔）形式系统既不能建立也不能否定连续统假设，所以是“非决定的”，把它叫做“真”的或“伪”的都“没有意义”。然而，对于一个好的柏拉图主义者，连续统假设或是真的或是伪的，但为了确立它就需要某种新的推理形式——实际上甚至超出了对策墨罗——弗兰克尔形式系统使用哥德尔型命题的手段。（柯亨(1966)本人提出一种使得连续统假设成为“显然错误”的反思原则！）6．参阅鲁克尔(1984)的生动而不太技术性的有关论述。7．伯鲁尔本人似乎部分地因为对自己的一个拓朴学的“伯鲁尔固定点定理”证明的“不可构造性”忧虑，而开始沿着这个思路思考的。该定理断言，如果你取一个圆盘——也就是一个圆和它的内部——并且以一种连续的方式运动到它原先定位的区域的内部，那么在圆盘上至少有一叫做固定点的点，它刚好在自己开始的那点结束。人们也许不知该点准确地在何处，或者也许那里有许多这类的点，这个定理只是断言某一这类的点的存在。作为数学的存在定理而言，这实际上是一个相当“构造性的”定理。依赖于所谓的“选择公理”或“卓恩引理”的存在定理具有不同程度的非构造性（参阅柯亨1966，鲁克尔1984）。伯鲁尔情形的困难和下面相类似：如果f为一实变量的实数值的连续函数，该函数既取有负值又取有正值，找到f取零值的地方。其通常的步骤是涉及到重复地对分f改变符号的区划。但是去决定f的中间值为正、负或零，在伯鲁尔需要的意义上可以不是“构造性的”。8．我们列出集合{v，w，x，.，z}，这里按照某种字典方案，v代表函数f。我们在每一阶段（递归地）检验看是否有f(w，x，.，z)=0，x ，，.，并且只有如果是这样的话，才维持命题$w，，.〔z f(w xz)=0〕。9．最近妮诺·伯龙（由于受这本书初版精装本中我的议论所刺激）告诉我，她已能断定孟德勒伯洛特集（的补集）在下面注释10的特殊意义下的确是非递归的，正如我在正文中所猜测的那样。10．存在实变量的实函数的可计算性的一种新理论（和传统的自然数变量的自然数函数相反），由伯龙、苏伯和斯马勒(1989)提出。我最近才注意到该理论的细节。该理论还适用于复函数，它可能和正文中提出的问题有重要的关系。这一新工作的一些结果赋予孟德勒伯洛特集在适当意义下为非递归的猜测以强大的支持。11．这一特殊问题可更正确地被称为“半群的词语问题”。还有其他形式的词语问题，其法则略为不同，我们在此不予关注。12．汉弗(1974)和迈尔斯(1974)还指出，存在一个单独的（一个巨大数目的花砖）集合，它只能以不可计算的方式来镶嵌平面。13．事实上对于大的n，这一步骤的数目可用一些技巧减少到nlogloglogn——这当然还在P中。参见克奴斯(1981)有关的更多资料。14．更正确地讲，只对是/非类型问题（例如，给定a，b和c，a×b=c为真的吗？）P、NP和NP完备的族（参见165页）才被定义，但在正文中的描述对我们的目的已经足够。15．严格地讲，我们需要是/非的模式，诸如：推销员是否有一条距离小于若干的路径呢？（见上面的注释14）。第五章经典世界物理理论的状况物理理论的状况相反地，我在下面将持一种非传统的论点，也就是我们对物理学的理解，甚至在原则上还不足够用以描述我们大脑的运作。为了论证这一点，我首先必须概述物理学的现状。本章是关于所谓的“经典物理”，它包括牛顿力学和爱因斯坦相对论。此处“经典”基本上是指在1925年左右发现量子理论之前的占统治地位的理论。量子力学是由诸如普郎克、爱因斯坦、玻尔、海森堡、薛定谔、德布罗依、玻恩、约丹、泡利以及狄拉克的开创性工作的成果。它是一种不确定的、非决定性的、神秘的、描述分子、原子和次原子粒子行为的理论。相反地，经典理论是决定性的，这样，将来总是由过去所完全固定。尽管许多世纪以来对经典物理学的理解使我们得到了非常精确的图像，它仍有许多神秘之处。我们还必须考察量子理论