囚徒和盖梯尔
现在我们回到意外绞刑悖论。我们可以从三重理由出发做出论证:囚徒的“知识”是一个假象。奎因(W. V Quine)认为，囚徒(或者律师)的全部推理都是错误的。就连第一个推理(囚徒不能在最后一天被绞死)也是无效的。
当法官说囚徒不可能预知行刑的日期时，很明显，他的意思是说，一个完全遵循逻辑思维的囚徒将无法确切地推出行刑日期。一个普通的、不那么遵循逻辑思维的囚徒拥有更大的自由空间，他可能凭直觉确定一个日子，甚至有可能猜对(一个不合理的、正确的信念)。囚徒无法选择行刑日期，这足以说明囚徒不是知道，而只是猜对了。如果法官的命令确实有什么意义的话，其意义就在于禁止仅仅凭借推理确定日期的可能性。
为简单起见，我们假定行刑日期只能在两个日子中做出选择。假设囚徒的论证是有效的，他可以根据逻辑确定，为了奉行法官的指示，他一定在星期六被处死。刽子手(此人和囚徒一样聪明)同样可以推出这个结论。这样的话，他就没有理由在星期 六而非星期日行刑了。为什么呢?囚徒预测星期六是行刑日(根据归谬法假定这个前提)，但是，即使由于某个奇迹囚徒没有在星期六被绞死，他也可以推出行刑将发生在星期六。这就使得刽子手没有理由倾向于选择某一天而非另一天。如果他在星期六行刑，他会受到谴责;如果他不在星期六行刑，他也会受到谴责。
因此，刽子手可以在两个日子里自由选择行刑日。这意味着， 囚徒推出他将在星期六被绞死的推理是错误的。
如果我们愿意，我们可以假定囚徒推出星期日是惟一合乎逻辑的行刑日。但是这使得刽子手有同样的理由在星期六行刑，这同样说明囚徒的推理是错误的。
以上分析导致了两个并列的盖梯尔反例。假定事实上囚徒在星期六被绞死。表面看来，囚徒似乎是正确的。囚徒的信念是合理的真信念，然而，这并非真正的预先知道。囚徒没有意识到他的信念的败因:他有同样合理的理由相信行刑日是星期日。如上12:所述，如果假定囚徒必须在星期六被绞死，则推出他同样可以在另一天被绞死。囚徒的信念中的败因就是信念本身。
意外绞刑悖论是对演绎推理的一个警示。囚徒的推论是:他不可能在星期日被绞死，因此星期六是惟一的可能。致命的错误 在于，他以为排除了不可能的情况就保证其他的可能情况被留下来了。有时候所有的可能性都导致矛盾。律师的结论是法官的命令不可能得到执行，他的观点更加片面。律师和囚徒都没发现残酷的下一步推论:如果囚徒相信法官的命令不可能得到执行，那么刽子手可以在任何一天绞死他，甚至可以选择最后一天，而且绞刑将是意外的。
第七章 不可能性：期望悖论
你是一所大学的心理学系主任，正在主持一次奇怪的实验，实验对象是人。一个人A坐在桌边，接受心理学考试。另一个人B坐在他对面，监视他的进展。B面前有一个按钮。B被告知，按下这个按钮将使A受到惩戒性的、痛苦的电击(但是不会造成永久性伤害)。琼斯教授会定期走到A的旁边，指出一个错误答案，然后指示B按下按钮。
实际上A是琼斯教授的同伙。按钮没有接通任何东西，当按钮被按下时，A假装痛苦。琼斯进行这次试验的惟一目的是测试B，看他是否会执行“惩罚”A的命令。琼斯的一贯主张是，在权威人物的授意下，大多数人会执行残酷的命令。琼斯在10个不同的B身上做过实验，其中g个人按下了按钮。127
琼斯教授没有意识到，他本人正处于卡夫卡式的陷阱中:他其实是你的实验对象。你的兴趣是研究心理学实验中的“附加因素”，即“实验者偏见效应”。在心理学实验中，当一个研究者期望某个特定结果时，他得到这种结果的可能性更大。研究倾向于支持研究者的一贯主张—这意味着研究过程有问题。
换一种研究方法，可以消减或消除实验者偏见效应。在检验新药的实验中，实验以“双盲”方式进行，一些实验对象服用新药，另一些实验对象服用安慰剂(不含任何有效成分)，在结果出来以前，实验对象和实验者都不知道谁是怎么回事。这种设计防止了实验者对新药的热情感染服药者。
但是在某些心理学研究中，双盲设计几乎不可能。实验者必须知道正在发生的情况。他期望他的实验对象变得像纳粹一样凶残，于是，大多数实验对象如其所愿。相反，另一个实验者史密斯教授相信人本性善良，做了相同的实验，并报告说，在10个实验对象中只有一个人按下了按钮。这不是有意欺骗，这是潜意识的欺骗。史密斯和琼斯都倾向于按照对自己有利的方式解释模棱两可的结果。当琼斯让其实验对象按下按钮之时，其态度比史密斯更严厉、更专横。二者在选择实验对象B时都可能有意挑选以获得期望的结果。这两个研究者都没有意识到这一点，但是他们创造的预言具备使自身得以实现的力量。
如果实验者偏见效应比较强，对实验对象的研究将会受到强烈的影响。于是，你说服了一个大基金会资助你的实验。你的实验对象是其他一些对实际情况一无所知的心理学家。这个基金会给你足够多的钱，你可以资助琼斯、史密斯以及许多其他的研究者。你不关心这些人在他们自己的实验中发现什么，你惟一的目的是检测存在于研究者的偏见和他的结果之间的可疑的相关性。你已经观察了许许多多的心理学家，他们个性各异，对不知情的人类实验对象进行各种类型的所有可设想的实验。证据是明显128的:实验者偏见效应巨大而普遍。在百分之九十的场合，心理学实验的结果就是实验者期望的结果。
现在问题出现了。这个结果本身正是你所期望的。如果你的研究是正确的，那么针对人类实验对象的心理学实验的结果就是无效的。你的研究也是一个针对人类实验对象的心理学实验，因此，你的研究是无效的。但是如果你的研究无效，我们就没有理由相信实验者偏见效应，而你的研究也很可能是有效的，你的研究揭示了无效的研究……
第22条军规
小仲马(Alexandre Dumas fils)说过:“所有全称命题都是危险的，包括本命题在内。”这句话与上文的讨论相比，不仅是表面上的相似性。另外，“期望悖论”也令我们回想起约瑟夫·海勒(Joseph Heller)在《第22条军规》中描述的悖论性的情景:
只有一条军规—即第22条—具体提到，面对真实而紧迫的危险时，心智健全对个人的自身安全是至关重要的。奥尔疯了，因此他可以停飞。他需要做的只是提出要求。但是他一旦提出要求，就说明他不是疯子了，他必须继续执行任务。如果他继续执行任务，他就是疯子;如果他停止执行任务，他就是心智健全的。但是，如果他是心智健全的，他就不得不继续执行任务。如果他继续执行任务，那么他就是疯子，他就不必执行任务了;但是如果他不想执行任务，就说明他心智健全，必须继续执行任务。
比较一下普罗泰戈拉(Protagoras，约公元前480一公元前411)的著名故事(这个故事很可能是假托的)。普罗泰戈拉是智者学派的开创者，是古希腊最早的收费教师。一个跟随他学法律的学生和他达成协议:学生在打赢第一场官司之后付学费。①这个学生不受理案件，想以此逃避交学费。普罗泰戈拉不得不起诉学
生以讨回学费，学生则为自己辩护。如果学生输了，他不必付学
费:如果他赢了，他也不必付学费。
(无论如何，故事就是这么讲的。也许有人这样设想:如果
学生在他是否可以推迟受理第一场官司这个问题上赢得胜利，那
么普罗泰戈拉可以立刻向学生索取学费，如果必要的话，可以再
次起诉，因为学生已经板上钉钉地违约了。)
以上这些悖论的一个共同之处是，悖论中有一个概念(或集
①经作者同意，此处译文有改动。—译者注
合)可以自我包含。期望悖论的症结在于，这个实验研究的是以129人作为对象的这一类实验，而这个实验本身就属于这个类。关于包含自身作为元素的集合，最经典的表述是罗素的“理发师悖论”:在某个特定的镇上，理发师给每个不自己刮胡子的人刮胡子。更确切地说，他给且仅给不自己刮胡子的人刮胡子。他是否给自己刮胡子?这个理发师无法遵行这个规定。如果他不给自己刮胡子，他必须给自己刮胡子:如果他给自己刮胡子，他就不能给自己刮胡子。
以上这些都是伪装成谜题的悖论。乍一看似乎有个答案等待发现，而一旦你找到了答案，你会说:“啊哈!就是这么回事!”但是随后你会发现这个答案站不住脚。无论你怎么想，结果都是不可能的。这样的事有可能吗?
面对这类悖论，一种常见的反应是怀疑它们是否“可能”—也就是说，它们是否可能在真实世界中发生。在某些场合，答案是一个肯定的“是”。普罗泰戈拉的诉讼有可能发生(法官会面临困难的抉择);军方可能制定令人糊涂的、自相矛盾的规定(这样的规定很可能已经有了)。某个理发师可能为镇里除他本人以外的每一个不自己刮胡子的人刮胡子—这使得大家对他做出了一个与罗素的说法一样的判断—虽然他还是不能真正地符合这个判断。
实验者偏见效应已经得到了真实的实验的支持。(人们甚至为“实验者偏见效应”创造了一个专门的字母缩写:EBEo> 1963年，罗伯特·罗森塔尔(Robert Rosenthal)和福德(K. Fode)报告说，有三个研究显示了显著的实验者偏见效应。罗森塔尔和福德指派许多大学生去进行以人作为实验对象的假实验。向实验对象出示不同种类的人的照片，让实验对象判断照片上的人正在“经历成功”还是正在“经历失败”。大约一半主持实验的学生受到引导并相信他们的实验对象将倾向于回答“成功”;其他的学生则受到引导并期待他们的实验对象回答“失败”。最后，对假实验的实验报告进行比较。由于每次假实验获得的结果应当相同，所以如果结果中有差异，则应当认为差异是由实验者的期望造成的。罗森塔尔后来进行的研究进一步探索了实验者偏见效应。罗森塔尔如此关注这种效应，以至于主张未来的针对人类的实验也许不得不由自动化的程序引导，以避免这种效应的污染。
其他研究者无法再现罗森塔尔的发现。1969年的《咨询与临床心理学杂志》把争论推向高潮。这份杂志接连发表了一系列文130章:西奥多·色诺芬·巴伯(Theodore Xenophon Barber)及其同事仔细地重复了罗森塔尔的实验，但是发现完全没有支持实验者偏见效应的证据;罗森塔尔进行辩护性的反驳;巴伯发表火药味十足的反反驳。学术上的吹毛求疵演变为暴躁的潜流，最后导致了这样一个冷冰冰的声明:“罗森塔尔主张实验者偏见效应在男女混校的州立大学比在其他类型的大学或学院更易于发现，如果他的主张是严肃的，他应当拿出证据支持这个主张。”(罗森塔尔反驳巴伯说，巴伯的重复实验是在女子学院进行的，对此巴伯做出了如上回应。)
随后的实验进一步削弱了显著的实验者偏见效应的证据。1968-1976年间，至少有40个研究显示，不存在统计上的明显的实验者偏见效应，另外6个研究发现了实验者偏见效应的较弱的证据。
为了使期望悖论在现实世界中存在，必须确保期望效应既普遍有效又无法避免。如果只是某些心理学家受到这种效应的影响，不会产生问题。这样，实验者本人可以是一个小心谨慎、头脑冷静的心理学家，而他的同事马马虎虎，他可以研究同事的失误。正如“所有克里特人都说谎”这个悖论要求有一个克里 特人把它说出来，所有此类实验的不可靠性也需要一个同类的实验表达。
在现实中，期望效应不大可能表现为普遍的。因此，即使某个实际研究宣称发现了这种效应，这个研究本身也未必陷入悖论的漩涡。
没问题。但是如果某个实验真的确定了“所有针对人类的实验得出的结果都是无效的”这个结论—包括确定这个结论的实 验本身在内，将会如何呢?这有可能发生吗?①
“假”和“无效”是有差别的。如果一个实验的结果是假的，它就是假的，但是如果这个实验仅仅是无效的(由于粗心的操作、缺乏控制等等)，它的结果可能是真的，也可能是假的。一个无
效的实验可以支持一个碰巧为真的假说(我们可称之为“盖梯尔 实验”)。
对于说谎者悖论，假定其为真则推出其假，而假定其为假则推出其真。但是在这里，我们讨论的是期望效应实验的真/假还是有效/无效?问题并非一目了然。我们先列出所有的可能 性，就像处理逻辑谜题一样。131 (a)假定研究结果为真。如果它是真的，就意味着针对人类的心理学实验是不可信的。(这并不是说这些心理学实验得出的结果必然是错误的，只是说这些结论不足以从实验中得出。)于是本研究本身也是不可信的。其结论可能是真的—我们其实已假定其为真—但是本研究并不构成其结论的有效证据。这个研 究是一个盖梯尔实验。这种情况不无讽刺意味，但的确是一种可能状态。 (b)假定研究结果为假。也就是说，不存在普遍的期望效应。①这个问题有点不着边际。一个由实验确立的结论只能是归纳结论，所以不可能有普遍性—一旦认识到这一点，这个问题就没必要讨论了。如果一定要把这个实验的结论应用于这个实验本身，那不过是外推，而外推的失败再正常不过了。—一译者注
这个研究结果可能为假，它应当由于其他原因为假。(如果结论为假，那么研究就一定是无效的。)这又是一种可能状态。 (。)假定研究是有效的。于是，结论是真的，而且实验是无
效的—这是矛盾的。(d>假定研究无效。于是，结论可真亦可假:没有矛盾。
简单地说，如果某人做了一个研究，表明实验者偏见效应是普遍存在的，那么有以下三种可能:这属于情况(a)，结论碰巧是真的，但是研究是无效的，研究不足以支持其结论:这属于情况(b)，结论是假的，研究无效:这属于情况(d)，研究是无效的，真假不定。以上三种批评都是合理的。无如何，三种情况都表明:研究是无效的。
但是，如果有一群获得过诺贝尔奖的科学家组成了一个委员会，这个委员会指导这个研究，付出了最大的努力以确保研究的有效性，我们该如何评价这个研究呢?他们设计了前所未有的严谨的研究体系，包括细致的控制、统计检验、仔细地校验各个环节，以保证研究无可置疑地有效，并且_正确地断言:所有针对人类的心理学实验(包括本研究在内)都因潜意识的实验者偏差而无效。
这个问题的核心其实就是说谎者悖论，只不过把“真”替换成“有效”了。一个有效的研究恰好断言其自身的有效性是不可能的。我们的讨论进入了不可能性的领域。可能世界
“可能世界尸是哲学中的一个非常著名的概念。为什么世界是这个样子的?—这是一个很自然的问题。为什么会有邪恶?我们能提出这个问题，这就足以说明，我们可以设想一个没有邪恶的世界，这个世界与真实存在的世界截然不同。我们有理由认为，这种构想可能世界的能力是人类智力的最基本的部分之一。132我们在生活中做出无数的选择，所有这些选择无论大小都以想像力为基础。你想像了一个世界，在这个世界里你在今天下午洗了车;你又想像了另一个世界，在那个世界里你在今天下午没洗车。比较这两个可能世界，然后决定哪一个你更乐意生活于其中。
第一个广泛使用“可能世界”这个概念的西方著述者是德国数学家、哲学家莱布尼兹(Gottfried Leibniz, 1646-1716)。莱布尼兹感到奇怪，为什么上帝在创造世界的时候在所有的可能世界中选择了这一个。莱布尼兹给出了一个独特的答案:因为这个世界实际上就是所有的可能世界中最好的一个。他设想，这个世界中的痛苦和不幸是绝对的最小值。在造物主那里做出的任何一点改动，任何希望在这里或那里做一点修正的企图，都将把整个世界变糟。这种难以置信的观点再现于伏尔泰的讽刺小说《老实人康迪德》中，书中人物潘格洛斯博士(Pangloss)受到莱布尼兹的启发。康迪德无法相信，一个没有发生里斯本地震(1755年，4万人丧生)的世界怎么会不如我们的真实世界好。
20世纪60年代，索尔·克里普克((Saul Kripke )、戴维·刘易斯(David Lewis)、拉科·欣蒂卡(Jaakko Hintikka)等哲学家复兴了可能世界哲学。为了避免误解，我们澄清一下什么是“可能世界”。它指的不是在宇宙中的另一个星球。一个可能世界是一个完整的宇宙，它有自己的过去、现在和未来。我们可以谈论一个德国人打赢了二战的可能世界，我们甚至可以谈论那个可能世界的公元1万年。人们经常用单数的可能世界表示实际上的一类可能世界。一定存在着不止亿万个德国人打赢了二战的可能世界，其中的每一个都在某些细节上与其他的不同。存在着(或者说看来存在着)无穷多个可能世界。我们生活于其中的那一个可能世界称为“真实”世界。
即使这样一个纯哲学的概念也有其限度。如果任何一种随意的想像都构成一个可能世界，那么这个概念也就没什么用处了。多数哲学家同意，谈论一个并非可能世界的世界是有可能的。
虽然我们可以说出这样一个句子:"1十1不等于2的世界”但是这并不描述一个可能世界。类似地，"6是素数的世界”、“有四条边的五边形的世界”、“里斯本地震既发生过又没发生过的世
界”、“林肯比斯大林个头高、斯大林比拿破仑个头高并且拿破仑比斯大林个头高的世界”都不表达可能世界。
(有人对此表示异议。虽然任何人都无法设想一个1十1不等133于2的世界将是什么样的，但是冥顽不化的怀疑论者还是可以提出疑问:我们怎么就能保证这样一个世界是不可能的呢?大多数关于可能世界的哲学讨论都遵循一个基本规则:我们的逻辑无论如何在其他可能世界中也生效。不然，我们就没法思考它们了。)
有多少个可能世界
说某事是不可能的—不同于仅仅是假的—意味着在任何一个可能世界中它都不能为真。有多少个不同的可能世界?这是哲学中最深刻的问题之一。
索尔·克里普克主张，像“金的原子序数是79”这样的事实在任何可能世界中都是真的。大多数人则认为这种观点难以接受。看来很容易想像一个世界，其中金的原子序数是78,80或17.
关于金的原子序数，在你整个一生中你很可能从来不知道，或者没在乎过。表面看来，想像一个金的原子序数不同的世界与想像一个你的电话号码或车牌照不同的世界没什么两样。真是这样吗?
根据元素在周期表中的位置可以推测其性质。在表中，金位于银和铜之下，而性质与这二者在许多方面相似:密度大、柔软、惰性、金属类、导电性极好。如果金的原子序数加1或减1它在周期表中的位置会变化，而性质也应当不同。 假设金的原子序数是78。在周期表中它将位于镍和把下面，而性质应与这二者相似。它应当还是密度大的金属，但是性质会更接近铝(实际上铝的原子序数是78)。如果“金”在所有方面与铝相似，它还是金吗?
你可以坚持说，在周期表中其他元素的原子序数也会减1,于是金的相对位置保持不变。金是78号元素、铝是77号元素，以此类推。但是如果这样，在周期表的开端将不得不删掉一个元素。被删掉的应当是氢，这种元素构成恒星，目前是宇宙中最普 遍的元素。一个没有氢元素的宇宙是如此的奇异，以至于我们甚至无法相信它有多奇异。
克里普克断言，从化学家的角度说，元素的属性或多或少地、134不可避免地由其原了序数决定。设想在某个世界中氦不是惰性气体与设想在某个世界中1十1不等于2没有太大差别。确定某个世界是否可能不像表面看来那么简单!
也许有一天，我们的物理知识会达到与化学同样完备的程度。也许电子、夸克、光子的属性遵循某些根本的原则，就像化学元素符合周期表一样—这是可以设想的。“超弦”理论试图提供这样的理论。如果这类理论是正确的，许多似乎可能的奇异世界(例如质子比中子质量大的世界，电子的尺寸如同高尔夫球的世界等等)也许会被排除。物理学家甚至怀疑，真实世界就是惟一的可能世界。物理定律，甚至世界的初始状态也许已经被严格的逻辑所预先规定，我们几乎没有设想的余地。
悖论和可能世界
“这个句子是假的”是一个悖论—当我们做出这个断言时，我们的意思是说，在任何一个可能世界中这个语句都不能正确地描述自身。我们可以从两个方面分析:(1)如果这个句子是真的，那么这个句子是假的;(2)如果这个句子是假的，那么这个句子是真的。我们可以任意设想在某个世界中这个句子是真的或者假的，但是无论怎么设想，都会导致矛盾。
拉科·欣蒂卡利用可能世界定义知识。增加一个人的知识就意味着减少与此人的知识相容的可能世界的数量。例如，我们知道的所有事情都与半人马座阿尔法星系内存在生命相容;同时，我们知道的所有事情都与半人马座阿尔法星系内不存在生命相容。也就是说，如果有一个世界在各方面都与我们的真实世界相同，惟独在半人马座阿尔法星系内是否存在生命这一点上与我们的真实世界不同，我们的知识不足以鉴别这两个世界有何差别。而一旦我们知道了实际上半人马座阿尔法星系内是否存在生命，就有一半可能性被排除掉了。
科学发现消减相容的可能世界的数量。我们很自然地想问，这个消减的过程可以进行到什么程度。在欣蒂卡看来，完全知识意味着彻底排除所有的可能世界，只剩下一个世界—即真实
世界。
请注意全知与悖论之间的微弱差别。对于一个完全无知的人来说，与他的知识相容的可能世界的数目有无穷多;对于一个拥有完全知识的人来说，可能世界的数目被限制为一个。如果可能135世界的数目被限制为0，会怎么样呢?某个人遭遇这样一种困境:他发现所有的可能世界都与他的知识矛盾。他的已知事实集合包含矛盾。看来悖论顶多只能证明这不是一个可能世界。
博格斯在《乌龟的化身》一文中推测，悖论作为线索揭示了世界是不真实的:
让我们认可唯心主义的主张:世界在本质上是虚幻的;同时，让我们采取非唯心主义的方法:寻找世界的非真实性的证据来证实世界的虚幻本性。我认为，在康德的二律背反和芝诺的矛盾中可以发现这样的证据。
“最伟大的魔法师(诺瓦利斯令人难忘地记录过)可以向自己施展法术，其法术如此高超，以至于他本人在魔法的控制之下而浑然不觉，以为自己在自由地行事。我们不就是处于这种状态中吗?”我猜想情况就是这样。完满的神在我们体内驱使我们，令我们梦到了世界。我们梦想到一个稳固、神秘、可见的世界，在空间中弥漫、在时间中延续;但是我们承认，在这个世界的结构中存在细微而永远无法修补的非理性的裂缝，这些裂缝告诉我们，它其实是个梦。
序言悖论
我们都见过过分谦虚的序言—作者(在感谢自己的配偶和打字员之后)声明对“在所难免”的错误负责。你很可能觉得奇怪，既然他对于错误的存在如此有把握，为什么他不回去把错误 改过来，而只是做一个空洞的说明。受这种“不作为”现象的启发，梅金森(D. C. Makinson)提出了“序言悖论”(1965)。这个悖论与期望悖论和意外绞刑悖论都有联系，它“证明了”除非在文学作品中，这种情况不能发生。
一个作者写了一部巨著，他认为此书属于非文学作品。书中有许多命题，他仔细地检查过这些命题。一位朋友读了这本书，耸耸肩说:“任何一部如此长的书中至少有一处错误。”“在哪呢?”作者要求朋友指出来。而朋友断言，虽然他没发现任何错误，但是所有的长篇非文学类著作都包含一两个错误。作者勉强接受了朋友的说法。朋友说:“这么说，你的读者没有理由相信你书中的任何命题。”
“你看，”朋友说，“随便挑出一个命题。”他随机地翻到一页，找到一个陈述句。“我们暂且不看这个命题。我用手指挡住这个命题，让你看不见它。你是否相信，在这本书中除了这个命题以外的所有命题都是真的?”136“当然。除非我信以为真，否则我不会把命题写讲书中。我有非常合理的理由相信它们。”
“好极了。你已经同意:这本书中至少包含一个错误，尽管你我都未能发现错误。既然你相信书中至少有一处错误，而且你相信除了这个命题以外的所有命题都是真的，于是，你必须相信我正用手指挡着的这个命题是假的，否则你的信念就是自相矛盾的。我只是随便挑出了一个命题作例子。其实我可以把任何一个命题拿出来，进行完全相同的推理。对于书中的任何一个命题，你都不能合理地相信它是真的。”朋友下了结论。
为了避免误导读者，这个作者为这本书加了一个序言作为警告:“本书中至少有一个命题是错误的。”
如果这本书中包含一个(或多个)错误，则这个作为序言的命题是正确的。如果这本书中除了这个作为序言的命题以外没有任何错误，则这个作为序言的命题就是错误的。于是，这本书中确实有一个错误，而作为序言的命题是正确的。但是如果作为序言的命题是正确的，那么本书中就没有错误，作为序言的命题就是错误的……在再版时插入一系列的勘误表也无助于解决这个问题!①理的信念必须是相容的吗?
确实有许多实际的序言承认错误。小库尔特.冯内古特(Kurtdonnegut Jr.)的小说《猫的摇篮》就有这样一个序言:“本书中的东西统统是假的。”这与梅金森的序言悖论不一样，它是更直接的矛盾。不过好在冯内古特的书是文学作品，只要这个序言不应用于自身，它还是正确的。按理说，这个序言本身是真正的冯①作者对序言悖论的理解和介绍与常见的版本不同。一般认为，序言悖论的要点在于“相信”。根据常识，某人X既相信A又相信B,则可以推出，此人相信“A并且B"。序言悖论颠覆了这种想法。但是从作者的分析看，他显然把“相信”替换成了“是真的”。—译者注
内古特(而非小说中的人物)写的，所以序言不是文学性的。当序言涉及自身时，就产生了一个说谎者悖论。
序言悖论使我们回想起数学家威廉·尚克斯毕生悲剧性的工作。他一生致力于计算圆周率，他在计算第528位小数时出了错，导致以后的全部工作都无效了。设想你正在写一本名为《圆周率的数字》的书。书的第一页写道:“圆周率的第一个有效数字是30”此后的悔一页都承续上一页记录圆周率的十进制小数的下一位数字。你用手摇计算器得出数字。你是个有水平的数学家，采用的是公认有效的算法。因此，你有理由相信自己算出的每一个数字。
当你算到第1000位的时候，你发现，你很可能己经在计算137中犯了至少一个错误。哎哟!你的处境比梅金森的序言悖论还要糟。计算新的一位数字依赖于先前的计算结果(就像在长除法中一样)。你不能直接确定圆周率的第100()位数字，在此之前，你必须先确定第999位数字，而为此你必须确定第998位数字，如此等等。如果在计算某一位数字时出了错，那么随后的所有数字都是无效的。这就好比竖起1000枚多米诺骨牌，一旦第307枚骨牌倒向右侧，随后的每一枚骨牌都会倒下。如果在前1000位数字中至少有一处错误，则第ION)位一定是错的。①同样，第999位、第998位以及此前的一长串数字很可能也是如此。
和期望悖论一样，序言悖论质疑了在涉及归纳概率的、没有确定性的场合下演绎推理的作用。由于科学家借重于概率更甚于确定性，这个问题值得深思。
我们的世界观由一系列信念构成，这些信念大体上是真实、合理的(至少我们是这样认为的)。序言悖论提出一个问题:在合理的信念之中是否可能包含逻辑矛盾。请注意，在悖论内部包①这个数字有十分之一的概率是正确的。如果它碰巧正确，则构成一个盖
梯尔反例。—作者注含着悖沦。书的作者有这样一个信念:书中的每一个命题单独考虑都是真的，但是整体上书中一定包含错误。这个信念包含矛盾。假定这本书做出了1 000个不同的判断，这些判断都是正确的，而且相互一致;而序言中的声明(“本书中至少有一个命题是错误的”)是第1001个判断。这就产生了一个极为奇异的矛盾:虽然全部1001个判断构成的整体是自相矛盾的，但是从中任意取出100()个判断，则这1000个判断在逻辑上相互一致。
在小亨利·E"屈贝里(Henry E. Kyburg Jr.)提出的“彩票悖论”(1961)中，概率的地位更加明显。任何一个买彩票的人都不能合理地期望赢，因为相反的概率太大了。但是事实上总会有某个人赢，如果每个人都预计自己不会赢，则与这个事实矛盾。在实际生活中这个可疑的推理链条又向前推进了一步。“既然一定会有某个人赢，焉知这个人就不是我呢?”这个想法不符合理性，但是国家彩票的广告词就是这么说的。屈贝里认为，一个人的合理信念的集合可能在逻辑上是矛盾的。
梅金森的序言悖论和屈贝里的彩票悖论的深层问题在于，大量信念汇集在一起可能把矛盾隐藏起来。在一个由100万个命题构成的集合中，某个单独的命题可能引入一个微妙的矛盾。考虑138
这个连锁推理:
1.艾丽丝是个逻辑学家。
2.所有逻辑学家吃猪排。
3.所有吃猪排的人是克里特岛人。
4.所有克里特岛人是说谎者。
5.所有说谎者是出租车司机。
999997.所有得克萨斯人是富人。
999998，所有富人是不快乐的。
999997.所有不快乐的人吸烟。
1000000.艾丽丝不吸烟。
省略号表示其他前提，即第6-999996条。其中每一个命题都是“所有的X都是Y”这种形式，我们最终可以推出，所有的逻辑学家是吸烟者，由此得到艾丽丝吸烟。这与第100万条前提
矛盾。因此，这个命题集合是不可满足的(自相矛盾的)。
没有哪个前提格外值得注意。有趣的是，去掉任何一个前提都会使得整体变成可以满足的。例如，去掉前提4，则得到艾丽丝是克里特岛人，所有说谎者吸烟，艾丽妊不吸烟(因此艾丽丝
不是说谎者)。
在这个例子中，所有前提以整齐的次序排列，因而不难看出矛盾。如果这100万个前提打乱次序随机排列，发现其中的自相矛盾就非常困难了。如果其中某些命题采取了更复杂的形式，难度则更大。一个信念集合如同一个博罗梅奥环(Borromean Ring).或是那种抽出一片就使整体散架的智力玩具。每个命题的作用在整个集合中传播开来，对整体产生影响。
波洛克毒气室
一旦陷入悖论，人们的第一个反应是放弃一个(或更多)导致矛盾的初始假设。问题是，我们如何决定放弃哪个信念?约翰·L·波洛克(John L. Pollock )根据证实规则解决了序言悖论。他通过下面这个思想实验展示了证实规则:一个房间有时会充满绿色的毒气。为了警告那些可能想进入139的人，这个房间设计了一个警示系统。这个系统(由一个委员会设计)这样工作:通过门上的窗户可以看见房间里的一只警示灯。当可以安全进入时，灯是绿色的(表示“通过”):当房间里有致命气体时，灯是白色的(在某些亚洲国家白色代表死亡)。
糟糕的是，当房间里有毒气时，灯实际上是白色的，但是绿色的毒气使得灯看起来是绿色的，因此，这个系统没有用。无论房间里有没有毒气，灯看起来总是绿色的。委员会设法修补了这个缺陷。在距警示灯几英寸的地方安装一只闭路电视摄像头，视频信号传给房间外的彩色监视器。无论房间里是否有毒气，监视器精确地再现警示灯的颜色。在门上有一个警示牌，上面写明:不要理会通过窗户看起来灯是什么颜色的，以电视监视器反映的颜色为准。
波洛克用这个组装的警示系统比喻我们关于世界的不完善的知识。灯或绿或白，但是我们不知道是绿还是白。从窗户看，灯是绿的。表面证据让我们相信灯是绿的。但是在电视屏幕上，灯看来是白色的。这个理由让我们相信灯是白色的。但是灯是绿的意味着它不能是白的，反之亦然。在这两个原本可信的猜想中，我们必须放弃一个。
波洛克注意到，拒斥一种信念的方法不止一种。你可能会说:“通过窗户看灯是绿的。根据经验我知道，大多数窗户是用无色玻璃做的，玻璃不会使颜色走样。空气也是无色的。因此，通过玻璃看灯是绿的构成了一个合理的理由，我相信灯是绿色的。如果灯是绿色的，那么它不能是白色的。因此它不是白色的。”
当然，你可以同样容易地做出如下推理:“从电视监视器上看，灯是白色的。物体的颜色通常与彩色电视机反映出来的一样—这就是我们买彩色电视机的全部原因。因此，从监视器上看灯是白色的是一个合理的理由，我相信灯是白色的。如果灯是白色的，那么它就不能是绿色的。因此它不是绿色的。”
这样，我们得到了一个小型的悖论。从很少的几条观察出发，推出了一个矛盾。每个推理都对另一个构成针锋相对的反驳，反驳看来是以最强烈的方式进行的。
解决方案很明显。实际上灯一定是白色的，和电视屏幕反映的一样。但是我们采用的不是上面第二个推理。上面的第二个推理不见得比第一个强—也许还稍微弱一些。(当我们在电视上140看到的与亲眼所见的相冲突时，我们很可能更相信自己的眼睛。)
我们有另一个理由支持灯是白色的，根据室门上的警示牌。
一切经验性的信念都是可错的。我们可能得知某些东西(一个败因)，因而放弃了一个过去的信念—这种情况总有可能发生。有两种类型的败因:直接反驳型和釜底抽薪型。
直接反驳型的败因直截了当地指出一个信念是错误的。一旦得知在哥本哈根动物园有一群白乌鸦，这就直接反驳了“所有乌鸦是黑色的”这个猜想。我们还是有很多证据(见到黑色乌鸦的所有目击证据)证明这个猜想，而且这些证据依然是有价值的，但是我们不得不承认这个猜想是假的。
釜底抽薪型的败因则揭示支持此信念的证据是无效的。得知你实际上是一颗缸中之脑就是一个釜底抽薪型的败因，使得你相信的关于外部世界的一切东西都失效了。一个釜底抽薪型的败因使我们用一种新视角来审视支持某个猜想的证据，显示出这个证据其实不能用来证明这个信念。当然，信念本身也许碰巧还是真的，但是提供支持的证据不好。
初看起来，直接反驳型败因强于釜底抽薪型败因。但是波洛克认为，实际上釜底抽薪型败因优先于直接反驳型败因。二者的差别如同有趣的论辩与无趣的论辩之间的差别:在无趣的论辩中，针锋相对的双方各自指责对方是错误的;在有趣的论辩中，他们指出为什么对方是错误的。
关于灯的两种结论(基于从窗户获得的证据它是绿色的;基于从电视屏幕获得的证据它是白色的)都有经验理由支持，而二者互为对方的直接反驳型败因。这种相持不下的局面只能通过警示牌解决，警示牌属于釜底抽薪型的败因。它解释了透过绿色的毒气看见绿色的灯，灯的绿色可能是假象。这使我们有理由抛弃一个信念而坚持另一个。
釜底抽薪型败因优先的原则有助于我们理解本章中的大多数悖论(也包括意外绞刑悖论)。在序言悖论中，作者的朋友针对一个挑选出来的命题所做的论证是一个直接反驳型的败因，这个论证只是说此命题是错误的，并不解释为什么是错误的。这个论证与这个命题本身没有直接关联。实际上，这个被挡住的命题的内容从来没有进入讨论过程。
作者可以用一个釜底抽薪型败因反驳朋友的论证。朋友的推理立足于书中包含错误这一信念。虽然我们也许有非常好的经验，41理由(在其他书中都发现了错误和排印问题)支持这个信念，但是，一旦我们发现事实上除了朋友挑出的命题以外所有书中命题都是正确的，这个理由肯定会遭到破坏。如果非要认为书中一定包含一个错误，那么惟一的可能就是朋友挑出的这个命题是错误的，但是没有理由认为，这个命题出错的可能性比其他命题更大。在必须做出选择的时候，我们应当诉诸于釜底抽薪型败因。
序言悖论其实是一个玩笑。我们一直很清楚，朋友的推理是错误的，问题只不过是说明错在哪里。相比之下，期望悖论更难攻破。诉诸于釜底抽薪型败因，可以得到如下解决方案(当然这个方案未必是定论):如果一个论证指出某个实验的结果是假的，这个论证属于直接反驳型败因;如果一个论证指出某个实验是无效的，则属于釜底抽薪型败因。在关于期望效应的实验中，两种败因出现冲突。在这种情况下，根据波洛克的理论，我们应当优先考虑揭示无效性的理由，而非揭示错误性的理由。
考虑这个悖论的加强版:一个由著名科学家组成的超一流委员会指导这个实验，因而我们确信实验的有效性。直接反驳型败因是这样:如果实验结果是真实的，那么实验必定是无效的。然
而，由于我们知道实验是有效的(根据指导委员会的权威性)，所以结果一定不是真实的(根据否定后件式推理)。
釜底抽薪型败因是这样:如果实验既有效又真实，那么潜意识的期望己经危及了实验本身。我们遗憾地得出结论:实验是无效的。(需要指出，在这两种败因中，后一种更有道理。)最后讨论一下意外绞刑悖论。(当天数较多时，这个悖论与序言悖论的命题数较多的情况类似。)囚徒的推理反驳了他在一周内的任何一天被绞死的可能性(直接反驳型败因)。这样一组信念又构成了对自身进行颠覆的釜底抽薪型败因，因为刽子手在了解了囚徒的信念以后可以在任何一天行刑。釜底抽薪型败因优先的原则使我们接受奎因的结论:囚徒是错误的。
你可能会问，在什么条件下我们才能下结论说，某个命题得到了确切无疑的确立。答案是:永远不能。这说明以不可失效性作为“知道”的第四条标准是有麻烦的。任何信念都不能在败因面前免疫—包括“这是一个败因”这样的信念。142一个门卫走到波洛克毒气室门外检查监视器。他嘀咕道:“伙计，用这玩意儿警告大伙是一个天大的玩笑。除非某个人因此送了命，否则他们是不会有什么行动的。”他这么抱怨着，调了调显示器的旋钮，灯泡的图像变成了鲜艳的绿色。
第几章无限:汤姗森灯
“汤姆森灯，，[得名于詹姆士·F·汤姆森(James F. Thomson)看起来与其他灯没什么两样，由一个按钮开关控制。按一下按钮灯亮，再按一下灯灭，再按一下灯又亮。一个超自然的精灵喜欢这样玩这盏灯:把灯点亮1/2分钟，然后熄灭1/4分钟，再点点亮1/8分钟，熄灭1/16分钟，如此等等。" 1/2 + 1/4 + 1/8 +……”这个级数是我们熟悉的，它等于1。因此，到1分钟的最后一瞬为止，这个精灵按了无穷多次开关。在最后一瞬，灯是开着的，还是关着的?
每个人都知道，从物理的角度看这种灯显然是不可能的。然而，我们的想像力并不受凡俗的物理学束缚。关于此灯的操作描述己经达到了最大可能的逻辑精确性。为了判定灯是开是灭，我144们已经获得了全部的必要信息—看来这是不可辩驳的。此外，灯要么开要么灭—看来这也是不可辩驳的。
然而，试图解答汤姆森灯这个谜题是可笑的，因为这个问题等价于判定最大的整数是奇数还是偶数!
圆周率机
“圆周率机”更令我们不安。这是一种神奇的机器，外观像老式的收银机。打开这台机器，它开始迅速地计算圆周率的各位数字(圆周率是直径为1的圆的周长)。古希腊、罗马时代人们就已知道，圆周率是一个无限小数:3.141 59265 ......圆周率计算每一位数字所需的时间等于计算上位数字的时间的一半，通过这种方法计算所需的时间得到压缩。每当一位数字被确定，这个数字立刻弹入机器顶端的一个窗口中。在任意一个时刻，只有刚刚得到的数字会出现在窗口中。
如果计算第一位数字需要30秒，那么计算圆周率的所有数字所需的时间为I分钟。一1不仅如此，在1分钟结束时，机器将如假包换地显示出圆周率的最后一位数字!当然，这纯粹是痴人说梦，因为圆周率的最后一位数字不存在。
第三台不可能的机器是皮亚诺机。这台机器像是一只自动伸缩笛，笛子上标有刻度，像尺子一样。一端标有数字“O”，另一端标有数字“1"。一个游标从“1”端滑向“0”端，历时1分钟，匀速滑动。当游标经过的点的刻度为整数的倒数时，一只机械嘴会读出这个整数。随着游标的滑动，声调越来越高，这样，读数字越来越快。
例如，在这1分钟刚开始处，游标位于刻度1，而1的倒数是1，机器用厚重的男中音朗读“1". 30秒过后，游标位于刻度0.5, 0.5的倒数是2，机器朗读“2"(声音已经变成男高音)。又10秒过后，机器用女低音读“3"。又5秒过后，是女高音的“499o
在这1分钟接近结束的时候，朗读声变得迅速而猛烈。声调145逐渐增高，尖锐到人耳听不到的程度。有一阵子狗会发出呜咽声，狂躁地用爪子刨地……，而后狗的耳朵也听不见机器的朋读声了。在这I分钟结束的时候，每个自然数都被这个机器朗读出来了。
芝诺悖论
“无限”是一个用来表示这个巨大的、我们无法完全领会的①在一间屋子里同步运行圆周率机和汤姆森灯，屋子里没有其他光源，在 闪烁的照明下可以见到圆周率的所有奇数位数字。—作者注
世界的符号，它是悖论中极常见的主题。悖论中经常包含着无限对自鸣得意的日常世界的冲击和威胁。
在最古老的关于无限的悖论中，有一些归功于埃利亚的芝诺(生活于公元前5世纪)。芝诺在一本书中(大约写于公元前460年左右)记录了他的悖论，书己失传。芝诺好辩，乐于证明时间、运动以及其他我们习以为常的东西并不存在。他最著名的悖论是这样:善跑的阿基里斯与乌龟赛跑。乌龟在阿基里斯前面起跑，比方说，领先1米。为了追上乌龟，阿基里斯必须先跑到乌龟的出发点。当他到达这个位置时，乌龟已经往前跑了一段较短的距离—10厘米。现在阿基里斯必须再跑10厘米才能追上乌龟，但是与此同时，乌龟又往前跑了1厘米。以上分析可以无穷延续，乌龟领先阿基里斯的距离越来越短，但是阿基里斯永远也追不上乌龟。
芝诺否认无穷数列和无穷量的真实性。他认为，如果你可以表明某个东西涉及无穷，你就可以证明这个东西是不存在的。在现代人看来，芝诺的某些论证缺乏说服力。芝诺的表现就像是一
个永远拒绝无穷级数的顽固、古怪的数学家。阿基里斯必须跑的趾离构成了一个无穷级数，加起来等于111.111-"…厘米(即111又1/9厘米)〔1少，是一个有限数。所谓的“无限”只是芝诺分析的结果，并非物理意义上的无限。
在芝诺发明的悖论中，“弄矢不动”悖论更令人困惑。一支箭在空中飞过。在时间中的任意一个瞬间，这支箭是静止的。在这个瞬间中，箭就像处于一张静止的照片中，或者说，就像是在拍摄飞箭的电影中截出一个孤立的画面。时间是由无穷多个这样的瞬间构成的，既然在每个瞬间箭都是纹丝不动的，箭的运动何在?①这是一个等比数列，首项为100，公比为1/10，因此前n项之和为100(1-1110")/(1-1/10).当n趋于无穷时即为111又I/4o—译者注
吃矢不动悖论值得深入思考。我们把这个问题移植到现代语境中。我们有一支箭，它是由原子构成的。它在相对论的时空中运动，在一个惯性参照系中对它进行测量在这种表述中，我们146以日常含义使用“时间中的一个瞬间”这个词组，和芝诺一样。
我们依然接受因果关系:将来是由现在决定的，而现在是由过去 决定的。(除了在量子层次上—我们可以暂且忽略这种考虑吧?)在完全静止的一个瞬间中，一支飞行的箭与一支静止的箭有何不同?看来这支运动的箭上一定附着了一些信息以区别于静L[的箭。否则，它怎么“知道”在下一个瞬间疾射向前?
就本书的讨论范围而言，我们更关注当代人的“无限机器”悖论。这些悖论是在芝诺的启发下诞生的。他们质疑的是知识，而非运动学。关于无穷级数的现代理论无助于消解这些问题。每台机器的操作都属于超级任务，其动作涉及无限。然而，这些动作可以清晰地描述—尽管动作本身也许是不可能的。在每个例子中，超级任务允诺我们瞥一眼不可知的事物—例如希腊神话中的美杜莎①。
注重实际的人也许会对无穷机器的想法表示质疑。关于超级任务的哲学讨论就好比医生为一种并不存在的疾病寻找疗法。然而，超级任务可以和真实世界中的某些过程类比。这些问题中表现出来的奇特状态只有通过由一系列离散的动作组成的无穷(或接近无穷)的序列才能得到解答，这是值得研究的。
造一台汤姆森灯
关于无穷机器的某些讨论关注操作细节。虽然机器的实用性(1)美杜莎为希腊神话中的女妖，任何人看她一眼就会变成石头。美杜莎是不能石一的，所以“弊一眼”美杜莎是不可能的，作者以此类比“超级任务”，说明超级任务是不可能的。—译者注似乎与讨论无关，但是略微分析一下细节也许有助于发现其中的逻辑困难。阿道夫·格林鲍姆(Adolf Grunbaum)分析了所有这三台机器。
针对汤姆森灯的一种反对观点是，电灯泡不可能无限迅速地打开、熄灭。在操作过程中的一个过去的确定时刻，当电流接通时灯丝没有足够的时间完全加热，而当电流断开时灯丝没有足够的时间冷却。在最后阶段，灯丝可能始终处于半明半暗的状态。
此外，每个人都知道，开关电灯泡很容易把灯泡烧坏。汤姆森灯的灯泡一定会烧坏。
阿道夫·格林鲍姆认为，这些讨论没说到点子上。问题的关键是，在这1分钟结束时，灯泡是亮的还是灭的?即使灯泡烧坏了也不要紧，在这1分钟过后，我们总可以卸下坏灯泡，拧上一个新的，看看它亮不亮。
真正的问题在于开关。汤姆森灯的开关按钮在每一次打开147或关闭时，显然要经过一段距离。因此，按钮必须在有限的时间内经过无限的距离。一个物理上的限制足以提出反驳:在这1分钟接近结束时，按钮的运动速度定会超过光速，而这是不可能的。
按钮将往复运动无限的距离这个问题并不重要—实际上，按钮不需要走这么远。格林鲍姆和艾伦·贾尼斯(Allen Janis )做了一点改进，得到了升级版的汤姆森灯。改进之后的情况更有
道理。
把按钮画成一个垂直的圆柱，其底部是导电的。当按钮被完全按下时，圆柱的底部接触电路的两个裸露电极，电流流过圆柱底部，点亮灯泡。
每当灯应当点亮时，按钮接在连通的电路上;每当灯应当熄灭时，按钮以恒定的速度沿上下方向做一个短程运动。每一次按钮弹起的距离仅限于时间允许的范围内，而运动速度是固定的。
灯每关闭一次距离减少4倍
在最初的30秒，按钮压在电极上，灯泡是亮的。再过15 秒，灯泡关闭。按钮先用7.5秒向上弹起，又用7.5秒回落。然后，按钮在电路上停留7.5秒，这段时间电路接通，灯泡又亮了。再往后，按钮用1.875秒向上弹起，用1.875秒回落，灯泡保持熄火3.75秒。
按钮起落无穷多次，但是每一次移动的距离都是上一次的四14:分之一，就像是一只弹性不大好的球。在整个操作中，按钮移动的总距离同总时间一样，是个有限数。移动速度是常数，比光速小得多。
遗憾的是，格林鲍姆和贾尼斯的改进还是不能彻底挽救汤姆森灯。按钮在往复运动的过程中需要加速和减速，而加速度会超过任意的固定值。看起来，无限大的加速度毕竟比无限大的速度容易接受，但是……任何物理对象都只能承受一定限度内的加速度。在某一时刻，加速度肯定会摧毁按钮，其效果就和用锤子砸碎的一样。
改进版的汤姆森灯有一个更严重的问题:在1分钟之后灯是开是灭已经不是问题。在操作过程中，按钮的底部与电路之间的距离越来越小，最终恰好停在电路顶上。(就好像一只球在地板上蹦，最终落在地板上。)改进版的汤姆森灯在操作结束时一定是亮的。修改开关的结构就会导致这种令人不满的结果。这个改
进版的汤姆森灯与原来的汤姆森灯有关系吗?—确实成问题。在设计圆周率机和皮亚诺机时也会遇到一些问题，有的与上面的问题类似，有的则否。〔顺便说一句，皮亚诺机的名字是格林鲍姆起的，为了纪念意大利数论家朱塞佩·皮亚诺(GiuseppePeano)o]圆周率机的问题是，计算圆周率的数字的过程怎么可能这么快。下文将提到，计算速度如同运动速度一样，是有上限的。在数字向窗口中弹出的过程中，为了避免运动速度达到无限，运动的距离必须递减。最终，我们将无法判断正在显示的是哪个数字。圆周率机可以换一种显示模式，每个数字被打印出来，数字的字体表现为超现实主义风格:每个数字的高度是上一个数字的一半。全部计算结果可为一张索引卡片所容纳。但是有一个问题:即使最强大的电子显微镜也看不出最后一位数字是几。
皮亚诺机有一个独特的问题:数字的读法越来越长。干净利落地读出一个100位的数也要花很长时间。贾尼斯建议不采用日常语言的读法。他的方案是，设计一个编码方法，让每一个数对应于一个频率确定的音调，然后用哨音把数字“吹”出来。
发出一个声音需要消耗多少能量取决于频率(音调)和振幅(音量)。为了避免能量需求达到无穷大，随着频率的增加振幅必须减小。在这1分钟的最后一瞬，机械嘴的音量控制将下降到O。149你无法听到最后的哨音—即使你的耳朵有能力捕捉音调无限高的声音。
请注意:如果试图以更具物理上的可实现性的方式设计三种无限机器中的任何一种，都会导致一个结论—最后的结果是不可见的(或不可闻的)。许多哲学家认为，在涉及无限机器、超级任务以及只有通过超级任务才能了解的事实时，总是有些可疑的东西。
几何级数
无限—完全就本意来说—是不可理解的，但是趋近于无限的情况随处可见。根据一个印度传说，什里姆国王(KingShirim)曾经落入西萨·本·达希尔(Sissa Ben Dahir)的圈套。达希尔是国王的大臣，发明了国际象棋。国王钟爱这种游戏，决定重赏发明者。因为国际象棋棋盘有64个格子，国王决定为每个格子赏赐达希尔一块金子。达希尔礼貌地谢绝了这份赏赐，恳请国王以另一种方式奖励他。他请求国王在棋盘的第一个方格上放一粒麦子，在第二个方格上放两粒麦子，在第三个方格上放四粒麦子，依此类推，每个方格上的麦粒数是上一个方格的二倍，直到棋盘的每一个方格上都分配了麦粒。
感于达希尔的谦虚，国王收回成命。国王命令拿来一袋麦子。麦粒按照达希尔的要求仔细地数出来。当国王的仆人们应付第12个方格时，他们己经无法把所有的麦粒放进方格里了，只好把大臣应得的麦子在棋盘旁堆成一堆。国王吃惊地发现，第20个方格还没被满足，一袋麦子就耗尽了。他下令取来更多的麦子……最后所有的麦子都用完了。他的王国的所有麦子加在一起也无法满足达希尔的要求，不仅如此，全印度乃至全世界的麦子加在一起也不够用。
这个故事的寓意在于，永远不要低估几何级数。当然，在民间故事里挖掘出数学含义有点奇怪。根据国王最初的想法，赏给达希尔的金子直接和棋盘包含的方格数成正比。如果达希尔设计的棋盘不是64个方格，而是81个、49个或者其他数字，从国王的角度说都没有太大的差别。区区几块金子与国王的财富相比，算得了什么呢?
然而，几何级数的增长超出世间的任何限制—对于财富或任何其他东西都是如此。达希尔的要求以麦粒为单位，麦粒的价值与金块相比微不足道，但是这个事实对最终结果几乎没有影响。
我们看一下，多少粒麦子才能满足达希尔的要求。这个数是150 1 +2+4+8+…，换一种写法即20+2`+22+23+ ---262+263。(这个级数的最后一位是263，不是26" ,因为第一个方格中的麦粒数是20,即1)
以2为公比的几何级数的和总是等于最后一项的二倍减to1N如，20+2' +2 Z(=1+2+4>等于23减1(即8减1>。所需的麦粒的总数是264-1，等于18 446 744 073 709 551 615.1吨麦子大约包含1亿粒麦粒，因此，所需的麦粒大约为2000亿吨。现在的小麦年产量仅有4.6亿吨。国王欠下达希尔相当于4个[irt己的小麦产量的债务(以现在的年产量计)。显然，当时的小麦产量比现在低得多。(我们不知道这个故事发生在多久以前，因为国际象棋的发明时间不能确定。和篮球一样，国际象棋发生过几次变形，此外，我们不知道历史上是否确有达希尔其人。)
马尔萨斯灾难
托马斯·马尔萨斯(Thomas Malthus)认识到，世界人口以几何级数增长，而粮食产量仅以算术级数增长，在此基础上形成了他的著名理论。马尔萨斯有理由相信，每年新开垦的农田面积是固定的。因而，粮食供给的增长大致是这样:100, 102, 104,106...…另一方面，人口的增长率(主要取决于每年的新生婴儿数)随人口规模本身增长。世界人口趋向于每隔若干年增加一倍，他的增长情况大致是:1, 2, 4, 8, 16, 32--"…和达希尔的奖赏一样，这是一个几何级数。马尔萨斯警告说，人口增长必定超过食物供给，一导致全球性的饥荒。
用“几何级数”这个术语来称呼这种级数并不恰当，把这种级数类比于几何既不形象又容易引起混淆。一个更恰当的术语是“指数级数”，这个名称源自“指数”这个术语。生长的有机体以
指数增长为特征。无论是细菌的繁殖还是人类的繁衍，其共同特征是，新增个体数与总数成正比。复利存款也呈指数增长—这显然与这一事实有关:借方和贷方都是生长的有机体，他们创造了指数增长的经济，而目.，他们进行交易时依据的货币处于呈指数增长的通货膨胀中。
指数增长可以用简单的数学函数描述。所谓函数是从一个数151转换为另一个数的过程。你可以把函数理解为袖珍计算器上的一 个特定的键。你先在计算器上输入一个数，然后按这个键，得到一个新的数。例如，开平方函数(许多计算器上都有开平方键)会产生一个数，此数乘以自身后得到最初输入的那个数。如果先输入36，再按开平方键，得到60函数不仅限于可以在计算器上找到的。任何一个从某个数产生新数的清楚而确定的过程都是函数。我们可以定义一个函数:67乘以n加上381(对于任意数n)，这就是一个有意义的函数。函数通常用方程的形式表示，例如:
f(n)=67n+381 "f(n)”读作“n的函数”。
我们很自然地想知道，哪种动物最大、什么动物运动最快。同样，数学家也想知道，哪一种函数最大，或者增长最迅速。有些函数胜过其他函数。如果在n足够大时，一个函数的值总是大于另一个函数，那么我们说前者比后者大(或者说增长更快)。例如，函数A是A(n)=1 000 000 000 000 000，而函数B是B(n)=n,则在很大一段期间里B较小。但是当n取大于1000 000 000 000 000的任意数时，B (n)大于A(n)。因此，B(n)的增长比A(n)快。
以上这些函数都不算大。任何一个常函数—即f(n)等于一个固定值的情况—最终一定会被一个与n成正比的函数超过。同样明显的是，这两种函数都会被与n2成正比的函数超过。与n3成正比的函数最终会增长得更大。类似地，对于与n4, n5, n6等等成正比的函数，也是如此。
多项式是一个表达式，由一个变量的各次幂组成，例如n3 +8n 2一17n十3。一个多项式表达了一个函数。粗略地说，一个多项式
函数的相对增长速度取决于它的最高次幂。函数矛+8矛一17n+3的增长速度远远超过任何最高次幂为n2的函数。同理，它将被一个最高次幂为n4(或更高)的函数超过。
许多函数的增长还要快。马尔萨斯的悲观论点立足于一个事实:指数函数的增长超过任何多项式函数的增长。在一个指数函数中，某一个特定的常数以n为指数(而非n以某个常数为指数)。f(n) = 3”是一个指数函数，它表示3乘以自己n次。当n为2时，3"即32，等于9。当n为1时，结果即等于底数(这个例子中是1523);当n为0时，无论底数是多少，结果都定义为1。于是，对
应于0, 1, 2, 3, 4...…函数值分别为1, 3, 9, 27, 81...…每一项的值等于前一项的3倍。底数越大，函数的增长越快。对于10"，每一项是前一项的10倍;而对于1 000"，每一项是前一
项的1000倍。
在复杂性理论中，表示一个问题的困难程度的最常用的标准是解决此问题所需的时间。不用说，每个人的工作效率是不一样的，计算机也各不相同。同样重要的是，针对同一个问题算法可能不!卜一种，而某些算法比其他的更快。解决各种类型的问题所需的时间差异如此之大，这使得计算机与计算机之间(以及人与人之间)的计算速度的差别已经不重要了。
需要强调的是，某些问题可以用“多项式时间”解决，而另一些问题需要“指数时间”。这意味着，解决一个问题所需的时间可以表达为关于问题的规模(或复杂度)的一个多项式函数(或指数函数)。如果一个问题需要指数时间，则通常令人绝望。无限机器也许只是胡思乱想，但是指数时间问题却是真实而普遍 的。解决这类问题需要接近于无穷多的步骤—即使问题出现在有限的宇宙中。
下一章将讨论多项式时间问题与指数时间问题的差别以及这个问题与悖论的关系。现在，研究两个质疑时空无限性的悖论。
奥尔贝斯悖论
1826年，德国天文学家海因里希·威廉·奥尔贝斯(HeinrichWilhelm Olbers)意识到宇宙中有些东西不对劲。天文学作为科学的一个分支，不能回避无限的问题。物理宇宙要么是无限的，要么是有限的。但是对于大多数人来说，这两种可能性都不容易接受。
布莱斯·帕斯卡(Blaise Pascal)写道:“每当我设想，我的生命被封闭在永恒的时间中的一个狭小的范围内，我能看到、能感知的一小部分空间淹没于一个无限广裹的空间中，我对这个无限的空间一无所知，这个无限空间对我毫不在乎，一想到这些，我就对自己身处于此地而非别处感到恐怖和震惊。”另一方面，153一个有限的宇宙也许令人更加难以接受。人类的心灵难以设想空间怎么会有尽头。
这种不安并非新问题。希腊哲学家卢克莱修(Lucretius)认为，他的论证足以证明空间是无限的:假定空间是有限的，那么空间有一个边界。让某个人达到这个终极的边界，把一支标枪掷过边界。这支标枪要么穿过边界，要么被什么东西挡住—某个本身必定在边界外的东西挡住了它。无论是哪一种情况，都说明在边界外存在某种东西。以上操作可以不断重复，推动这个所谓的边界无穷地倒退。
在奥尔贝斯的时代，大多数天文学家把空间的无限性当做理所当然的。奥尔贝斯对无限时空的反对被当做痴人说梦，他也因此而闻名。假定宇宙是无限的，而星体(还有星系，虽然奥尔贝斯那个时代的人还不知道星系)在各个方向上无限地延伸出去。在这种情况下，从地球发出的一条直线—无论其方向如何—必将与一颗星体相遇。
当然，这条直线也许在延伸数十亿光年之后才与某星体相遇。关键在于，在一个散布着星体的宇宙中，这条直线最终必定遇到一个星体。这就好比这种情况:如果我们在轮盘赌上玩足够
长的时间，那么任何一个号码肯定都会出现，不会有例外。
太阳是一颗恒星，在我们的天空中，看起来有宽度的恒星仅此一颗。如果太阳距我们的距离增加到现在的十倍，那么它的表观表面积将只有现在的百分之一，亮度同样下降到百分之一(根据很久以前就己确立的亮度递减公式)。如果太阳距离我们100万倍远，它将暗1万亿倍，它在天空中的大小将比现在小1万亿倍。需要注意的是，在天空中，单位面积上的亮度保持不变，与距离无关。无论太阳距离地球多远，单位面积上的亮度是固定的。奥尔贝斯意识到，这个简单的事实蕴含着一个悖论。
在夜空中，其他星体只占针孔大小，但是这些针孔(平均而言)与太阳表面一样亮。光沿着直线传播。如果从地球出发的一条直线与某颗星体相遇，我们可以见到这颗星体发出的光。如果从地球出发的每一条直线都与某颗星体相遇，那么整个天空应当充满相互交叠的星体光盘，其中每个光盘与太阳的光盘一样明亮，所有光盘融会在一起，遍布整个苍育。这个图景就好像太阳是一个空心的球体，而我们位于球体的中心。阴影之类的东西不会出现，也不会有所谓的夜晚—夜晚其实就是阴影。
太阳无处不在，阳光永不停歇地照耀。也许你会认为，某些黑暗的对象会挡住星光，令我们看不见。但是在这种环境下，不可能有任何黑暗的东西。所有东西都会吸收、传播或反射光(通154
常三种情况都有)。任何吸收光线的东西(如月球、星尘、这本书、你的眼睑)会吸收热量，直到其温度达到星体本身的平均温度，而后他们将发出同样强度的光。任何完美地传播光线的东西(一块理想的玻璃)是完全透明的，不会产生任何阴影。反射光线的东西(如同镜子)应当反射出与背景同样耀眼的光，我们分辨不出来。
这就是奥尔贝斯悖论。当然，整个论证显然是错误的。这个悖论令奥尔贝斯闻名，但是他并非最早沿着这个思路设想的.人。托马斯·迪格斯(Thomas Digges )、埃德蒙·哈雷(EdmundHalley )、爱德加·艾伦·坡(Edgar Allan Poe)以及其他人关注过这种观点，但是在儿个世纪的时间里没有受到重视。显然，和前文讨论的无限机器一样，这个悖论针对一个无限性的问题(宇宙是否无限)提供了一个短平快的、轻桃的答案。反对“多”
把望远镜倒过来看，会见到有趣的图景。类似的想法可以导致一个悖论，这个悖论可视为芝诺“反对多的悖论”的升级版。我们知道，即使最短的线段也包含着无穷多个点。这么说，一个核桃壳内部也存在着无限的空间，同辽阔的星际一样不可测量。
“坚固”的物质是由原子构成的，而原子内部大部分是空的空间。非空的部分是质子、中子和电子，而这些粒子大部分也是空的空间。如果空间是无限可分的，就会有一个无穷的序列:粒子、亚粒子、亚亚粒子，而它们大部分是空的空间。也就是说，任何东西的99.999 999%以上都是空。果真如此，我们应当无法看见任何东西，如同格特鲁德·斯坦(Gertrude Stein)提到“奥克兰”一样—那儿什么也没有。
利用物理学可以简单地解决这个悖论。原子中的电子散射可见光。电子可以像波一样在空间中展开，实际上，整个原子被电子“笼T 11着、“覆盖”着。另一方面，电子可以被当做一个无限小的粒子，永远无法进入其内部。原子核中的质子和中子不散射普通光。’F
为了使这个悖论成立，我们必须假定自己有一种超级视力:当且仅当从你的眼睛发出的一条绝对直的几何直线遇到一个被物质占据的点，你就会看到东西。这样，当你看一个核桃壳时，你(f)原著此处有笔误，译文己更正。—译者注看到的不是核桃壳，而是成千上万的由电子和组成电子的夸克(或者组成电子和夸克的终极的亚粒子)构成的点。侮个东西看起来‘55都像是不规则的尘埃碎片。由于我们看不到单独的、无限小的点，所以每个东西都应当是不可见的。奥尔贝斯悖论的解决
现在回到奥尔贝斯的宏观悖论。关于这个悖论的任何解决方案都必须立足于三个前提:宇宙是无限的;星体随机分布;没有任何东西阻止远方的星体发出的光被我们看到。这三个前提是预
设的。
一种解决方案是，假定星体的分布类似于上一节讨论的亚原子物质的分布。这两个悖论交相辉映，合在一起考虑两个问题都可解决。为了解决奥尔贝斯悖论，瑞典数学家沙利耶(C. V. L.Charlier)提出，星体不是任意地散布在各处，而是聚集在层次分明的体系里。现在我们知道，我们附近的星体都属于一个星系—银河系，而银河系本身是一个星系群—本星系群—的一部分。本星系群是一个更大的结构的一部分，这个结构称为本超星系团。这个本超星系团又是双鱼座一鲸鱼座超集结综合体的一部分……如果有一天有人宣布双鱼座一鲸鱼座超集结综合体是一个更大的东西的一部分，我们不会太吃惊。
沙利耶表明，在这个无穷无尽的层级结构中，即使星体的数量是无限的，悖论也可以避免。例如，也许某个由星系构成的超超超星系团离我们过于遥远，以至于在我们的天空中，它的图像恰好被隐藏在大角星或参宿四之类的微小天体后面。应当有一些超超超星系团和超超超超星系团距离我们极其遥远，这使得它们看起来甚至更小。根据沙利耶的设计，在大多数方向上，我们的视线无限延伸以后也碰不到一颗星体，因此，夜空是黑暗的。
从几何的角度看，沙利耶的解释是可以成立的。惟有一个原因使这个理论失败:它似乎无法解释已经观测到的天体层级结构的相对距离和大小。附近的星系虽然朦胧模糊，但是比附近的恒星大得多。仙女座星系非常昏暗，但是视直径是太阳或满月的数倍。南方天空的麦哲伦星云(距我们的星系最近的两个星系)的大小相当于一颗距我们一臂长的柠檬。附近的星系团甚至更大。例如，肉眼不可见的室女座星系团占满了整整一个星座区域。156现代人对奥尔贝斯悖论的解决诉诸于一个20世纪以前还不
为人知的事实:宇宙处于膨胀中。所有我们可见的星系都在以巨大的速度远离我们的星系。我们无法直接测量这种运动，但是它造成了从这些星系发出的光的改变，我们接收到的光透露了关于运动的信息。如果不假设这种运动，光的这种变化是无法解释的。位于天空中侮一个确定区域的星系都在离我们远去;在地球另一面的天空中，星系也在离我们远去，只不过方向相反。
对这一现象的一种解释是，我们的星系是“特殊的”，它处于宇宙的中心。另一种解释同样可以很好地解释这个现象:整个宇宙都在膨胀。这种说法很方便，但是有点容易引起误解。这种膨胀不是彭加勒所说的那种完全均匀的膨胀，而是以长度标准不变为基础的膨胀。地球和银河都没有变大，也许甚至本星系群也没有变大。但是星系团之间的距离越来越大。从理论上说，我们可以用尺子测量星系间的距离膨胀，因为尺子并没有膨胀。
根据宇宙膨胀假说，不需要假定我们的星系或它在宇宙中所处的位置有何独特之处。那些遥远的星系中的居民也会发现，自己处于膨胀“中心”。这个假说不需要假定我们的星系是特殊的，由于少了这个无关要求，所以这个假说更好。
我们所知的、距我们最远的星系在以接近光速的速度远离地球。一个高速远离的物体发出的光会产生“红移”:光的波长增大而能量减小。能量较高的可见光在红移以后变成能力较低的微波。当一个发光体以接近光速的速度远离时，它发出的光能量将下降到几乎完全消失的程度。因此，我们接收到的非常遥远的星系的光能量非常微弱，以至于不可见。
我们来看一下以_L知识对奥尔贝斯悖论的论证有何影响。设想我们把整个宇宙空间划分为以地球为中心的一系列同心球壳层。由于光的强度与距离的平方成反比，我们从各个壳层接收到的光(平均而言)强度相同。所有距太阳系10光年以内的星体发出的光应当与趾离在10光年至20光年之间的星体发出的光强度相同。距离在30光年至40光年之间的星体，乃至于距离在1000000光年至 1000010光年之间的星体也是如此。
如果宇宙是无限的，所有这些光的总量是一个无穷级数的和，大致为x+x十x+x+x+…，其中x表示从每个壳层发出的157光。这种类型的无穷级数不收敛，求和会导致无限。
但是由于来自更远的壳层的光受到红移效应的削弱，以上图景全变了。星系距我们越遥远，它远离的速度越大，光的能量越小。因此，这个无穷级数更像这样:x+0.9x+0.81x+0.729x+0.656 lx + ---，其中每一项按固定的比例递减。这样的无穷级数是收敛的。无穷多的星体照耀地球的天空，而光的总量可以依然是有限值。
很少有宇宙学家怀疑这个悖论可以用宇宙膨胀合理地解释，但是还存在一个更简单的解释。1720年，埃德蒙·哈雷(EdmundHalley)写道，天空的黑暗反驳了星体有无限多。今天，许多宇宙学家相信宇宙确实是有限的(虽然他们的出发点不同于奥尔贝斯悖论)。广义相对论提供了一种解释，使得有限的宇宙不必有一个令人难以接受的“边界”。空间可以自身弯曲，这个三维结构可以类比于一个球的表面。在地球上，如果你走足够远，无论朝哪个方向，你都会回到出发点。空间本身也许同样如此:一只火箭如果沿一条直线飞行足够远，它将回到发射点。
根据大多数当代宇宙模型的预言，如果宇宙中的物质密度达到或超过一个确定的限度，那么宇宙就是这样一个有限的宇宙。
已观察到的可见物质(星体)的密度低于这个限度，但是据推测，存在着足够多的不可见物质(星际间的氢、黑洞、中微子?)以建立一个有限的宇宙。最近关于遥远的星系和类星体的“引力透镜”效应的研究支持了有大量不可见物质存在的想法。特里斯特拉姆·香迪悖论
人们对待时间和空间潜意识地使用双重标准。时间的无限性似乎与空间的无限性略有不同。我们很自然地认为，空间向各个方向无限延伸(或许这是文化遗传的结果?)，而时间则被认为仅在未来的方向上是无限的。我们追问时间的起点，但是很少追问空间的起点。
“时间在过去的方向上是无限的”不是一种广为接受的信念。不过这个信念可以“回答”“世界是何时以及如何被创造的”之类的问题，因为如果时间在过去的方向上是无限的，那么这类问题就是无意义的。相反，“时间在未来的方向上是无限的”则得到了普遍接受，甚至那些以先知预言为基础的宗教都接受这个想158法。干年盛世到来后，善者永生:或者在一个新的世界中轮回。即使某些极端虚无主义的教派相信，时间有一个真实的终点，在终点处万物归复于虚无，与时间的起点之前完全相同，只有时间本身是善的，即使这种信仰存在，也是非常罕见的。罗素的特里斯特拉姆·香迪悖论(paradox of Tristram Shandy)巧妙地利用了“无限未来”这个概念。特里斯特拉姆·香迪是劳伦斯·斯特恩(Laurence Sterne) 18世纪60年代的漫游小说《香迪传》中的健谈的故事讲述者。罗素写道:“如我们所知，特里斯特拉姆·香迪用了两年时间来记录他的生活中的头两天的历史，然后他抱怨道，按照这种速度他永远也写不完。但是我认为，如果他可以永远活下去，而且坚持不懈地写下去，那么，即使他的一生始终像开端那样充满需要记录的内容，他的传记也不会遗漏任何部分。”
罗素的论证大致是这样:假定香迪生于1700年1月1日，而写作开始于1720年1月1日。在第一年(1720)写第一天(1700年1月1日)的事，写作进程如下:
等等
每一天对应于一年，每一年对应于一天。如果香迪的写作工作持续至今，在1988年，他将进展到1700年9月的事件。按部就班地，不死的香迪将在大约106 840年记录今天的事件。对于任何一天，在未来都有指定的一年去记录它，绝无例外，因此，罗素说:“他的传记不会遗漏任何部分。”即便如此，香迪的写作工作将越来越滞后。他每写I年，距离最后竣工就远了364年!
罗素的论证以乔治·康托尔(Georg Cantor)的无穷数理论为基础。如果在两个无穷量之间可以建立起一一对应关系，则这两个量相等。例如，数学家认为，所有正整数①(0, 1, 2, 3, 4, 1595,…)的个数与所有偶数((0, 2, 4, 6, 8, 10...)的个数相等，虽然有些人可能认为，前者是后者的二倍。二者相等，因为任何一个正数数n可以与一个偶数2n配对，而如此配对不会遗漏任何偶数。
更令人费脑筋的是克雷格(W. L. Craig)提出的一个悖论，①原文为“整数”。笔误。—译者注这个悖论是特里斯特拉姆·香迪悖论的颠倒版。假定时间在过去的方向上是无穷的，而香迪已经写了无穷长的时间。克雷格指出，在这种情况下，在年与日之间仍然存在康托尔-一一对应。香迪应当刚刚完成他的传记的最后一页。但这是荒唐的。既然他要花费一整年的时间记录昨天的事件，他如何可能已经把昨天的事件记录完了呢?
克雷格以及其他人用这个颠倒版的悖论证明无限的过去是不可能的，虽然这个证明不那么令人信服。罗宾·斯莫尔(RobinSmall)针对颠倒版的香迪悖论提出了一个合理的答案。答案是:实际上在特定日和特定年之间不可能建立一一对应。
假定现在是1988年12月31日午夜，香迪刚刚完成他的手稿的最后一页。在过去的一年里，香迪记录的是哪一天的事?不可能是这一年中的某一天。(否则就意味着，在这一年中这一天以前的时间里，香迪己经开始记录尚未到来的一天。)在1988年他可以记录的最邻近的一天是1987年12月31日。
如果香迪用1988年记录1987年12月31日，那么他必须用1987年记录1987年12月30日，这又是不可能的。实际上，在1987年他不能记录1986年12月31日以后的任何一天。
但是，如果他在1987年记录1986年12月31日，那么他不得不在1986年记录1986年12月30日……我们可以设想的任何一种对应方式都会遭到反驳。所谓的香迪一直在写的那一天向过去无穷倒退。它不可能是任何一天。
结论:如果过去的时间是无限的，而香迪始终在写，那么他将留下无穷多的未完成的写作任务。他最近完成的部分记录的是无穷远的过去的事件。
实际上，罗素版的悖论和克雷格版的悖论都不难解决。罗素从来没说香迪终将完成他的手稿。罗素的意思是，我们无法找到香迪不能记录的一天。香迪的“最后”一页始终是一个遥不可及的海市屋楼。
第九章 np完全：崔本迷宫
若热·路易斯·博格斯的小说《歧路花园》l)描述了一个迷宫，这个迷宫极其复杂，以至于没有人可以走出来。故事的讲述者说到他知道了道路的方向，然后开始跑题了:
指示说一直向左拐，这让我想起，走迷宫的一般方法就是如此用这种方法可以发现一个确定的迷宫的中心点。我对迷宫有研究。我是崔本的曾孙，这可非同寻常。崔本曾经管辖云南省，后来辞职，专心写一部小说，这部小说本来也许会比《红楼梦》更著名。同时他还在建造一座迷宫，任何进入迷宫的人都会迷路。他花了13年时间做这两件没什么关联的事，直到一个陌生人把他谋杀了。他的小说看起来语无伦次，他的迷宫也消失了。我在英国的树下沉思这座失传的迷宫:我想像这座迷宫是至高无上的完美巅峰;我想像它161消失在稻田下或水底;我想像它是无限的，不是由八角形的亭子和往复的路径构成，而是由河流、省份和王国构成……我构想的是迷宫的迷宫，一个错综复杂的迷宫，它涵盖过去和未来，并且以某种方式把星辰包括进去。
“迷宫”这个词起源甚早，而含义不固定。在古希腊罗马时期，迷宫是一种建筑，至少有一部分在地下，故意设计得令人转①又译为《小径交叉的花园》。—译者注向。希罗多德(Herodotus)认为，鳄城附近的埃及迷宫(建成于公元前1795年)是一个比金字塔还伟大的奇观。这座迷宫包括3000个房间，一半在地上、一半在地下，柱子像森林一样茂密，一直延伸到视力所及的范围之外。希罗多德游历了地上的一半迷宫，但是未被获准观赏地下部分。他被告知，神鳄在地下守护着法老的墓穴。许多古代作家记录了这座迷宫的逐渐衰落，它的遗址始终没有消失。1888年发掘了它的地基，大小是800 x 1 000英尺。
在西方文化中，最著名的迷宫是古希腊克里特岛上的弥诺陶迷宫。在希腊神话中，弥诺陶是一个牛头人身的怪兽，居住在一个巨大的迷宫中央，这座迷宫是代达罗斯为克里特国王迈诺斯设计的。在克里特打败稚典之后，迈诺斯国王下令，雅典人每九年向弥诺陶进贡七名童男和七名童女作为祭品。这些进入弥诺陶迷宫的人无一生还。雅典王子特修斯自愿作为祭品进入迷宫。迈诺斯的女儿阿里阿德涅告诉特修斯，进入迷宫时沿路展开丝线，这样就能找到出路。特修斯用这种办法杀死了弥诺陶，终止了进贡。
这个神话故事也许是根据雅典进贡者的传说演化而来的。在克里特人的制海权处于巅峰时，雅典派人向克里特进贡。也许他们在克里特见到了一些他们不理解的东西(莫非是一个戴着牛头面具的神秘教派的祭司?)，而后他们的故事逐渐变形了。我们 知道古代克里特的迷宫是什么样的，我们甚至不知道它是否真的存在。在克里特语中，“迷宫”可以指迷宫一样的建筑，岩洞或者曲折的山洞(克里特地形以岩洞为特色)，或者在推理中导致的不可解的困境一一即悖论。在克里特文明衰落以后，克诺索斯宫殿遗址被称为“迷宫”，也许只是为了讽刺性地把它比做岩洞。+2残存的克诺索斯钱币显示，他们有一个迷宫规划，它似乎是一个 人工建造的迷宫，不仅仅是天然的岩洞。20世纪初，考古学家
在克诺索斯发现了宫殿残骸，但是没有发现什么与迷宫相似的地方。
另一个隐藏存传说中的沐宫是罗莎蒙德闺房( RosamondBower)，据推测，它建于12世纪的英国伍德斯托克(W oodstock )的一个公园里。国王亨利二世把自己的情妇罗莎蒙德女士(Rosamond the Fair，约1140一约1176)藏匿于这个非常玄妙的迷宫中，以免自己的妻子阿基坦的埃莉诺(Eleanor of Aquitaine)发现。亨利利用一个秘密的“窍门”找到正确的路线，到达幽会地点。根据传说，埃莉诺也找到一个“窍门”:她沿着一根丝线追踪，也到达了迷宫的中心，令罗莎蒙德饮鸡自尽。这个故事是假冒的，在14世纪以前尚未出现。罗莎蒙德闺房是否真的存在，以现代的眼光看它是否称得上迷宫，这些问题都很难说。不那么浪漫的历史学家猜测，它不过是一个设计简陋的房子，外面有一些迷惑人的通道。
现代迷宫差不多都是花园迷宫，通道两侧用角树(在英国常见)或紫杉组成篱笆封死。都铎王朝时期和斯图亚特王朝时期，花园迷宫在英国很兴盛。迷宫的设计者通常留出一条有记号的秘密路线通向出口，这是走迷宫的窍门。知道这个窍门，就可以毫无困难地找到出路，出入自如。迷宫留下许多奥妙。走迷宫问题属于NP完全问题。它是一类普遍性的问题中的一个，有可能难倒最强大的计算机。
NP完全
世界就是一个由纵横交错的关联和关系组成的迷宫。" NP完全”这个名称客观而准确地表达了这种状态。从字面上，"NP完全，，是“非确定性多项式时间完全”( nondeterministicpolynomial-time-complete)的缩写。这个令人望而生畏的术语定义了一个基本而普遍的问题种类，在哲学思辨和实际应用两方面都有重大意义。
NP完全问题是30年来始终困扰着计算机程序员的一类问题。计算机自问世以来，速度越来越快，功能越来越强。20世纪 80年代末的计算机大约比SO年代末的计算机快3万倍。有一个炫耀的说法:“如果汽车技术的发展与计算机技术保持相同的速度，那么一辆劳斯莱斯汽车应当以超音速行驶，而价格低于1美 元。”然而，在20世纪60年代中期，计算机科学家开始意识到163有些事不对劲。有些普通问题极难用计算机解决(也很难用己知的方法处理)。采用更强大的处理器或者投入更大的内存也无法产生可以期望的差别。这些问题逐渐被称为“难以处理的”或“内在困难的”。
“旅行推销员”问题即为一例。许多古老的谜题书都介绍过这个问题。这是一道数学题:一个推销员必须到达几个城市，城市之间的距离已知，要求你为一个推销员设计一条最短路线。这个问题击败了最强大的计算机。关键在于组合数学，一个不太大的集合产生数额巨大的组合。解决这个问题的己知的最好办法不比比较每一条可能路线的总英里数高明多少。随着城市数的增 加，计算量如雨后春笋般膨胀，很快就突破了任何可以设想的计算机的计算能力。
NP完全作为一类问题首次在1972年的一篇论文中得到清晰的表述，论文的作者是加州大学伯克利分校的理查德·卡普。从此以后，NP完全在几十个意外的领域受到关注。小孩的谜语、谜题、游戏和脑筋急转弯中有许多是NP完全问题的例子。如果 找到了高效率地解决NP完全问题的“解法”，那将是价值连城的发现(不过大多数计算机科学家认为不大可能找得到)。美国、前苏联以及其他技术发达国家的军事安全目前以NP完全为基础①，而这个基础并不牢靠，在信息时代，再没有什么比这更令人如芒在背了。超级大国的敏感数据是用“公开密钥”密码保护的，这种密码以大型的、实际不可解的NP完全问题为基础。类似的密码为商业私人数据和政府数据库提供安全保障。许多种类各异的①原著出版时，苏联尚未解体，军备竞赛如火如茶。—译者注问题实际上是相互等价的，这个发现在哲学上也是发人深省的。毫无疑问，“很少有技术术语像‘NP完全’这样快速地声名远播”—麦克尔·R·加里(Michael R. Garey)和大卫·S·约翰逊(DavidS. Johnson)影响广泛的著作《计算机与难以驾驭性:NP完全理论导论》(1979)就以这句话开篇。
" NP完全”是一个非常难以理解的抽象说法。我们最好用具体的例子解释一下。迷宫不仅可以用来比喻我们对知识的探求，在方法论上迷宫等价于我们的逻辑方法(从一个适当的、164抽象的视角看)。迷宫预示了演绎方法中的核心问题—悖论发现问题。
迷宫算法
我们以这个问题开始对NP完全的探讨:是否存在解迷宫的一般方法?
是的。事实上，存在几种方法。并非所有的迷宫都需要动脑筋。单行线迷宫从头到尾都只有一条通道，没有岔道，没法走错。许多中世纪的迷宫迁回曲折但是没有岔道，惟一的通道通向一棵树或一座神殿。早期的英国教堂墓地设计成这种类型的迷宫，象征迂回曲折的人生道路—虔信者在世间邪恶的诱惑下穿行。
克诺索斯的弥诺陶迷宫可能就是没有歧路的。钱币的图案显示了一条没有岔道的通道。如果你在这样一座迷宫里遭遇弥诺陶，你只需做一件事:掉过头跑。你永远都不会走进死胡同。另外，也许这些钱币只是表明一种设计风格，而非一张真正的地图。还有一种可能:这些图案也许展示了在更复杂的通道网络中应当怎么走。除非有岔道，否则用不着拿一根丝线标记路线。
每座迷宫至少有一个入口，而且大多数迷宫有一个终点—在迷宫中你试图到达的一个地点。终点通常在迷宫的中心附近， 当然，终点也有可能只是迷宫边界上的一个出口。、，解迷宫的目的是找到一条路线，从入口走到终点。路线也许只有一条，也许有多条。当连接入口和终点的路线不止一条时，一个潜在的谜题是发现最短路线。
有些迷宫入口不止一条。这与入口惟的迷宫并无本质的不同。你的第一个选择是从哪个入口进入，这个选择是在进入迷宫以前做出的，但是这与在迷宫内选择路径没什么两样。有些迷宫有多个终点，要求游客走遍迷宫的各个部分，或者一系列由雕像、长椅或其他东西标示出来的地点中的每一个。路易十四在凡尔赛建造了一个著名迷宫，游客需要找到39座根据伊索寓言设计的雕塑。每座雕塑都是伊索寓言中说话的动物，喷泉从它们的嘴里165喷出来。最后，还有一类迷宫是没有终点的，这种迷宫的走法是进去闲逛，然后找条路出来。
在迷宫格局中，每个分岔处称为一个“节点”。节点是通道交叉的地方，在节点处你必须做出选择。入口、终点和死胡同的终端也被视为节点。两个节点之间的通道称为一个“枝”。任何迷宫都可以用简化的图来表示，在图中，“节点”用点表示，“枝”用线表示，点和点之间用线连接。用数学术语来说，迷宫是一个 “图”。
几乎所有物理形式的迷宫都是二维的。这意味着，枝和枝之间从不交叉。在三维迷宫中可以有天桥和地道，枝和枝可以互相穿越，如同高速公路的立交桥。
在图上解迷宫和实际地走迷宫不是一回事。面对谜题书上印出来的迷宫地图，通常利用眼睛就可以解决，人眼会自动地把迷宫当做一个“完形”。但是当你身处于一个实际的迷宫内部时，通道两侧被篱笆或石头封闭，你很难在心里形成一个整体图像。
高明的设计者会把某些节点设计得非常相似，让你觉得自己在老①经作者同意，此处删掉了一个中国人不易理解的例子。—译者注路上兜圈子，而实际上你到达的是一个新地点。此外，在图上解迷宫可以用一些由来已久的方法，例如，把终点当做起点进行倒推(这种方法有时使问题简化，有时更麻烦)，或者勾掉所有死胡同，从而使路线变得更清晰。但是在实际的迷宫内部，这些法子都用不上。
迷宫的难度与各节点处发出的枝的数量息息相关。如果每个节点处都只有一个枝，这个迷宫一定是单行线迷宫。我们可以把节点想像成两颗珠子，在珠子之间有一条线，无论这条线如何盘旋环绕，一个不变的事实是它总是连在两颗珠子之间。沙特尔教堂的迷宫就是单行线迷宫，这个迷宫没有墙，是用蓝色和白色的大理石在地板上铺出来的。
如果每个节点处有两个枝，迷宫同样毫无难度可言。我们可以把它设想成一堆珠子串在一条线上。走这样一个迷宫时，你不用做出选择。实际上，你通常不会把连接两个枝的连接点视为一个节点。把这两个枝看做连续的一个枝更简单，所谓的节点不过是在这个枝上打了一个结。
在迷宫里，一个真正的岔道至少需要通道汇聚在一个点(三条路形成三岔路口)。节点处汇聚的枝越多，迷宫就越难走。
大多数近年来的迷宫按照习俗采用了接近直线的设计，道路和限制通道的篱笆构成密密麻麻的蜂巢，填满整个区域内。这使得迷宫比每个节点发出四个枝还要难。凡尔赛迷宫采用了更灵活的设计。各个枝不必要地平行，许多枝汇聚在一个单独的节点上。166最高记录是一个节点上汇聚了5个枝。凡尔赛迷宫的设计师安德烈·勒诺特雷(Andre Le Notre)在尚蒂伊建造了另一个迷宫，其中心节点汇聚了8个枝。
下表介绍了关于几个著名迷宫的统计数据。有几处，节点和枝的数目应当如何计算有待商榷。在每个场合，细心的游客需要做出决定的地点都被我算做一个节点。入口、终点和死胡同的终端也被当做节点，但是只有两个枝的冗余节点被排除在外。最后一列是平均每个节点汇聚的枝的个数，这个量大致反映了迷宫的难度。
凡尔赛迷宫
右手法则
最著名的迷宫算法是“右手法则”:每当你面临选择时，选最右面的枝。如果走到了一个死胡同，折回来退到上一个节点，选择你没走过的枝中最右面的一条。为了具体地应用这条法则，最好的办法是始终用右手摸着右侧的篱笆，决不漏掉右侧的枝。
当然，右手本身没什么特别之处。采用“左手法则”一样行得通。惟一需要注意的是，一旦进入迷宫，必须坚持同一条法则。
为什么这条法则行得通?它不是一个单纯的习俗。“按顺时针方向拧紧螺丝”是一个单纯的习俗，但是你完全可以制造一颗方向相反的螺丝。右手法则比简单的习俗更深刻，它依赖于迷宫
的拓扑结构。
我们来研究一张画在纸上的迷宫的规划图。被篱笆封锁的区域涂成绿色，绿色区域之间的白色部分是迷宫中可以通行的部分。在许多迷宫中，被篱笆封锁的区域连成一片。此时实际上只有一道篱笆，尽管它可能是蜿蜒曲折。这个迷宫看起来像是一个形状诡异的国家。对比地图上的国家，代表国土的绿色区域被边168界线包围。边界线是一条单独的封闭曲线(边界线对应于迷宫的篱笆)。这条曲线的任何一个部分与任何一个其他部分是连在一起的。因而，走迷宫的时候，只要把右手放在篱笆上耐心地往前走，一定会经过迷宫的所有部分。
前文提到童子军迷路算法①—沿着溪流可以找到有人烟的地方，实际上，右手法则的基本原理与此类似。整个北美是一块大陆，北美的海岸线—包括江河构成的凹陷—是一条封闭曲线。沿着河岸或者海岸线走最终一定会到达新奥尔良(也可以到达任何一个位于河流或海岸线上的地点)。在迷宫中，也许会包①见第五章中“复杂性”一节。—译者注含被篱笆分隔开的“岛屿”，但是，只要入口处的篱笆和终点处的篱笆属于同一个岛屿，右手法则就可以生效。
右手法则(或者左手法则)的优点是简单。它的缺点有两个:其一，效率不高。跟随这条法则你会走遍右侧(或左侧)的每一条死胡同。在大多数场合，存在一条通向终点的短得多的路线。更糟糕的是，右手法则并非在所有迷宫中都能生效。显然，所有已知的、在19世纪20年代以前建造的迷宫用这条法则都能走通。此后，数学家斯坦诺普伯爵设计了一个更复杂的迷宫，坐落在肯特郡的切佛宁。
切佛宁迷宫有八个被篱笆分隔开的“岛屿”，因而右手法则不再有效。入口和终点不在同一个岛屿上。如果你依照右手法则走这座迷宫，你会围着一个区域兜圈子，永远无法到达终点。(就好比在长岛沿着河岸和海岸线走永远无法到达新奥尔良。)这类迷宫需要一个更复杂的算法。
特雷莫算法
所有更强大的迷宫解法需要某种方法以确保自己不是在兜圈子。你需要在路上做标记，沿路放丝线、撒面包屑、折弯树枝，如此等等。否则，你必须有极好的记忆力，能记住篱笆的形状，并且保证自己能认出所有曾经走过的地点。
有一种名为“特雷莫算法”的通用方法可以确保解决任何迷宫问题。根据法国数学家爱德华·卢卡斯(Edouard Lucas)的《娱乐数学》(1882)一书的记载，这种方法是特雷莫(M. Tr6maux )发明的，因而命名为特雷莫算法。这种方法可以说是前文提到的特修斯沿路放丝线的方法的精细化。
特修斯沿路放丝线保证自己可以原路返回入口，不至于迷169路。但是丝线不能帮助特修斯找到弥诺陶的窝。特修斯可能会走到某个岔路口，发现自己在兜圈子。当他决定下一步选哪一条路
时，他可以利用这个信息加以改进，这种想法是合理的。特雷莫算法就是这么做的。
切佛宁迷宫(篱笆围成的外部“岛屿”以黑色表示)
走进迷宫后，首先随便选任何一条路，沿路做记号，可以用丝线或任何就手的东西(下文的叙述采用面包屑。)一直走，直到达到目标(如果走运的话)，或者一条死胡同，或者迷宫中的一个你以前来过的岔路口(证据是你留下的记号)。
一旦走进一条死胡同，退到上一个节点。(你别无选择!)记住在回来的路上也要做记号。如果你曾经在一条死胡同里一进一出，路上将留下两行面包屑。这个记号提醒你下次不要再走进去。在特雷莫算法中，任何一条路你都不会走两次以上。
当你走到迷宫中的一个以前来过的节点时，(可能是通过另:70外一条路来过，)如下操作:如果你是从一条新路到达的(也就是说，你的身后只有一行面包屑)，转回身沿原路退回上一个节点。否则:如果有一条没走过的路，选择这一条。否则:任选一条以前只走过一次的路。这就是全部需要遵守的规则。根据特雷莫算法，你会在迷宫内完成一次完整的旅行，每一条路你都走过了两次，两个方向各一次。当然，在到达终点以后就可以停下了，没有必要完成整个巡回，o
和右手法则一样，这种算法的效率极低。当然，你有可能非常走运地从入口直接走到终点，但是可能性更大的是，你走完了迷宫的大部分甚至是全部以后才到达终点。
在什么时机采用右手法则或者特雷莫算法都不算晚。你可以走进一个迷宫，随心所欲地走，在迷路以后再采用算法。在任意一个点都可以开始执行算法，把这个点当做另一个“入口”。特雷莫算法将引导你从这个点出发完全地游历整个迷宫，包括终点和实际的入口。这两种算法不仅可以用于花园迷宫，在令人转向的建筑中也有效。如果你在五角大楼或罗浮宫迷路了，你可以利用特雷莫算法走出来。
无限的迷宫
设想一个无限延展的迷宫。这个迷宫无边无际，遍布整个世界，所以根本没有入口和边界。你从迷宫中的任意一个点开始探索，你不知道自己在这个宏大的迷宫中的位置，正如我们不知道自己的星系在宇宙中的位置。
这个迷宫的结构非常简单。在每个节点上，恰好有三个枝交汇。各个节点通过标记相互区分，雕像、长椅、树木等等，各种各样的东西都可以充当标记，你寻找的终点可能是其中的某一个。
和所有其他迷宫一样，这个迷宫在本质上也是非理性的。在寻找一个给定的目标的过程中，没有哪一条路比其他的路更优先。任何一条路都可能是“正确的”。正确与否依赖于这个迷宫是如何建造的。这个迷宫的结构是通过无止无休的自我复制实现的，在复制过程中又加入了变化—意识到这一点令人绝望。假定一个游客花了若卜年探索迷宫中的一个特定区域，到达了已知171区域的边界上的一个岔路口。他面对两条未探索过的枝，其中一条通向他寻找的标记，但哪一条是呢?实际上，在整个迷宫中他己经探索过的部分一定会多次重复，在某些重复结构中，熟悉的路线连接迷宫的其他部分，因而，右侧的路通向终点;但是在其他场合，左侧的路才是正确的。当然，这个游客没法知道他的当前处境属于哪种情况。对于任何企图以理性的方法选择路线的计划，这构成了一个嘲讽。
假定你处在这个无限的迷宫中，闲逛了一段时间之后，绝望地发现自己迷路了。你没有沿路做标记，也不知道自己究竟走了多远。
在这个困境中，你不想采用特雷莫算法。只要你没有和以前走过的路交叉，特雷莫算法就不会对你的行动给予任何指导。你有可能在迷宫中深入若干英里，越陷越深。在一个无限的迷宫中，你甚至有可能从未与自己走过的路交叉，从未见到终点，也从未再次遇到熟悉的地点。
特雷莫算法和右手法则预先假定，即使走遍迷宫的全部或一个很大的部分也没什么大不了的，只要确保自己不是在不停地兜圈子，最终到达终点就行。特雷莫算法实际上鼓励优先探索迷宫中较远的区域。根据此算法，选择未走过的枝总是优先于熟悉的枝，而且，除非不得已，尽量避免与自己走过的路交叉。在有限的迷宫中，这些建议是合理的，因为终点几乎总是距离入口相对较远。否则的话，迷宫的主人浪费了自己的地产，付给维护灌木的园丁工资，却没有增加迷宫的趣味性，这是没道理的。
但是在无限的迷宫中，你不能浪费时间在未知的区域漫无目标地闲逛。当你迷失方向、但确知目标比较近(与迷宫的整体大小相比)时，你应当首先探索邻近的区域，在必要时向外扩展。耶鲁大学的厄于斯泰因·奥尔(Oystein Ore)在1959年介绍的一种算法就是如此。
奥尔算法
为了解释清楚这种算法，最好假定你从一个节点开始。如果你的出发点不是一个节点，那就走到最近一个节点。如果不知道172叨a个方向通向最近的节点，随便选一个方向，走到你遇到的第一个结点。这个点就是你的出发点。
从出发点开始，探索交汇于此的每一个枝。在进入每一个枝的时候，在入口处放一块鹅卵石。对每一个枝的探索仅限于到达F一个节点，然后在这个枝的终点处放一块鹅卵石，原路返回出发点。
如果遇到死胡同，做一个标记。一旦对一个枝做了标记，以后就忽略这个枝。做标记的方法可以是在死胡同的入口处拉一条封锁线，或者摆上一排鹅卵石。
如果某条路转了一圈又回到最初的节点，也把它标记为死胡同。这种路对你也是无用的。
你的兴趣在于确定那些通向有新枝的新节点的枝。在探索的第一个阶段结束之后，每一条有可能通向终点的潜在路线都已经做了记号—路的两端各有一块鹅卵石，而你重新回到了出发点。
下一步，探索的深度达到两个节点。沿着每一条非死胡同的枝走到新节点，从这个新节点出发探索每一条由此辐射出去的枝，探索方法照旧。在最初的那个枝的两端各加一块鹅卵石(此时，这个枝的两端各有两块鹅卵石)，对于新探索的第二级的枝，两端各放一块鹅卵石。这个办法可以防止你找不到返回出发点的路，返回出发点的路有一个特点:路口处的鹅卵石比其他路多一块。和第一阶段一样，对死胡同和兜圈子的路做标记，予以排除。如果一个枝通向以前探索过的节点(这个节点至少有一块作为记号的鹅卵石)，在这个枝的两端也做标记，予以排除。
探索的第三步，深度达到距出发点三个节点，在每一个探索过的枝的两端各加一块鹅卵石。依照以上规则不断推进探索步骤，直到发现终点、入口或者其他想找的东西。
奥尔算法可以确定通向终点的最短路线(所谓最短是指枝的数量最少，而非物理距离最短)。当然，你的探索过程不是最简的。但是，如果最短路线需要经过五个节点，你一定可以在探索的第五个阶段发现它，而且可以确保它是最短的。
奥尔算法的效率同样低得可怜。它不是直接对准正确的路线，而是检查所有可能的路线。这是必不可少的，因为任何一条路线都可能是正确的。迷宫的NP完全性
下面考虑一个问题。这个问题也许可以称为无限迷宫问题。你位于E点(E点代表入口，不过这个点和其他点一样，淹没于、73无边无际的无限迷宫中)，你在寻找‘点，这个点代表终点，终点可以是迷宫中的任意点。你不知道G点在哪儿，无法在地图上对G点定位(根本就没有地图)。你确信，如果你走到了终点，你可以认出来，因为终点处有一个己知的标记。根据以上对迷宫的明确规定提出我们的问题:“连接E点和G点的简单路线是哪条?”
所谓的“简单路线”，是指不自身交叉的路线。如果路线自身交叉，就是在兜圈子。兜圈子总是不必要的，而简单路线要求成本较低。简单路线可能不止一条。如果存在多条简单路线，其中最短的一条更受欢迎。但是对于一条简单路线是否具备“最短”这个优点，你小是很在乎。毕竟，探索这个无限迷宫是一个令人恐惧的任务，几乎任何一条通向G点的路线都是令人满意的。
另一个问题与无限迷宫问题密切相关，这个问题可以称为“迷宫存在性问题”:是否存在从E点通向G点的简单路线?
我们来看一下为什么这个问题比较简单。一旦无限迷宫问题得到了答案(具体指明了一条路线)，这个答案本身就回答了存174在性问题:简单路线确实是存在的。即使无法具体地指明一条路线，在某些情况下，有可能表明简单路线是存在的。我们很自然地认为，一个只需回答“是一否”的问题要比一个也许需要为一个长达数十亿个枝的路线不厌其烦地定向的问题简单。
只有怀疑主义者才会问存在性问题。大多数迷宫探索者有一个基本信念:所有的点是以某种方式连在一起的，从此处总可以走到彼处。尽管路线可能曲折而漫长，但是它毕竟是存在的。然而，实情未必如此。有这样一种可能:迷宫是骗人的，它只有问题却没有答案。也许所有道路构成了两个互相缠绕但彼此分离的网络，从一个部分无法到达另一个部分。即使假定整个迷宫属于一个单一网络，对此我们也永远无法证明，因为我们的知识仅限于迷宫的局部。在一条具体的路线被发现并得到证实以前，我们总是可以设想通向目的地的路并不存在。
这个“存在性问题”属于NP完全问题的一种，称为“最长路径”问题。NP完全问题以“困难”著称，但是这个存在性问题有时不难回答。例如，当G点碰巧距离E点只有一个枝时，随机的探索几乎会立刻发现G点，存在性问题和无限迷宫问题同时得到解决。
这很正常。一个一般性问题的特例有可能非常简单。我们要寻找的是解决存在性问题的系统化的通用方法，对于最简单的迷宫和无限的迷宫都有效。
对于一个未知的迷宫，不存在快速的解法，事先我们无法知道哪条路更好。我们所能采取的最好的方案就是检验几乎每一条路，直到发现终点。各种各样的迷宫算法其实只有一个功能:避免不知不觉地兜圈子或者在已知的死胡同和环道上浪费更多的时间。在探索迷宫中的新领域时，算法不能给你“聪明”的指导。
我们看一下奥尔算法，这个算法的效率和其他算法一样。你从出发点开始。这个节点发出了三个枝。每个邻近的节点同另外两个节点相连。(在一个邻近的节点上有三个枝，其中一个枝把这个节点与出发点连在一起，这个枝已经考虑过了。)这六个点中的每一个依次与另外两个节点相连，新的节点距离出发点又远了一层。迷宫的节点和枝层出不穷。你探索的枝把你带到新的节点，而新的节点又产生更多的枝。这些枝中可能有些以前探索过(根据以前做的记号可以证明)。在多数场合，需要探索的枝的数量呈指数关系剧烈增长。你对迷宫的了解越多，你就越感觉到对175迷宫的无知。
假定探索一个枝需要1分钟，奥尔算法的执行过程大致如下:
在所有有限的迷宫中，发现新的枝的过程最终一定会结束。 在某个具体的探索阶段过后，大多数新的枝会向已经去过的节点连回来。最终，所有的枝都被走过了，终点一定己经发现。然而，在无限迷宫中，指数增长永不停息。即使终点相对较近，找到终点也会耗费大量的时间，以至于实际上难以找到。也许相距5个节点，需要花费将近一天的时间，但是实际上一旦发现了路线，走到终点只需要5分钟。搜索一个巧个节点远的终点需要若干年。如果终点的距离是45个节点，为了找到终点，宇宙的全部时间都不够用。
我们从计算机程序员的角度来看一下最长路径问题。你希望用计算机来判定，在一个比较大的迷宫中的两个点是否被某条路线连在一起。为此，你必须为计算机提供一幅迷宫“地图”。这幅地图以表格的形式列出了迷宫中的所有节点和所有的枝。节点标以数字或名字，通过明确一个枝连接哪些节点以及节点之间的距离可以确定枝。(无论采用什么单位，距离都用整数表示。)一个枝可能被表示为“节点16，节点49二72英尺”。距离是游客所走的实际长度，而非直线距离。充当入口和终点的节点同样如此表示。176最长路径问题还需要考虑一个因素:一个特定的距离。。最
长路径问题问的是，在入口和终点之间是否存在长度大于n的直接路径。如果你愿意，n可以取任意小的值，甚至是0。当n取0时，最长路径问题转化为:是否存在一条长度大于0的路径，这等价于是否存在一条连接入口和终点的无论怎样的路径。
既然存在性问题属于NP完全问题，比它更难的无限迷宫问题至少和NP完全问题一样难。如果判定通向G点的路径是否存在这个问题的难度己经达到了实际不可解的程度，那么具体指明这样一条路径的问题更是如此。
迷宫先知
NP完全问题有一个令人惊异的属性:其答案很容易验证。设想你遇到一个先知，无论你问什么问题，这个先知都能依靠神的启示立刻给出答案。那些相信先知的全知能力的人带着问题来问先知，这些问题如此之难，以至于他们解决不了，但是先知立即做出回答。
然而，当他试图向所有人证明自己的特异功能时，他遇到了麻烦。他的想法是，通过表明他给出的答案的正确性来证明自己确实是全知的。但有时这是不可能的。
人们问他的问题分两类。最常见的一类是其他人无法回答的难题:为什么存在邪恶?神存在吗?圆周率的十进制小数展开式中小数点后第10'00位数字是几?实际情况是，先知的回答从各个角度来说都是正确而精准的，但是他无法证明这些答案。怀疑者对他冷嘲热讽:对于这些问题先知可以胡乱给出任意的答案，反正别人无法揭穿他。即使相对而言比较现实的问题(例如圆周率的第10100位数字)也难以验证，其难度已超出了世界上最强大的计算机的处理能力。
为了证明他的特异功能，这个先知必须回答那些答案可以检验的问题。人们问他的问题中也包括这种，其中某些是怀疑者提出的，提问的目的就是拆穿他。基里巴斯的首都是哪儿?622521的平方根是多少?《小妇人》中姐妹们叫什么名字?这只密封的盒子里装的是什么?
先知正确地回答了所有这些问题，而且提问者知道先知的答案是正确的。提问者知道这一点，是因为提问者本来就知道答案。177问题就出在这儿。这些问题太简单了，因而不足以确切无疑地证明先知的神力。既然提问者早已通过普通的方法知道了答案，那么可以设想，先知同样可以利用普通的方法了解或发现。怀疑者会说，他的全知口J能是假冒的:他不过是一个计算天才，在琐细的事情方面非常渊博，至于最后一个问题，他采用了“测心术”—表演者在舞台上施展的不入流的骗术。
这两种结果都是先知的失败。如果一个问题是其他人无法回答的，怀疑者会指控他捏造;如果一个问题的答案是己知或者可知的，怀疑者会指控他假冒。为了证明自己的全知，先知需要第三类问题，其特点在于:问题很难回答，但是一旦说出答案，很容易验证。存在这样的问题吗?
无限迷宫问题就满足这个要求。让怀疑者在这个迷宫中选两个随机点，然后让先知在两点间确定一条路线。任何人都能轻而易举地验证答案正确与否，他们需要做的不过是沿着指定的路线走，验证一下自己是否到达正确的地点。
这个问题不会是另一个“简单”的问题吗?我们必须确保选 定的这两个点足够远，没有人知道连接这两个点的路线，甚至没有人可以用正常方法找到一条这样的路线。算法(包括奥尔算法)的相对低效性保证了这样一对点普遍存在。如果两个点相距20个节点，用普通方法找到一条路线需要若干个世纪。①另外，这个①“没有人知道连接这两个点的路线”这个要求是不必要的，出题者可以知道路线。出题者这样出题:自己在迷宫中随机地走过50个节点，记住自己走的路，定义他的起点为E点，终点为G点。仅把E和G告诉解题者，让解题者找到路线。从解题者的角度看，这道题的难度好比大海捞针:但是从出题者的角度看，就像回家一样简单。—译者汁问题不会是另一个“困难”的问题吗?不会，因为我们只需20分钟就可以检验先知的答案(假定每分钟走过一个枝)。迷宫的一个解比迷宫本身容易太多了。
就本质而言，第三类问题与复杂性理论中的“NP类”很接近。P和NP
一个一般性的问题不同于一个问题的若干例子。拼版游戏是一类一般性的问题;把1 500块碎片拼起来，复原成一幅荷兰风车的图案，这是拼版游戏的一个例子。
NP完全理论判断问题的难度不是以某些特定的例子为依据，而是以难度随问题的规模增长而增长的函数关系为依据。在拼版游戏中，问题的规模反映为碎片的数量。碎片越多，问题越;s难。问题的难度最好用解题所需的时间衡量。当然，所需时间依赖于你的工作效率，但是时间显然与为了完成工作你必须比照、处理的碎片数目有非常大的关系。
拼版游戏有一些非常困难的例子，例如有一种比较新颖的玩法，所有的碎片都是一种颜色。在这种情况下，你必须随机地比较碎片，判断它们是否吻合。在这个过程的早期，你需要把每一个碎片和许许多多的碎片比较，这个阶段令你疲于奔命。比较和匹配操作的总体步骤与碎片数量的平方成正比。因此，所需的时间可以表示为包含n2的多项式函数，其中n为碎片的数量。
比较而言，这个问题所需的时间还不算多。·在迷宫中，用奥尔算法找到终点所需的时间更接近于2"，其中n是起点和终点之间的节点数。当n较小时，矛和2”之间差别不算巨大;随着n的增加，多项式函数和指数函数之间出现一条巨大的鸿沟。你可以解决一个有5000个碎片的拼版问题，但是你无法解决一个需要5000次正确选择的迷宫问题，除非迷宫特别明显地简单。从复杂性理论的角度看，所谓“容易”的问题是那些可以在多项式时间内解决的一般性问题。这些问题属于P类(P代表多项式)。我们把P设想为某处的一个辽阔的国家，粗略地画在地图上，但是边界是清楚的。地图上的任何一点或者属于P,或者不属于P。当然，我们的地图不大可靠，有时候无法判断属于与否。拼版问题是一个属于P类的点，简单的算术问题也属于此类。
另一类问题称为“NP"，包括所有那些答案可以容易地检验的问题(可以在多项式时间内验证)。如果一个问题是简单的，那么答案也是容易检验的。如果别无检验的办法，你可以把问题重解一遍，比较一下两次的答案是否一样，这样就完成了检验。因此，所有简单问题(P类)属于答案容易检验的问题(NP). NP还包括许多P以外的问题，迷宫就是一个例子。这样看来，NP是一个更大的国家，而P是NP内部的一个省。如果画成地图，大致如下图。外面的矩形代表所有可能的问题。NP类并不包含所有的问题。有些极端困难的问题，甚至检验其答案都是很难的。矩形中NP的圆圈以外的部分代表这类问题。
我们在这个背景下讨论先知的问题。第一类问题是困难的，检验也是不容易的，它们相当于NP的圆圈以外的问题。第二类179问题对应于P类。第三类问题难以回答但容易检验，对应于在NP范围内但不属于P的问题。
"NP”这个术语(“非确定性多项式时间”)涉及一种被称为“非确定性计算机”的东西。特别地，这种理想化的计算机被称为“图灵机”，是计算机先驱艾伦·图灵(Alan Turing)构想出来的。非确定性计算机与字面意思不大一样。从字面看，它的意思似乎是计算机随机工作，或是遵循某种不大确切的“算法”(或者一台有自由意志的计算机!)。
我们可以这样设想一台非确定性计算机的操作:我们的计算机不止一台，我们有很多台计算机，计算机的数量有可能是无穷多。每一台计算机被分配了某个问题的一个可能解，负责检验这个解。
例如，我们的问题是在迷宫中找一条路线，全体计算机(在这个例子中是机器人)从入口处出发。每当这支机器人搜索队走到迷宫的一个岔路口时，他们分兵数路，每条路分配一支人马。搜索队在每个新的岔路口不停地分派人马，直到所有可能路线探索完毕。
至少有一个机器人实际上从入口走到了终点。现在我们集中考虑这个机器人。它用了多长时间?很可能没用多少时间。迷宫的解通常较短，迷宫的难度在于尝试所有错误的路径以及退回到出发点的过程。一台非确定性计算机用来“解”一个问题所需的iao时间就是用来检验一个猜出来的解的时间。
NP问题大致相当于科学探索所面对的问题。当科学家试图建立新的真理时，他的地位很像上文提到的先知。科学最关心的假说与NP问题的答案类似:这些假说可以非常容易地证实或反驳。
在NP问题和科学之间还有更惊人的联系—逻辑演绎本身就是一个NP问题。最难的问题在NP类中，哪个问题最难?1971年，斯蒂芬·库克证明， “可满足性”和NP中的任何一个问题相比至少同样难。他的证明显示，在NP中不存在更难的问题，因为所有NP问题都可以转化为可满足性问题。
随之而来的是理查德·卡普的发现(1972:许多不同种类的难题都属于可满足性问题。这些形态各异的问题来自图论、逻辑学、数学游戏、数论、密码学、计算机编程等领域，它们都和可满足性问题同样难。由最难的NP问题构成的类称为“NP完全”。用维恩图(Venn diagram)表示，NP完全在NP的圆圈内，但位于P外。
严格地说，NP完全是一个不稳定的疆域，也许并不真正存在。我们尚未证明NP完全问题无法在多项式时间内解决。我们的证据仅仅是经验性的:理论家和计算机程序员倾注多年的心血，试图在多项式时间内解决NP问题，但是毫无例外地失败了。在实际中，一旦证明一个问题属于NP完全，则可以认为有充分理由证明，这个问题不存在高效率的解决方法。
我们还是能勉强设想，存在一种尚未发现的超级算法，可以在多项式时间内解决所有的NP问题。如果确实有这种算法，那么P, NP和NP完全就全变成一回事儿了，我们可以把它们合在一起表示为一个圆圈。
如果存在一种高效率的解法—一个神奇的窍门，那么我们从逻辑前提中可以推出什么(像福尔摩斯那样)实际上就没有任何限制。反过来说，如果可满足性问题和NP完全问题没有高效率的解法，在现实中就一定存在大量的永远不会被发现的真理。18，我们强烈地感到，这样一种解法是不存在的。我们所有人都像华生医生那样，错过了大量己被我们看见的线索。
这意味着，对于哪些逻辑问题是可解决的，存在着一个关于其规模的相对严格的限制。在迷宫问题中，一旦迷宫规模超过一定限度，就变成实际不可解的了;同样的道理，一旦一个逻辑问题超过一定的复杂程度，也会变成实际不可解的。一个明显的推论是，我们关于实在世界的推理也是有限度的。
经验目录
悖论意义重大、影响深远，超过了表面看来的程度。如果某人相信一些自相矛盾的信念，那么这些信念中至少有一些是他没有理由相信的。因而，理解一组信念(至少)意味着有能力发现信念中的矛盾。所以说，发现悖论的问题—即可满足性问题—是知识的界标。在试图全面理解某事的含义的过程中，已经内在地包含可满足性的难度。
奠定牛顿的万有引力理论基础的东西没有一样是古希腊人不知道的。疾病的细菌理论原本有可能提前几个世纪提出和确立—如果某人发现了正确的联系。同理，此刻一定也有我们尚未完成的综合，虽然所需的材料已经摆在面前。非常可能的是，解决“如何预防癌症”、“第10颗行星在哪儿”这些问题所需的全部事实己然齐备，但是还没有人发现组织这些事实的正确秩序。不仅如此，也许我们正在错过关于这个世界的各种各样的逻辑结论。这些结论有可能隐藏在我们见到、听到的每件事里，但是其复杂性有一点点超出了我们的理解力。
爱因斯坦写道:“全部科学的宏大目标是，从最小数量的假说或公理出发推导出最大数量的经验事实。”①把人类的全部经验加在一起，包括从冰川纪至今所有人曾经看到、摸到、听到、尝到或闻到的一切。从理论上说，这些信息可以汇集为一个巨大的目录。这个目录是一个简单的列表，对经验不做任何解释。对梦境、幻象、胡思乱想和错觉详尽描述，与“真实”的经验并列。二者中哪个是真实经验(如果有的话)，留给目录的读者自己确定。①原文此处有笔误。译文已改。—译者注182这个目录必然已包含作为自然科学的基础的全部观察。对鸟、星星、蔽类植物、水晶和草履虫的全部观察都可以在目录中找到。这个目录还包含所有曾作过的科学实验的哪怕最微小的细节。目录中还包括，在1887年那个特殊的日子，迈克尔逊和莫雷对下午稍晚的阳光照耀在仪器的镜子上的印象。加牛顿曾见过的所有苹果的颜色、尺寸、形状、速度以及加速度等信息也搜集在目录中。
科学不是简单的经验目录。首先，任何人的大脑都无法容纳全部人类经验的整体。目录必须包括你经历过的一切，这就会占据迄今为止你的整个生命中的全部注意力!科学对人类经验(或经验的某些方面)进行压缩，达到一个可处理的形式。我们真正感兴趣的是理解目录所描述的这个世界。总的说来是这样，虽然 某些特殊场合并非如此。在科学哲学中有一个恼人的问题:这种过程可能进行到何种程度?
每一个经验对未知的世界的某些部分的真值做出了限制—和在逻辑谜题中一样。当然，未知事物间的关系可能非常微妙，每一个事物都必须用一系列的“如果”来限定。也许你的经验中的一个是:你听到你的朋友佛瑞德说，他上周二见到了尼斯湖怪兽。经验的实际输入也许是这样:
如果佛瑞德没犯错误，并且他没有撒谎，并且外部世界不是幻象，那么在星期二尼斯湖怪兽存在。这些“如果”从句是必不可少的辅助性假设，它们使证实复杂化。
把经验目录输入一台超级计算机，编好程序，令它进行推演。①指著名的迈克尔逊一莫雷实验，这个实验证实了爱因斯坦的光速不变理论。—译者注这个任务只需要逻辑，而逻辑正是计算机的强项。在这个任务完成以后，计算机甚至可以把推演结果按重要性排序，重要的标准是一个结果可以解释多少不同的经验。推演结果列表的第一条应当是人类可以知道的最重要的事实。
虽然以上介绍只是幻想，但是它确实展现了科学哲学中某些最核心的问题的基本框架。连锁推理是我们的科学的基础，它的一致性可以在多项式时间内识别和检验。这些简单的逻辑问题相183
当于单行线迷宫(在每个节点处只有一或两条枝的迷宫)，简单得不值一提，而与“正常”的迷宫(每个节点处有三条或更多的枝)不同。更复杂的推演包括含有三或四个未知量的前提，解这类问题需要指数时间(实际上是无法完成的)。也许有一大类可以解释我们的感觉经验的逻辑推演是我们永远无法发现的。
把我们的经验设想为迷宫，把关于经验的逻辑真理设想为遍布迷宫的路径。可满足性问题的NP完全性表明，我们永远无法穷尽所有的潜在路线。和宇宙一样大的计算机
计算机科学家拉里·J·斯托克迈耶(Larry J. Stockmeyer )和阿尔伯特·R·迈耶(Albert R. Meyer)设想了一台大小和宇宙一样的计算机，以此来形象地展示NP问题何等的难以处理。他们表明，有许多关于宇宙的问题，我们为了回答这些问题，会发现宇宙不够大。
假定我们试图把所有己接受的信念列出一个清单。就像笛卡尔一样，我们希望从一片一空白开始，非常小心地把信念填进去。在任何一个信念被填进去之前，首先再次检查己经被列进清单的
信念，以确保增加新的信念不产生矛盾。这个检验即可满足性问题。
也许你会认为，为此只需要把清单浏览一遍，确保准备加入的新信念不与任何一个以前列入的信念直接矛盾。然而，实际情况没有这么简单。
显然，新的信念有可能与旧的信念矛盾。如果新的信念是“所有乌鸦是黑色的”，而旧信念中有一条“所有乌鸦都不是黑色的”，在这里你就遇到了矛盾。‘最危险的是这种情况:三个或更多命题，各自独立地看都是可以成立的，但是合在一起构成矛盾。通常，“悖论”这个术语专门指这种情况。矛盾不是一目了然的。
假定新的信念是“所有草是绿色的”，清单中可能已经包含了两个语句:所有干草是黄色的。干草是草。
这两个语句加上新语句就产生矛盾。如果你仅仅一对一对地184检查—在三个语句中拿出两个来检查是否相互一致，你就会遗漏这个矛盾。为了排除这种情况，有必要在清单中一对一对地取出所有可能的命题组合，一一检验加入新命题后是否一致。这剧烈地增加了检查的工作量。但是这还不算完。也许还有更精致的悖论，只在四个、五个或更多命题合在一起考虑时才显现出来。
在100万个信念中加入一个信念，即使在原来的信念中任意取出999 999个信念与新信念合在一起都是一致的，整体上还是有可能出矛盾。
需要检查的事实太多了，显然必须借助于计算机。我们从1号信念开始(这个信念也许是“我思故我在”)。为了让计算机能够处理，这个信念表示为关于布尔未知量的一个逻辑命题，下一①这个例子不恰当。现代逻辑认为，“所有乌鸦是黑色的”和“所有乌鸦都不是黑色的”并不矛盾，两个语句可以同时为真。不过，这并不影响作者的分析。—译者注步，我们准备加入一个新的信念，2号信念。我们指示计算机对照1号信念进行检查，看看是否出现矛盾。此时，只需一次逻辑检验(比照2号信念和1号信念)。
现在清单中有两个信念，我们准备加入第三个。此时必须进行3次检验:与1号信念比照;与2号信念比照;与1号、2号合在一起比照。
第四个信念必须和7个命题集合进行比照:分别与1, 2, 3号比照;分别与1和2, 1和3, 2和3比照;与1, 2, 3合在一起比照。
事实上，一个新的信念必须与当前清单的所有可能子集合在一起检验。n件东西的子集数计算公式是一个指数函数:2"。这个公式把空集也计算在内，其实我们不必考虑空集。非空子集的数量是2"-l o
假定这些信念(或其中的某些信息)在逻辑上足够复杂，因而无法避免指数时间的算法。此时，需要进行比较的次数如下表:
即使这个清单的规模非常有限，比方说，只包含100个信念，185它的子集数也是一个天文数字。为了接受第101个信念，它必须与这个清单的1030个子集对比检验。
怎么会这样呢?你可以写下第101个信念，然后很快地确信其中并无悖论，这不是很明显的吗?
确实如此。你可以随机地从一部百科全书中抄下100个命题，确保每个命题都提到一些别的命题没说的东西。但是，我们现在研究的是更一般的情况，清单中的信念可能有许多是关于同一个未知量的，而且逻辑关系是复杂的。这些信念有可能互相纠葛，就像卡洛尔猪排问题的前提那样。这样我们就必须求助于一种算法—一种很慢的算法。
计算机向清单中加入信念的过程可以快到什么程度?
斯托克迈耶和迈耶的分析假定有一台“理想”计算机依靠指数时间算法确定某些数学命题的真假。就本质而言，这个分析对可满足性问题同样有效。斯托克迈耶和迈耶认为，任何一台计算机的计算能力最终取决于它所包含的元件的数量。在体积一定的条件下，元件越小，处理能力越强。
在最早的数字计算机中，逻辑门采用真空管，而连接采用导线。后来，真空管让位于晶体管。现在，强大的处理器封装在一个芯片内。大多数连接是通过印刷电路实现的，由很薄的金属膜
构成。
没有人确切地知道，处理器和逻辑门可以小到什么程度。在实验条件下，逻辑门可以采用只有几个原子厚的膜。在这个领域，许多前途远大的技术尚待开发。斯托克迈耶和迈耶在他们的思想实验中采用了非常乐观的假定。他们设想，计算机元件以某种方式可能达到质子的大小。现在我们认为，在可测量的范围内，质子和中子是最小的。在这台理想计算机中，无论元件多么小，其直径不能低于10-i s米(负的指数表示分数，这个数是1除以10'5.即一毫米的一万亿分之一)。
假定这些质子大小的元件可以像沙丁鱼罐头那样密密麻麻地塞满。在一个给定的体积内，可以填充多少个直径为10-15的理想球体，就可以填充同样数量的元件。如果计算机的大小与普通的个人电脑相仿(体积大约为十分之一立方米)，则大约包含1040个不同的元件。一个体积为一立方米的小型机将包含1045个元件。
在计算机技术中，另一个头等重要的因素是速度。一个元件;86需要花费的时间(例如一个逻辑门从一个状态转换到另一个状态的时间)构成瓶颈。任何形式的信息最快只能以光速传播。因此，
一个元件转换状态的时间不能超过光通过它所需的时间。否则就意味着，元件的一端以超过相对论所允许的速度“得知”另一端发生的情况。
光穿过一粒质子的直径所需的时间是3 x 10-24秒。在斯托克迈耶和迈耶的分析中，理想计算机的元件转换状态所需的时间采用这个值。
在现实中，计算机的速度还依赖于元件之间的连接方式以及为处理问题配置的可用资源的完善程度。大多数现在的计算机是串行的，也就是说，在一个时刻计算机只处理一件事。在任意一个瞬间，计算机处于算法中的一个点。就潜力而言，并行计算机的速度快得多。并行计算机有很多处理器，总任务分解为子任务，交给各个处理器。在大多数时间，并行计算机同时做许多事。
我们不妨奢侈一些，假定这台理想计算机按超精密的并行结构设计。每一个质子大小的元件是一个单独的处理器。各个处理器用某种类似于连接机器的方式连接起来，以确保相对直接的连接—即使处理器的个数是天文数字。
这台计算机向各个处理器分派子任务，每一个处理器分配到当前信念清单的一个不同的子集。每个处理器有能力瞬间完成新信念与当前的子集比较。在一次转换状态的时间内，处理器可以确定是否出现矛盾，然后转而处理下一个子集，这个时间是3 x 10-24秒(为了计算方便，把这个数近似为10-23。因此，每个处理器在一秒钟内可以进行1乎3次检验。在体积为一立方米的计算机内部，有1045个处理器。这台计算机每秒钟能处理1沪次检验。
这个速度很快。面对一个由225个信念构成的清单，在一秒钟之内计算机就完成了所有需要进行的比较。
但是此后，进程突然慢下来了。在增加第226个信念时，花费1秒钟:验证第227个信念花费2秒钟;检验第232个信念大约需要1分钟。计算机的速度一如既往，但是清单中每增加一个信念，检验的工作量增加一倍。验证第250个信念需要一个月以上。当清单扩展到300个信念时，需要的时间是—3800万年I187没关系，这是一个思想实验，我们拥有世界上的全部时间。据估计宇宙的年龄大约是100亿年，折合成秒在10'7和10'“之间。增加一或两个数量级，得到1019，这是对“永恒”的很恰当的估计。当宇宙的年龄达到现在的十倍时，实际上所有恒星都己熄灭，生命很可能己经消亡。①因此，1019秒基本上是可以有意义地谈论的时间的最大值。如果一台理想计算机有1045个处理器，从时间的起点开始工作，直到时间的终点，它可以进行的检验次数是巨大的10,”乘以1045，也就是说，它可以把这么多个子集与新信念比较。这个数等于1087。足以处理一个由289个信念构成的清单。
我们需要一个更强大的计算机。一旦元件的最小尺寸已经确定，为了获得更强大的运算能力，惟有增加体积。把这台计算机扩大到一个房间、一座房屋·····一个国家乃至于一个大陆那么大。但是无论如何扩大，终极限度是不能超过宇宙的尺寸。
迄今已知的最遥远的类星体据估计在120-140亿光年以外。如果宇宙是有限的，一个大胆的估计是，其“直径”为100()亿光年。1光年略低于10'3公里，即10'6米。因此，宇宙的直径大
约是1027米，其体积大约是108，立方米。
因此，一台大小同宇宙一样的计算机可以有1045乘以10,，个质子尺寸的兀件。这个数是10126.当然，这是白日做梦。关键在①这个预言有一定的问题。宇宙的演化是新生和消亡并存的。不如说“到了那个时候，宇宙可能已经演化成与现在完全不同的形式”更合适一些。当然，这里所说的合适与否只是就本语句的语意而言，并不影响作者的逻辑结论。于:无论科技发达到什么程度，任何计算机的元件个数不会超过10126。大脑或任何形式的物理实体都不能超过这个限度。这是一个我们必须接受的极限。如果这样一台计算机从时间的起点开始工作，直到时间的终点，可以执行10' 26乘以1002次基本运算，即10'680
10168这个数字是你做任何事的次数的绝对极限。最接近超级任务的情况不过如此。没有足够的时间和空间去实现或超过10'68次的任何事。不幸的是，运行 10'6“次逻辑检验并不能前进多远。当清单扩展到包含人约558个信念时，这台计算机就报废了。
我们最多只能知道558件事吗?不，当然不是的。我们根据简单推理、三段论和连锁推理可以知道很多事情。558这个粗略的限制针对的是在逻辑上足够复杂、需要用指数时间算法来检验的信念。如果558个信念像卡洛尔猪排问题那样“不规则”，那么这些信念组成的集合很可能超出了算机的处理能力—即使’88计算机和宇宙一样大。这就是新的悖论不断涌现的原因。
在逻辑上复杂的信念既不罕见，也非不自然。就连那些我们认为简单的信念(例如“所有乌鸦是黑色的”)实际上也配备了一系列的辅助性假设。可满足性的难度不仅限于逻辑谜题。
既然我们甚至不能辨别在我们的比较复杂的信念中是否包含矛盾，我们就不完全理解它们。我们当然无法从这些信念推出所有可以推出的结论。如果你把逻辑推演当做观察世界的一个视域，那么这个视域是有限的。连锁推理是简单推理构成的链条，它构成了这个视域中的基本视线。通过这种视线，我们在黑暗中看得很远。对于更复杂的推理，我们则非常近视，我们无法看清所有东西，我们甚至无法看清所有蕴含在我们的思想实验中的东西。有些东西就摆在哪儿，但是我们永远也看不到。
如果说我们过于低能，无法理解那些我们没看到的东西，这种评价是不公平的。假如我们遇到了全知者(在关于悖论的讨论中全知者经常冒出来)，全知者可以向我们指明我们没看到的东西，而我们有能力证明它们是真的。问题的答案是简单的—在你看到它以后。
这里的“我们”包括人类、计算机、宇宙生命以及任何物理机制。NP问题对于所有这些“我们”来说都是困难的。斯托克迈耶和迈耶的思想实验是奥尔贝斯悖论的一个信息时代的翻版。奥尔贝斯的出发点是我们能看见天空中的星星这个事实，而斯托克迈耶和迈耶的出发点是整个宇宙不是一台计算机这个事实。这里的结论是，这个宇宙中没有人无所不知。
第十章 意义：孪生兄弟
《伏尼契手稿》是一部非常古老的书，232页，配有插图，全书用密码写成，至今无人破译。作者是谁?主题是什么?阐释什么意义?这些都是未解之谜。甚至没有人知道，这些密码解码之后是什么语言。奇异的插图—裸体的妇人、怪异的发明、不存在的植物群落和动物群落—吸引密码破译者进行研究。彩色插图以中世纪医书的严谨风格绘制而成，而这些画表现的景象和意境却是在地球上和天空中前所未见的。一些平面图展示了古怪的、来世风格管道系统，图中美丽的少女坐在浴盆里嬉戏，浴盆连着有分叉、可转动的水管。这部手稿有一种非常奇异的风格，似乎是对另外一个宇宙的完美而精确的描述。这些画反映的是正文的主题吗?抑或只是一种伪装?没人知道。
一封写于1666年的信宣称，神圣罗马帝国皇帝、波希米亚192的鲁道夫二世(Rudolf 11 of Bohemia 1551一1612)以600达克特金币买下这部手稿。他可能是从约翰。迪伊博士(Dr. John Dee )手中买下的，迪伊是一个油嘴滑舌的占星术士兼数学家，游走于各国宫廷，追名逐利。鲁道夫认为，这份手稿的作者是英国僧侣兼哲学家罗杰·培根(Roger Bacon, 1220-1292).
