5，…，顶点4 接到顶点5，…等等 （见图4.14）。如果需要的话，哈密顿线路可由这些边缘的子集给出，它用具有比前述的更多个零的二进位序列来描写。检查过程是可以比开始找这些哈密顿线路更迅速地完成的事。人们所要做的一切，是检查提出的线路的确是一线路，也就是边缘须属于原先的图，而图中的每一顶点刚好只被用过两次，在两个边缘的一个顶点各一次。这一检验过程是某种可以在多项式时间内完成的事。事实上，这个问题不仅是NP 的，而且被认为是NP 完备的。这表明其他任何NP 问题都可在多项式时间内转变成它。这样，如果某个足够聪明的人能在多项式时间内找到解决哈密顿线路的算法，也就是能显示哈密顿线路问题实际上是在 P 中！则其推论是任何 NP 问题都在P 中！这样的事情会具有重大的含义。一般地讲，对于合情理大的nP 中的问题被认为可以用一台快速的现代电脑 “处理”的（也就是“在一可接受的”时间长度里是可解的）。而在NP 中又不在P 中的问题，对于合情理大的 n被认为是“不可处理的” （也就是虽然在原则上可解，“在实际上是不可解的”），而不管我们将面临着何种可以预见的种类的电脑速度的增加。 （对于大的n----------------------- Page 139-----------------------的不在P 中的NP 问题，需要的时间会急速地变得比宇宙的年龄还要长，这对于实际的问题没有什么用处！）任何在多项式时间内解决哈密顿线路问题的聪明算法都能转换成在多项式时间内解决任何其他NP 问题的算法！另一个NP 完备的15 问题是 “旅行推销员的问题”。这个问题和哈密顿线路问题很相像，除了在不同的边缘附上数字，人们寻求数 （推销员走的 “距离”）的和为极小的哈密顿线路。旅行推销员问题的多项式时间解会又一次导致所有其他NP 问题的多项式时间解。（如果真的找到这样的一个解，将会变成头条新闻！尤其是好几年来提出了密码系统，该问题有赖于大整数的因子化问题，这是另一种NP 问题。如果可在多项式时间内解决这一问题，那么这样的码就可能被强大的现代电脑所破。但是如果不能，这码就是安全的。参见伽特纳 1989。）专家们普遍相信，不管用任何类图灵机的仪器，实际上都不可能在多项式时间内解决一个NP 完备的问题。所以结论是，P和NP 不是同样的这个信念很可能是正确的，虽然还没有一个人能证明之。这仍然是复杂性理论最重要的未解决问题。----------------------- Page 140-----------------------物理事物中的复杂性和可计算性复杂性理论对于本书的讨论是重要的，因为它引起了另外的问题，和事物是否可计算的问题有一点区别；也就是说，被认为是算法的事物实际上是否以一种有用的方式为算法的。在后面的章节中，我关于复杂性理论将讲得比可计算性更少。因为我倾向于认为 （虽然毫无疑问地是在相当不足够的基础上）复杂性理论的问题和可计算性本身的问题不一样，在和精神现象相关联上不占有中心的地位。而且，我感到算法的可行性问题的现状才刚刚被复杂性理论所触及。然而，关于复杂性作用的问题，我也很可能是错的。正如我将在后面（第九章464 页）评论的那样，实在物理对象的复杂性理论也许和我们刚刚讨论的有显著的不同。为了使这种差异变得更明了，那就必须使用量子力学，这个原子、分子以及许多其他在大得多的尺度下重要现象行为的神秘而强有力的精确理论。在第六章我们将遇到这一理论。按照最近大卫 ·德义奇(1985)提出的一系列思想，在原则上可能建造 “量子电脑”，存在不属于 P 的然而由这种装置可在多项式时间内解的问题的 （类）。直到现在一点也不清楚，一个实际的物理仪器如何建造成行为可靠的量子电脑，而且迄今所考虑的问题的类肯定是很人为的——但是，我们似乎已经知道了用量子物理仪器改善图灵机的理论可能性。我在这里讨论时把它当作一台 “物理仪器”的人类的头脑，尽管是设计得非常微妙精巧的，而且是非常复杂，它本身会从量子理论的魔术中得到好处吗？我们是否理解量子效应可以用于解决问题或作判断的方式呢？为了利用这种潜在的好处，我们也许必须 “超越”现存的量子理论，这是可以理喻的吗？实际物理仪器真的很可能改善图灵机的复杂性理论吗？实际物理仪器的可计算性理论又是如何呢？为了研究这类问题，我们必须离开纯粹数学的领域，并在下面的章节中探求物理世界在实际上是如何行为的！注 释1．在考虑其成员又为集合的集合时，我们必须小心地区别那个集的成员以及那个集的成员的成员。例如，假定S 是另一确定的集T 的非空子集的集合，而T 的元素是一个苹果和一个桔子。T 就有 “二性”而非“三性”的性质；但是S 实际上有 “三性”的性质；S 的三个成员是：一个只包括一个苹果的集合，一个只包括一个桔子的集合以及包括一个苹果和一个桔子的集合——总共有三个集，这就是S 的三个元素。类似地，其成员只有空集的集合具有 “一性”而非“零性”——它有一个成员，也就是空集！空集本身当然只有零个成员。2．事实上，哥德尔定理的推理可以用这种方式来表达，使之不依赖于----------------------- Page 141-----------------------诸如P (k)的命题 “真理”的完全外在的概念。然而，它仍然依赖于某k些符号的实在“意义”的解释：尤其是，“～$”的真正意义是“不存在 （自然数）……使得……”。3．在下面用小写字母代表自然数，而用大写字母代表自然数的有限集合。令m-→ 〔n，k，r〕表示陈述“如果x= ｛0，1…，m｝，它的k个元素的每一子集都被放到r个盒子里，则存在X 的一个 “大”的至少包含n个元素的子集Y，使得所有Y 的k 元素子集都被放到同一盒里去。”这儿“大”的意思是Y 中的元素数目比作为Y 中的元素的最小的自然数还大。考虑如下命题：“对于任何选取的k，r和 n，存在一个m ，使得所有大于m 的m，0 0陈述m-→ 〔n，k，r〕总成立。”J ·巴黎斯和L ·哈林顿(1977)指出这一命题等效于算术的标准的 （皮阿诺）公理的哥德尔型命题。这一道命题是不能从那些公理证明得到的，但是关于那些公理作了某些 “显然正确”的断言正也就是，在这种情形下，从公理推断出来的命题本身是真的）。4．其题目为 《基于序数的逻辑系统》，而且有些记者将会熟悉我用在下角标示代表康托序数的记号。使用我在上面所描述的步骤得到的逻辑系统的等级由可计算的序数来表征。存在一些相当自然的和容易陈述的数学定理，如果人们试图用标准的算术的 （皮阿诺）法则去证明，就需要使用在前面概述的 “哥德尔化”步骤。这些定理的数学证明根本就不依赖于任何模糊或可疑的似乎处于正常数学论证的步骤以外那一类推理。参见斯莫林斯基(1983)。的最“极端的”的数学陈述（虽然人们还经常考虑比这更极端得多的陈述）。连续统假设，由于哥德尔本人和保罗J ·柯亨确立了它实际上和集论的标准公理和步骤法则无关，而变得格外有趣。这样，对连续统假设的看法可用来区分形式主义者和柏拉图主义者。对于一个形式主义者而言，由于用标准的 （策墨罗——弗兰克尔）形式系统既不能建立也不能否定连续统假设，所以是 “非决定的”，把它叫做“真”的或“伪”的都 “没有意义”。然而，对于一个好的柏拉图主义者，连续统假设或是真的或是伪的，但为了确立它就需要某种新的推理形式——实际上甚至超出了对策墨罗——弗兰克尔形式系统使用哥德尔型命题的手段。 （柯亨(1966)本人提出一种使得连续统假设成为 “显然错误”的反思原则！）6．参阅鲁克尔(1984)的生动而不太技术性的有关论述。7．伯鲁尔本人似乎部分地因为对自己的一个拓朴学的“伯鲁尔固定点定理”证明的 “不可构造性”忧虑，而开始沿着这个思路思考的。该定理断言，如果你取一个圆盘——也就是一个圆和它的内部——并且以一种连续的方式运动到它原先定位的区域的内部，那么在圆盘上至少有一叫做固定点的点，它刚好在自己开始的那点结束。人们也许不知该点准确地在何处，或者也许那里有许多这类的点，这个定理只是断言某一这类的点的存----------------------- Page 142-----------------------在。作为数学的存在定理而言，这实际上是一个相当 “构造性的”定理。依赖于所谓的 “选择公理”或“卓恩引理”的存在定理具有不同程度的非构造性 （参阅柯亨1966，鲁克尔1984）。伯鲁尔情形的困难和下面相类似：如果f 为一实变量的实数值的连续函数，该函数既取有负值又取有正值，找到f 取零值的地方。其通常的步骤是涉及到重复地对分f 改变符号的区划。但是去决定f 的中间值为正、负或零，在伯鲁尔需要的意义上可以不是 “构造性的”。8．我们列出集合{v，w，x，…，z}，这里按照某种字典方案，v代表函数f。我们在每一阶段 （递归地）检验看是否有f(w，x，…，z)=0，并且只有如果是这样的话，才维持命题$w，x，…z 〔f(w，x，…，z)=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）。----------------------- Page 143-----------------------第五章经典世界----------------------- Page 144-----------------------物理理论的状况为了了解意识如何是自然的一部分，我们对自然的运行要知道哪些呢？制约身体和头脑组成基元的定律与此关系重大吗？如果真的像许多人工智能的拥护者所竭力说服我们的那样，意识理解仅仅是由算法所规定的，那么这些定律实际上是什么样子的则是无关紧要的。任何能够实现算法的仪器都一样好。另一方面，也许我们的知觉比可怜的算法更富有内容。也许构成我们的确切方式正和实际上制约构成我们物质的物理定律一样重要。我们也许需要理解构成物体物质以及规定所有物体行为的根本性质。物理学尚未做到这一步。许许多多的秘密还有待揭示和探索。然而，大多数物理学家和生理学家却断言，我们已经拥有足够的关于通常尺度的、诸如人脑物体运作的物理定律的知识。作为一个物理系统，大脑毫无疑义是极端复杂的，我们对其结构的大部分细节和相应功能相当无知。但是少数人说，人们对作为构成其行为基础的物理原则的理解不存在任何重大缺陷。相反地，我在下面将持一种非传统的论点，也就是我们对物理学的理解，甚至在原则上还不足够用以描述我们大脑的运作。为了论证这一点，我首先必须概述物理学的现状。本章是关于所谓的 “经典物理”，它包括牛顿力学和爱因斯坦相对论。此处“经典”基本上是指在1925年左右发现量子理论之前的占统治地位的理论。量子力学是由诸如普郎克、爱因斯坦、玻尔、海森堡、薛定谔、德布罗依、玻恩、约丹、泡利以及狄拉克的开创性工作的成果。它是一种不确定的、非决定性的、神秘的、描述分子、原子和次原子粒子行为的理论。相反地，经典理论是决定性的，这样，将来总是由过去所完全固定。尽管许多世纪以来对经典物理学的理解使我们得到了非常精确的图像，它仍有许多神秘之处。我们还必须考察量子理论（在第六章）。因为和大多数生理学家的观点相反，我相信量子现象似乎对大脑的运行是相当重要的——这些是下面几章的内容。迄今为止科学已取得了引人注目的成就。我们只要环视四周即可见证理解自然帮助我们取得了何等伟大的威力。现代世界的技术大多是从大量的经验中推导出来的。然而，正是物理学理论以更基本得多的形式成为我们技术的基础。这正是我们在此所关心的。我们的理论是相当精确的。但其力量并不仅仅在此，而且在于异乎寻常地遵从精密的、微妙的数学处理的这个事实。正是这两者一道为我们带来了威力无比的科学。这个物理理论的大部分并不特别新颖。如果首先要挑选一个事件的话，那应该是 1687年伊萨克·牛顿出版了 《原理》一书。这本重要著作向人们展示了，如何仅仅从几个基本的物理原理出发，能够理解并经常以惊人的精度预言了大量的物理对象的行为。 《原理》一书中很大部分是关于数学技巧的非凡的发展，尽管欧拉等人后来提供了实用的方法。）正如牛----------------------- Page 145-----------------------顿所坦率承认的，他自己的工作大大得益于更早期思想家的成果，其中最杰出者为伽利雷·伽利略、雷奈·笛卡尔以及约翰斯·开普勒。还用了一些更古老的思想家们所奠定的重要概念，诸如柏拉图、欧多索斯、欧几里德、阿基米德以及阿波罗纽斯等人的几何概念。我在下面还要更多地说到这些。后来出现了对牛顿动力学基本框架的偏离。首先是十九世纪中叶由詹姆斯·马克斯韦发展的电磁理论。这个理论不仅包括了电场和磁场，而且1还描述了光的经典行为 ！此一杰出的理论将是本章后面所关注的课题。马克斯韦理论对于今天的技术具有相当的重要性，并且毫无疑义地，电磁现象和我们大脑的工作密切相关。然而，和阿尔伯特·爱因斯坦名字联结的两种伟大的相对论对我们的思维过程是否具有任何意义，还没有这么清楚。亨利·彭加莱、亨德里克·安东·洛伦兹以及爱因斯坦为了解释当物体以接近于光速运动时所产生的使人迷惑的行为，从研究马克斯韦方程出发，提出了狭义相对论 （后来赫曼·闵可夫斯基给出了精巧的几何描述）。2爱因斯坦著名的E=mc 方程是该理论的一部分。但是迄今为止此理论对技术的影响 （除了对核物理的效应之外）甚微，看来它和我们头脑工作的关联最多也只是外围的。另一方面，狭义相对论加深了我们对和时间本质有关的物理实体的理解。我们将会在后面几章看到，这给量子理论带来一些根本的迷惑，这些迷惑和我们对 “时间流逝”的感觉有重要关系。况且，人们在鉴赏爱因斯坦的广义相对论之前必须理解狭义相对论。广义相对论是用弯曲的空间——时间来描述引力。迄今为止此理论对技术的效用几乎①