按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
⑾值摹＃ㄔ�1933 年的一天，古腾伯格和爱因斯坦两人正专心地讨论地震学的问题，以至于他们谁也没有注意到由于长堤（LongBeach）地震引起的加州理工学院校园的震颤。）同样，不断飞抵地球的极小的陨石主要是由专家们在统计测量中摘记下来的，而在6500万年以前发生的，促使白垩纪绝灭的巨大碰撞则被认为是生物圈历史中的重大的单个事件。
因为幂定律已被证明是在自组织临界态情况下生效，所以本已很流行的词组“自组织”就具有了更大的通用性，它常常与“自然生成”（emergent）一词并列使用。包括圣菲研究所许多成员在内的科学家们正力图弄清楚，在没有引入外部作用的情况下，结构是怎样产生的。在种种令人惊讶的过程中，具有简单规则的系统形成了显然很复杂的结构。这些系统被说成是自组织的，它们的性质也被说成是自然生成的。最完美的例子是宇宙自身，它在简单规则与偶然性作用的基础上，产生出了十足的复杂性。
在很多情况下，由于现代计算机的使用，关于自生结构的研究已经容易多了。通过计算机的方式比在纸上列方程往往更易于跟踪新特征的自生。由于自生过程需花费很长的时间，因此计算机的作用往往特别引人注目，因为计算机能够通过使用一个很大的因子而有效地加速有关过程。可是计算机计算仍然需要许多步骤，这将引起一个全新的问题。深度与隐蔽性
到目前为止，在对复杂性所进行的讨论中，我们考虑了关于系统或其规律性的压缩描述（或用于产生编码描述的短小计算机程序），并将各种各样的复杂性与那些描述或程序的长度联系起来。可是，我们很少关注为实规压缩或识别规律所需要的时间、人力或技巧。既然一个理论科学家的工作严格地包括识别规律，并将有关它们的描述压缩成理论，所以我们对上述因素的忽视也就等于是藐视了理论家工作的价值，这显然是一种荒诞的犯罪行为，必须采取措施来矫正这种错误。
我们已经了解到，要完全捕捉住关于复杂性的直觉观念，需要有好几种不同的概念。下面我们就要给有效复杂性的定义补充其他一些量的定义，这些量将描述，计算机要花多长时间才能从一个短小的程序到给出对一个系统的描述，反之亦然。（在一定程度上，这些量必然与一个问题的计算复杂性相似，后者已在前面被我们定义成计算机产生一个解答所用的最短时间。）
许多人都研究过这样的附加概念，但唯有查尔斯·贝纳特（CharlesBennett）是以一种特别优美的方式来处理它们的。查尔斯·贝纳特是IBM公司一位卓越的思想家，领导给他的任务就是创立新的观点与概念，将它们发表，并到各处去作关于它们的演讲。我乐意拿他的旅行同12 世纪时期一些抒情诗人在现在的法国南部，从一个庭院到另一个庭院的游历作对比。那些诗人们吟诵的是爱情诗，而贝纳特“吟诵”的是复杂性与熵，量子计算机（quantum puters）与量子编码（quantum encipherment）。我有幸与他一起在圣菲共过事，并在帕沙第纳一起工作过一学期，当时他在我们加州理工学院的研究小组中作访问学者。
贝纳特所定义的两个特别有意思的量“深度”（deepth）与“隐蔽性“（crypticity）均与计算复杂性有关，并且它们彼此之间也是相关的。对这两个量的研究进一步说明，一个系统虽然很明显十分复杂，但由于其描述可以通过一个简短的程序得出，因而具有很低的算法信息量与有效复杂性。关键在于下述问题的答案：（1）从一个简短的程序或一个高度压缩的图式发展到一个对系统本身或其规律的成熟的描述，其艰难程度如何？（2）从系统着手，将对它的描述（或对其规律的描述）压缩成一个程序或图式，又有多艰难？
粗略地说，深度是第一种困难的量度，而隐蔽性是第二种困难的量度。显然，与理论家的工作价值有关的是隐蔽性（虽然关于理论创立过程的更细致的描述，还应该对人的灵巧与纯粹的艰难作出区别）。一个假想的例子
为了举例说明许多的简单性怎样与巨大的深度产生联系，让我们回到哥德巴赫关于每个大于2 的偶数都可表示为两个素数之和的猜想上来。如前面所提到的，这一猜想从来未被证明或证伪过，但是在某个相当大的范围内的所有偶数都被核实了，这个范围是根据计算机的容量与研究者的耐心而设定的。
以前我们允许自己相信哥德巴赫猜想（在数论公理的基础上）是不可判定的。这次让我们假定它是错误的。在这种情况下，某个很大的数g 是大于2 但不能表示为两个素数之和的最小的偶数。这个假想的g 有一个相当简单的描述，也就是我们刚刚给出来的。同样，也会有很简短的程序来求它。例如，你只需有顺序地寻找越来越大的素数，并将所找到的最大素数加上3，然后检验小于或等于所得数的全部偶数，看它们是否符合哥德巴赫猜想。用这一方法，违背哥德巴赫猜想的最小偶数g 将最终被发现。如果哥德巴赫猜想真是错的，那么用于寻找g 的任何一个简短程序，其运行时间实际上可能很长。因而在这种假想情况下，数g 有着相当低的算法信息量与有效复杂性，但有很大的深度。再论深度贝纳特对深度的定义涉及到计算机，与我们讨论算法信息量时所引入的那种计算机相同：一个理想的多功能的计算机，它的存贮容量在任何时候都可以按需要扩充（或一开始就具有无限大的容量）。他从一个用来描述被研究系统的信息比特串入手。他不仅考虑致使计算机打印出那个比特串然后停机的最短程序，而且考虑具有相同作用的所有简短程序。对每个这样的程序来说，他关心的是从输入程序到得到信息串需要多长的计算时间。最后，他使用一个偏重于较短程序的求平均方法，将时间对程序的长度求平均。
贝纳特还用一种稍微不同的形式重新定义了深度这个概念，他使用了格里高里·蔡廷的隐喻。假定著名的猴子打出的不是散文，而是计算机程序。让我们把注意力只集中于那些使计算机打印出我们所关注的特定信息串然后停机的少数程序。在所有这些程序中，所需要的计算机时间小于某个特定值T 的概率是多大呢？设那个概率为P，那么深度d 将是T 的某种平均值，一个取决于P—T 曲线的平均值。图8…2 中的曲线给出了概率P 随所允许的最大计算机时间T 变化的略图。当T 很小的时候，猴子们要敲出一个在如此短的时间内算出所需结果的程序，其可能性极小，因而P 趋于0。当T 非常大时，概率必然接近1。大致说来，深度d 等于P—T 曲线上概率上升部分的时间。它告诉我们，为了挑选出能使计算机打印出信息串然后停机的最佳部分程序，可允许的最大运行时间需要多大。因此，深度是衡量一个信息串的产生所需时间的粗略尺度。图8…2 深度与时间的关系
若自然界的一个系统具有很大的深度，那就表明，它是经过长时期进化形成的，或者说它滋生于由长时间进化而形成的某种东西。对自然或历史文物保护感兴趣的人，正试图保护自然群体或人类文化中所显示出的深度和有效复杂性。
但是，如贝纳特所证明的那样，在漫长的进化过程中，深度有被传递给此过程中产生的副产品的倾向。我们发现，深度不仅存在于包括人类在内的当今的生命形式中，存在于人类手工制作的不朽的艺术品中，存在于恐龙或冰河时代哺乳动物的化石中，而且还存在于沙滩上开启啤酒罐的拉扣或描绘在峡谷壁上的粗糙的雕刻中。保护主义者不必保护所有具有深度的事物。深度与AIC
虽然深度是运行时间对程序长度的平均，它偏重于突出较短的程序，但我们往往可以通过最短程序的运行时间，来很好地理解深度的概念。比如，假定信息串是完全规则的，其AIC 接近于零。那么，最短程序的运行时间不会很长——计算机不必为执行像“打印12 兆个0”这样的程序而进行长时间的“思考”（当然，如果打印机速度很慢的话，打印出这些0 倒是可能要花费一些时间）。所以，当AIC 非常低时，深度也就很小。
对于具有给定长度的信息串来说，具有最大AIC 的随机串的情况怎么样呢？在计算机方面，从最短的程序——“打印数串？？ ”——到实际打印出该数串，同样不需要“思考”。所以，与AIC 很低时的情况一样，当AIC 最大时，深度也很小。这个情形与图5…1 所示的最大有效复杂性随AIC变化的方式有些相似。这里，我们可以大致看出最大深度随AIC 变化的规律。在AIC 最小与最大这样两个极限值附近，深度很小，而在有序与无序之间的中间区域，各处的深度都可以很大。当然，在那个中间区域，深度并不是非大不可。图8…3 可能的最大深度随AIC 的略图
注意，这个关系图与图5…1 的那个图的形状不同。尽管两者都只是略图，但它们显示出，即使AIC 的值很接近完全有序或完全无序，深度也可以很大，但其有效复杂性却依然很小。隐蔽性与理论化
隐蔽性涉及的是与深度定义相反的过程。信息串的隐蔽性，是指一个标准计算机从该信息串开始，到找出能致使计算机打印出该串然后停机的一个较短程序，所需要的最少时间。假定该信息串是由一个理论家所研究的数据流编码而得，那么，它的隐蔽性是衡量该理论家工作艰难的粗略性尺度，这与定义中计算机的艰难度没有太大的差别。理论家识辨出尽可能多的规律性，也就是将数据流各部分联系起来的交互信息，然后建构尽可能简单、自洽的假说，用来解释观察到的规律性。
规律是数据流的可压缩的部分。它们一部分来源于自然界