1701742002
发出一个声音需要消耗多少能量取决于频率（音调）和振幅（音量）。为了避免能量需求达到无穷大，随着频率的增加，振幅必须减小。在这1分钟的最后一瞬，机械嘴的音量将下降到0。你无法听到最后的哨音——即使你的耳朵有能力捕捉音调无限高的声音。
1701742003
1701742004
请注意：如果试图以更具物理上的可实现性的方式设计三种无限机器中的任何一种，都会导致一个结论——最后的结果是不可见的（或不可闻的）。许多哲学家认为，在涉及无限机器、超级任务以及只有通过超级任务才能了解的事实时，总是有些可疑的东西。
1701742005
1701742007
几何级数
1701742008
1701742009
无限——完全就其本意来说是不可理解的，但是趋近于无限的情况随处可见。有一个印度传说，什里姆国王（King Shirim）曾经落入西萨·本·达希尔（Sissa Ben Dahir）的圈套。达希尔是国王的大臣，发明了国际象棋。国王钟爱这一游戏，决定重赏发明者。因为国际象棋棋盘有64个格子，国王决定为每个格子赏赐达希尔一块金子。达希尔礼貌地谢绝了这份赏赐，恳请国王以另一种方式奖励他。他请求国王在棋盘的第一个方格上放一粒麦子，在第二个方格上放两粒麦子，在第三个方格上放四粒麦子，依此类推，每个方格上的麦粒数是上一个方格的2倍，直到棋盘的每一个方格上都分配了麦粒。
1701742010
1701742011
因感动于达希尔的谦虚，国王收回成命，转而下令拿来一袋麦子，按照达希尔的要求仔细地数出麦粒来。当国王的仆人们对付第12个方格时，他们就已经无法把所有的麦粒放进方格里了，只好把大臣应得的麦子在棋盘旁堆成一堆。国王吃惊地发现，第20个方格还没被满足，一袋麦子就耗尽了。他下令取来更多的麦子……最后所有的麦子都用完了。他的王国的所有麦子加在一起也无法满足达希尔的要求，不仅如此，全印度乃至全世界的麦子加在一起也不够用。
1701742012
1701742013
这个故事的寓意在于，永远不要低估几何级数。当然，从民间故事里挖掘出数学含义有点奇怪。根据国王最初的想法，赏给达希尔的金子直接和棋盘包含的方格数成正比。如果达希尔设计的棋盘不是64个方格，而是81个、49个或者其他数字，从国王的角度说都没有太大的差别。区区几块金子与国王的财富相比，算得了什么呢？
1701742014
1701742015
然而，几何级数的增长超出世间的任何限制——对于财富或任何其他东西都是如此。达希尔要求以麦粒为单位来赏赐，麦粒的价值与金块相比微不足道，但是这个事实对最终结果几乎没有影响。
1701742016
1701742017
我们看一下，多少粒麦子才能满足达希尔的要求。这个总数是1+2+4+8+…，换一种写法，即20+21+22+23+…262+263。（这个级数的最后一位是263，不是264，因为第一个方格中的麦粒数是20，即1。）
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
[
上一页 ]
[ :1.701742002e+09 ]
[
下一页 ]