1701742018
1701742019
以2为公比的几何级数的和总是等于最后一项的2倍减1，再用这个差乘以数列的第一项。例如，20+21+22（=1+2+4）等于23减1（即8减1）。所需的麦粒的总数是264–1，等于18 446 744 073 709 551 615。
1701742020
1701742021
1吨麦子大约包含1亿粒麦粒，因此，所需的麦粒总量大约为2 000亿吨。现在（指本书成书时的1987年）全世界小麦年产量仅有4.6亿吨。国王欠下达希尔相当于4个世纪的小麦产量的债务（以现在的年产量计）。显然，当时的小麦产量还比现在低得多。（我们不知道这个故事发生在多久以前，因为国际象棋的发明时间不能确定。和篮球一样，国际象棋发生过几次变革，此外，我们不知道历史上是否确有达希尔其人。）
1701742022
1701742024
马尔萨斯灾难
1701742025
1701742026
托马斯·马尔萨斯（Thomas Malthus）认识到，世界人口以几何级数增长，而粮食产量仅以算术级数增长，在此基础上形成了他的著名理论。马尔萨斯有理由相信，每年新开垦的农田面积是固定的。因而，粮食供给的增长大致是这样的：100，102，104，106……另一方面，人口的增长率（主要取决于每年的新生婴儿数）随人口规模本身而增长。世界人口趋向于每隔若干年增加一倍，增长情况大致是：1，2，4，8，16，32……和达希尔的奖赏一样，这是一个几何级数。马尔萨斯警告说，人口增长必定超过食物供给，导致全球性的饥荒。
1701742027
1701742028
用“几何级数”这个术语来称呼这种级数并不恰当，把这种级数以几何指称既不形象又容易引起混淆。一个更恰当的术语是“指数级数”，这个名称源自“指数”这个术语。生长的有机体一般以指数增长为特征。无论是细菌的繁殖还是人类的繁衍，其共同特征是，新增个体数与总数成正比。复利存款也呈指数增长——这显然与这一事实有关：借方和贷方都是不断生长的有机体，他们创造了以指数状态增长的经济，而且，他们进行交易时依据的货币处于呈指数增长的通货膨胀中。
1701742029
1701742030
指数增长可以用简单的数学函数描述。所谓函数是从一个数转换为另一个数的过程。你可以把函数理解为袖珍计算器上的一个特定的键。你先在计算器上输入一个数，然后摁这个键，得到一个新的数。例如，开平方函数（许多计算器上都有开平方键）会产生一个数，此数乘以自身后得到最初输入的那个数。如果先输入36，再摁开平方键，得到6。
1701742031
1701742032
函数不仅限于可以在计算器上算出。任何一个从某个数产生新数的清楚而确定的过程都是“函数”。我们可以定义一个函数：67乘以n的积加上381（对于任意数，n），这就是一个有意义的函数。函数通常用方程的形式表示，例如：
1701742033
1701742034
f（n）=67n+381
1701742035
1701742036
“f（n）”读作“n的函数”。
1701742037
1701742038
我们很自然地想知道，哪种动物最大、什么动物的运动速度最快。同样，数学家也想知道，哪一种函数最大，或者增长得最迅速。有些函数胜过其他函数。如果在n足够大时，一个函数的值总是大于另一个函数，那么我们说前者比后者大（或者说增长更快）。例如，函数A是A（n）=1 000 000 000 000 000，而函数B是B（n）=n，则在很大一段区间里b较小。但是当n取大于1 000 000 000 000 000的任意数时，B（n）都大于A（n）。因此，B（n）的增长比A（n）快。
1701742039
1701742040
以上这些函数都不算大。任何一个常函数，即f（n）等于一个固定值的情况，最终一定会被一个与n成正比的函数超过。同样明显的是，这两种函数都会被与n2成正比的函数超过。与n3成正比的函数最终会增长得更快。类似地，对于与n4、n5、n6等成正比的函数，也是如此。
1701742041
1701742042
多项式是一个表达式，由一个变量的各次幂组成，例如n3+8n2–17n+3。一个多项式表示了一个函数。粗略地说，一个多项式函数的相对增长速度取决于它的最高次幂。函数n3+8n2–17n+3的增长速度远远超过任何最高次幂为2的函数。同理，它将被一个最高次幂为4（或更高）的函数超过。
1701742043
1701742044
许多函数的增长还要更快。马尔萨斯的悲观论点立足于一个事实：指数函数的增长超过任何多项式函数的增长。在一个指数函数中，某一个特定的常数以n为指数（而非n以某个常数为指数）。f（n）=3n是一个指数函数，它表示3自乘n次。当n为2时，3n即32，等于9。当n为1时，结果即等于底数（这个例子中是3）；当n为0时，无论底数是多少，结果都定义为1。于是，对应0，1，2，3，4……的函数值分别为1，3，9，27，81……每一项的值等于前一项的3倍。底数越大，函数值的增长越快。对于10n，每一项是前一项的10倍；而对于1 000n，每一项是前一项的1 000倍。
1701742045
1701742046
在复杂性理论中，表示一个问题的困难程度的最常用的标准是解决此问题所需的时间。不用说，每个人的工作效率是不一样的，计算机也各不相同。同样重要的是，针对同一个问题，算法可能不止一种，而某些算法比其他的更快。解决各种类型的问题所需的时间差异如此之大，这使得计算机与计算机之间（以及人与人之间）的计算速度的差别已经不重要了。
1701742047
1701742048
需要强调的是，某些问题可以用“多项式时间”解决，而另一些问题需要“指数时间”。这意味着，解决一个问题所需的时间可以表达为关于问题的规模（或复杂度）的一个多项式函数（或指数函数）。如果一个问题需要指数时间，则通常会令人绝望。无限机器也许只是胡思乱想，但是指数时间问题却是真实而普遍存在的。解决这类问题需要数量接近于无穷多的步骤——即使问题出现在有限的宇宙中。
1701742049
1701742050
下一章将讨论多项式时间问题与指数时间问题的差别以及这个问题与悖论的关系。现在，我们来研究两个质疑时空无限性的悖论。
1701742051
1701742053
奥尔贝斯悖论
1701742054
1701742055
1826年，德国天文学家海因里希·威廉·奥尔贝斯（Heinrich Wilhelm Olbers）意识到宇宙中有些东西似乎不对劲。天文学作为科学的一个分支，不能回避无限的问题。物理宇宙要么是无限的，要么是有限的。但是对于大多数人来说，这两种可能性都不容易被接受。
1701742056
1701742057
布莱士·帕斯卡（Biaise Pascal）写道：“每当设想我的生命被封闭在永恒的时间中的一个狭小的范围内，我能看到且感知的一小部分空间淹没于一个无限广袤的空间中，我对这个无限的空间一无所知，这个无限空间也不能了解我。一想到这些，我就对自己身处于此地而非别处感到恐惧和震惊。”另一方面，一个有限的宇宙也许令人更加难以接受。人类难以设想空间怎么会有尽头。
1701742058
1701742059
这种不安并非新问题。希腊哲学家卢克莱修（Lucretius）认为，他的论证足以证明空间是无限的：假定空间是有限的，那么空间则有一个边界。如果让某个人达到这个终极的边界，把一支标枪掷过边界，那么这支标枪要么穿过边界，要么被什么东西挡住——某个本身必定在边界外的东西挡住了它。无论是哪一种情况，都说明在边界外存在某种东西。以上操作可以不断重复，推动这个所谓的边界无限倒退。
1701742060
1701742061
在奥尔贝斯的时代，大多数天文学家认为空间的无限性是理所当然的。奥尔贝斯对无限时空的反对被当作痴人说梦，他也因此而闻名。假定宇宙是无限的，而星体（还有星系，虽然奥尔贝斯那个时代的人还不知道星系）在各个方向上从中心向外无限延伸出去。在这种情况下，从地球发出的一条直线（无论其方向如何）必将与一颗星体相遇。
1701742062
1701742063
当然，这条直线也许在延伸数十亿光年之后才与某星体相遇。关键在于，在一个散布着星体的宇宙中，这条直线最终必定遇到一个星体。这就好比，如果我们在轮盘赌上玩足够长的时间，那么所有号码最终肯定都会出现，不会有例外。
1701742064
1701742065
太阳是一颗恒星，在天空中，看起来有宽度的恒星仅此一颗。如果太阳与我们的距离增加到现在的10倍，那么它的外观表面积将只有现在的百分之一，亮度同样下降到之前的百分之一（根据很久以前就已确立的亮度递减公式）。如果太阳距离我们比现在远100万倍，它将变暗1万亿倍，它在天空中的大小将是现在的一万亿分之一。需要注意的是，在天空中，单位面积上的亮度保持不变，与距离无关。无论太阳距离地球多远，其单位表面积上的亮度都是固定的。奥尔贝斯意识到，这个简单的事实蕴含着一个悖论。
1701742066
1701742067
在夜空中，其他星体只呈现为针孔大小，但是这些针孔（平均而言）与太阳表面一样亮。光沿着直线传播，如果从地球出发的一条直线与某颗星体相遇，我们可以见到这颗星体发出的光。如果从地球出发的每一条直线都与某颗星体相遇，那么整个天空应当充满相互交叠的星体光盘，每个光盘都与太阳的光盘一样明亮，所有光盘交叠在一起，遍布整个苍穹。这幅图景就好像太阳是一个空心的球体，而我们位于球体的中心。阴影之类的东西不会出现，也不会有所谓的夜晚——夜晚其实就是阴影。
[
上一页 ]
[ :1.701742018e+09 ]
[
下一页 ]