n，它比
n，n
2，n
3，
n4以及
n
5中的每一个都大多了，甚至比带有任何固定指数
r的
n
r都大），
或者譬如讲
N甚至近似地和
2
2n（这又更大得多）成比例。
当然，这些“步骤”的数目可依赖于实现该算法的电脑的类型。如果
电脑为第二章描述的图灵机，那儿只有一盘磁带——这是相当低效率的—
—那数目
N就会比允许两盘或三盘磁带的增加得更快速（也就是说机器会
运行得更慢）。为了避免这类不定性，按照
N作为
n的函数增加的可能方
式进行了宽广的分类，使得不管使用何种类型的图灵机，N的增加率的度
量总是归到同一分类中去。一种称为
P（说明“多项式时间”的分类包括
了所有最多为
n，n
2，n
3，n
4，n
5，.中的一个的固定倍数①的速率。也就
是说，对
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）=n
2/4，并且可具
有(n
2/4-(n/2)次的单独的二进位加法（包括移位）。这样，总共有
(n2/2)-(n/2)次的单独算术运算——我们必须包括一些涉及到移位的额外
的逻辑步骤。总的步骤数为
N=n
2/2（忽略低阶项），这肯定是多项式的
13。
一般来说，对于一族问题，我们取这问题的“尺度”的测度
n为需要
指明该特别尺度的问题的自由数据所需要的二进位位数（或比特）的总
数。这意味着，对于给定的
n，在给定的尺度下问题会有多到
2
n种不同的
情形（因为每一位可有两种可能性中的任一个，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．事实上，哥德尔定理的推理可以用这种方式来表达，使之不依赖于
诸如
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
0，使得所有大于
m
0的
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 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）。
第五章经典世界
物理理论的状况
物理理论的状况
相反地，我在下面将持一种非传统的论点，也就是我们对物理学的理
解，甚至在原则上还不足够用以描述我们大脑的运作。为了论证这一点，
我首先必须概述物理学的现状。本章是关于所谓的“经典物理”，它包括
牛顿力学和爱因斯坦相对论。此处“经典”基本上是指在
1925年左右发现
量子理论之前的占统治地位的理论。量子力学是由诸如普郎克、爱因斯
坦、玻尔、海森堡、薛定谔、德布罗依、玻恩、约丹、泡利以及狄拉克的
开创性工作的成果。它是一种不确定的、非决定性的、神秘的、描述分子、
原子和次原子粒子行为的理论。相反地，经典理论是决定性的，这样，将
来总是由过去所完全固定。尽管许多世纪以来对经典物理学的理解使我们
得到了非常精确的图像，它仍有许多神秘之处。我们还必须考察量子理论
