1701742443
1701742444
推理的迷宫：悖论、谜题及知识的脆弱性 [:1701739735]
1701742445
和宇宙一样大的计算机
1701742446
1701742447
计算机科学家拉里·J·斯托克迈耶（Larry J. Stockmeyer）和阿尔伯特·r·迈耶（Albert R. Meyer）设想了一台大小和宇宙一样的计算机，以此来形象地展示处理NP问题的极高难度。他们表明，我们在想回答许多关于宇宙的问题时，会发现宇宙并不够大。
1701742448
1701742449
假定我们试图把所有已接受的观念列成一个清单。就像笛卡儿一样，我们希望从一片空白开始，并且非常小心地把观念填进去。在任何一个观念被填进去之前，首先再次检查已经被列进清单的观念，以确保增加的新观念与已有的观念不产生矛盾。这个检验即为可满足性问题。
1701742450
1701742451
也许你会认为，为此只需要把清单浏览一遍，确保准备加入的新观念不与任何一个以前列入的观念直接矛盾。然而，实际情况没有这么简单。
1701742452
1701742453
显然，新的观念有可能与旧的观念矛盾。如果新的观念是“所有乌鸦都是黑色的”，而旧观念中有一条“所有乌鸦都不是黑色的”，在这里你就遇到了矛盾。[6]最危险的是这种情况：三个或更多命题，各自独立地看都是可以成立的，但是合在一起构成矛盾。通常，“悖论”这个术语专门指这种情况，矛盾不是一目了然的。
1701742454
1701742455
假定新的观念是“所有草都是绿色的”，清单中可能已经包含了两个语句：
1701742456
1701742457
所有干草都是黄色的。
1701742458
1701742459
干草是草。
1701742460
1701742461
这两个语句若加上新语句就产生了矛盾。如果你仅仅一对一对地检查——在三个语句中拿出两个来检查是否相互一致，你就会遗漏这个矛盾。为了排除这种情况，有必要在清单中一对一对地取出所有可能的命题组合，一一检验它们加入新命题后是否一致。这极大地增加了检查的工作量。但是这还不算完。也许还有更精致的悖论，只在四个、五个或更多命题合在一起考虑时才显现出来。在100万个观念中加入一个观念，即使在原来的观念中任意取出999 999个观念与新观念合在一起都是一致的，整体上还是有可能出现矛盾。
1701742462
1701742463
需要检查的事实太多了，显然必须借助于计算机。我们从l号观念开始（这个观念也许是“我思故我在”）。为了让计算机能够处理，这个观念被表示为关于布尔未知量的一个逻辑命题，下一步，我们准备加入一个新的观念，2号观念。我们指示计算机对照1号观念进行检查，看看是否出现矛盾。此时，只需一次逻辑检验（比照2号观念和1号观念）。
1701742464
1701742465
现在，清单中有两个观念，我们准备加入第三个。此时必须进行三次检验：与1号观念比照；与2号观念比照；与1号、2号合在一起比照。
1701742466
1701742467
第四个观念必须和7个命题集合进行比照：分别与1、2、3号比照；分别与1和2、1和3、2和3比照；与l、2、3合在一起比照。
1701742468
1701742469
事实上，一个新的观念必须与当前清单上的所有可能子集合在一起检验。n件东西的子集数计算公式是一个指数函数：2n。这个公式把空集也计算在内，其实我们不必考虑空集。非空子集的数量是2n–1。
1701742470
1701742471
假定这些观念（或其中的某些信息）在逻辑上足够复杂，因而无法避免指数时间的算法。此时，需要进行比较的次数如下表：
1701742472
1701742473
1701742474
1701742475
1701742476
即使这个清单的规模非常有限，比方说，只包含100个观念，它的子集数也是一个天文数字。为了接受第101个观念，它必须与这个清单包含的1030个子集对比检验。
1701742477
1701742478
怎么会这样呢？你可以写下第101个观念，然后很快地确信其中并无悖论，这不是很明显的吗？
1701742479
1701742480
确实如此。你可以随机从一部百科全书中抄下100个命题，确保每个命题都提到一些别的命题没说的东西。但是，我们现在研究的是更一般的情况，清单中的观念可能有许多是关于同一个未知量的，而且逻辑关系是复杂的。这些观念有可能互相纠葛，就像卡洛尔猪排问题的前提那样。这样我们就必须求助于一种算法——一种很慢的算法。
1701742481
1701742482
计算机向清单中加入观念的过程可以快到什么程度？
1701742483
1701742484
斯托克迈耶和迈耶在分析时，假定有一台“理想”计算机依靠指数时间算法确定某些数学命题的真假。就本质而言，这个分析对可满足性问题同样有效。斯托克迈耶和迈耶认为，任何一台计算机的计算能力最终取决于它所包含的元件的数量。在计算机体积一定的条件下，元件越小，处理能力越强。
1701742485
1701742486
在最早的数字计算机中，逻辑门采用真空管，而连接采用导线。后来，真空管让位于晶体管。现在，强大的处理器封装在一个芯片内。大多数连接是通过印制电路实现的，它们由很薄的金属膜构成。
1701742487
1701742488
没有人确切地知道，处理器和逻辑门可以小到什么程度。在实验条件下，逻辑门可以采用只有几个原子厚度那么厚的膜。在这个领域，许多前途远大的技术尚待开发。斯托克迈耶和迈耶在他们的思想实验中采用了非常乐观的假定。他们设想，计算机元件以某种方式可能达到质子的大小。现在我们认为，在可测量的范围内，质子和中子是最小的。在这台理想计算机中，无论元件多么小，其直径不能小于10–15米（负的指数表示分数，这个数是1除以1015，即一毫米的一万亿分之一）。
1701742489
1701742490
假定这些质子大小的元件可以像沙丁鱼罐头那样密密麻麻地塞满在一个体积给定的物体内，它们可以填充多少个直径为10–15米的理想球体，就可以填充同样数量的元件。如果计算机的大小与普通的个人电脑相仿（体积大约为1/10立方米），则大约包含1044个不同的元件。一个体积为一立方米的小型机将包含1045个元件。
1701742491
1701742492
在计算机技术中，另一个头等重要的因素是速度。一个元件需要花费的时间（例如一个逻辑门从一个状态转换到另一个状态的时间）构成瓶颈，任何形式的信息最快只能以光速传播。因此，一个元件转换状态的时间不能超过光通过它所需的时间，否则就意味着，元件的一端以超过相对论所允许的速度“得知”另一端发生的情况。