夸克与美洲豹 作者:[美]盖尔曼-第7章
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
豢裳顾醯某ば畔⒋鼙谎顾酰蚴挂桓鑫颐侨衔亲疃痰男畔⒋鼙唤徊窖顾酢Ｒ虼耍话憷此担颐遣荒苋范ㄋ惴ㄐ畔⒘康闹担恢荒芨鲆桓鏊荒艹龅纳舷蕖＜热恢荒苋范ㄋ诘陀谡庖簧舷拗档姆段冢蚨鳤IC 是不可计算的。不可计算性这一性质给我们带来种种不便，但使我们不能用算法信息量来定义复杂性的，还有另一个不同的原因。尽管通过AIC 可以引入一些有用的概念，如粗粒化、信息串的可压缩性，以及由观察系统所得出的描述长度等等，但它有一个实实在在的缺陷：它的另一个名字算法随机性就暴露了这一点。随机串的算法信息量最大。它（AIC）是衡量随机性的尺度，但随机性无论是在普通会话中，还是在大多数科学场合中都不是“复杂”的意思。因而AIC 不是真实的或有效的复杂性。但是，在讨论随机性的时候需多加小心，因为这个词的意思在不同的场合并不总是一样的。我第一次意识到这种暗藏的危险，是在很久以前与兰德（RAND）公司的接触中。第四章 随机性
50 年代我刚到加州理工学院工作的时候，我需要找份顾问工作来维持家庭的生计。加州理工学院的教授们每周可以出去做一次顾问工作，我跟同事们打听可去的地方。有一两个人建议我到兰德公司去，该公司位于著名的码头和玛斯卡滩附近的圣莫尼卡（Santa Monica）。
第二次世界大战之后不久，作为美国空军RAND 计划〔RAND 为研究与发展（researchanddevelopment）的简称〕，兰德公司成立了。它的使命就是诸如使军事策略与分派给军队的任务协调一致，给美国空军提供建议，并设计合理的方法。不久之后，公司的作用就扩大为包括在一系列问题上给政府提供建议，这些问题很多都与防御策略有关。兰德计划依然很重要，但是它只给公司提供部分经费，这样，公司成了一个不盈利的企业，于是它扩充为民间提供服务。兰德雇用各种领域的专家，包括政治学、经济学、物理学、数学及军事作战研究方面的专家。
物理所所雇用的成员大部分都是理论物理学家，我也加入了他们的行列。我开始作一些非机密研究，并为此挣得一份薪水。我们从加州理工学院来的3 个人组成了一个车辆合用队，每逢星期三到兰德去工作。“随机”的几个含义
对兰德公司所作的最初几次访问中，我记得最清楚的是，他们递给我一小堆新近提出来的报告，好让我熟悉正在进行的一些工作。其中有一份报告的题目是“兰德随机数表”（RAND Tableof Random Numbers），尽管读起来不那么精彩，但它毫无疑问很有用（不过我被告知，一些图书管理员根据“及100，000 个正常的偏差”这一小标题，将其归入变态心理学一类）。
关于这个报告，我觉得有趣的是里面飘出一小张纸，掉落到了地上。我拾起来一看，发现是张勘误表。兰德公司的数学家们在修正一些随机的数字！他们发现了随机数中的随机错误吗？在很长一段时间里，我认为这是件滑稽的事情，但是后来再思索这件事时，它使我注意到这样一个重要的事实：即便是对数学家和科学家来说，“随机”一词也有着几种不同的意思。
我们前面一直在使用的“随机性”一词，比如用于一个有一千个比特的数串，它的意思是该比特串是不可压缩的。换句话说，它非常地不规则，以至于无法用更短的形式来表示它。但是我们也可以认为，该数串是由“随机过程”所产生的，也就是说，是由抛掷硬币这样的偶然过程所产生的，这里正面用1 表示，反面用0 表示。这两个意思并不完全一样。一千次抛币的一个结果可能是一千个正面，用二进制数表示即为一千个1 组成的比特串。当然，这样一个一千次全是正面的结果不太可能存在。事实上，这种情况出现的概率是1n，其中n 是一个有300 来位数字的巨大的数。因为大多数长的比特串是不可压缩的（随机的）或几乎不可压缩的，所以许多组一千次抛币将得出随机的比特串，但不是所有的各组实验都产生随机比特串。一个避免混淆的办法或许是，用“stochastic”（随机），而不是“random”来表示随机过程，而将“random”主要用于不可压缩的数串。但是兰德公司随机数表中的随机是什么意思呢？这样一个表如何能配备一个勘误表呢？最重要的是，这个随机数表有什么用呢？
兰德公司物理部在1956 年和1957 年所开展的工作之一是一项非机密计划，该计划将应用于天体物理，它需要用相当基本的物理学进行计算。我承担了这一任务，另一个顾问，我的老朋友克斯·布吕克勒（KeithBrueckner）给我提供了一些帮助。部分计算涉及到几个非常困难的近似求和，兰德公司里一个很有趣的物理学家杰斯·马库姆（Jess Marcum）提出，通过一个称为蒙特卡罗的方法，利用随机数表来求和。随机数和蒙特卡罗方法
这个方法很适合于杰斯，因为他不仅是个物理学家，还是个赌徒。早些年，他在玩21 点牌游戏时赢了很多钱。他使用“学者方法”，在大部分情形下，当机会对他不利的时候，他就下小的赌注；而当机会对他有利的时候，例如，所有的十分牌（都是10 和有花的牌）都在牌桌的某一部分，他就赌大的。这个方法仅当使用一副牌的时候管用。不久后，所有的赌场都改变了赌博规则（可以说是对“学者们”适应的结果），而开始同时使用好几副牌。杰斯于是转向其他方面的赌博。
有一次，他曾经向兰德公司请了好几个月的假，去赌赛马。他的方法是，对预测赛马胜负的人进行分析、推测。他不需要熟谙那些马本身，只需研究比赛形式，看每个预测者所预测的机会与实际情况符合的程度。然后他听从成功预测者的建议。但是，他还辅以另外一种方法。每次比赛开始前，他核对布告板，看定出的赔率（反映到那时为止所收赌注的多少）与好的预测者所预言的是否相符。如果不相符，这就意味着参赌的人们在听从其他预测者的建议，或许就是那些名声不好的预测者的建议。杰斯瞅准最好的预测者所预言的赔率与布告板上所定赔率之间的这种差额，重重地下赌注。他用这种方式在赛马场稳稳当当地赚钱。但是不久之后，他总结出，在兰德公司他的薪水至少也有这么多，而且不必冒这么大的风险，因此他又回来工作了。这就是为什么我碰巧可以得到杰斯的帮助。
蒙特卡罗求和法用于对相当庞大的一组数的求和；它给出了一个从数字1 计算第一个量，从数字2 计算第二个量，从数字3 计算第三个量等等的计算规则。该规则使得量的变换从一个数变到另一个数相当顺利；从相应的数字计算每一个量，既冗长又乏味，因此人们往往不愿多做这样的计算。（现在，由于有了极其迅速而功能全面的计算机，我们可以直接求这样的和，但是35 年前的计算机需要有像蒙特卡罗方法这样的技巧，才能进行计算。）
假定我们要求1 亿个量的和。在此之前我们先要从相应的数字，按从1 到1 亿的顺序进行，来计算每个待加量。为了应用蒙特卡罗近似法，我们使用随机数表来得到1 与1 亿之间随机选择的若干个数，不妨假设是5000 个。5000 个数中的每一个，为1 至1 亿之间的任何数的概率是相同的。然后我们计算与这5000 个数相对应的量，将这些量当作待加的1 亿个量的代表性样本，并对它们求和。最后我们将所得结果乘以1 亿被5000 除所得的数（即20，000）。用这个方法，我们以一个短得多的近似计算代替了原来冗长的计算。真随机还是伪随机？
随机数表中应该是大于1 而小于某个固定的大值的一组整数，每个数都是随机挑出来的，而且在挑选过程中，上述范围内的各个数都有同样的被挑选机会。实际上，随机数表通常不是这么产生的，因而是一个伪随机数表！那些数是由计算机按照某个特定的数学规则迅速而容易地得出的，该规则非常地杂乱无章，所以整个过程被认为类似一个随机过程（例如，使用的规则从工程意义上来说可能是混沌性的）。然后，产生的数表可能被进行随机性检验，以确定它是否符合一个由真正的随机过程得出的数表在大多数情况下所应满足的统计标准。在兰德公司的表格里，那些数真是伪随机的吗？最后一刻的检验真的发现了某个统计标准未被完全满足吗？这就是为什么会出其不意地发现一个勘误表吗？这些问题的答案竟然都是否定的。毕竟，随机数表可以通过一个真正的随机过程，比如，一个利用量子力学现象的过程得到。事实上，兰德公司的数表就是通过使用真空管中产生的噪声这样一种随机方式来得到的。而且，勘误表是针对100，000个正常偏差数，而不是针对随机数表本身！如此具有教育意义的神秘现象原来一点也不神秘。然而，用随机方法需要作大量的工作，而利用决定论的规则则要方便得多。这只需让计算机迅速而容易地产生一个序列，并进而确保序列中多余的规律性在使用这些数的场合中相对来说没什么害处。可是，经验依然表明，将这样的伪随机序列当作随机序列使用，有时是很危险的。
最近我阅悉，许多实验室在使用一组极不随机的伪随机数。结果，用那些数字进行的某些计算出现了严重的错误。这个事件可以用来提醒我们，从决定论混沌或近混沌过程中产生数列具有相当程度的规律性。金融市场中的决定论混沌
有时，被认为是随机的序列结果却是伪随机的。例如，多年来许多新古典主义经济学家一直都在鼓吹，金融市场上受市场基本原理控制的，价格围绕价值的涨落构成了一种称为“随机游动”的随机过程。同时，那些深谙价格随时间变化的曲线图的“图表专家”，可以在市场投资方面为你提供建议，他们声称能从那些曲线中得到关于在不久的将来价格是上升还是下降的这样一些聊胜于无的预言。我曾经读到一位经济学家所写的一篇文章，作者在文章中对某些人主张使用这样的证据，而无视经济学家们关于价格涨落是随机过程的强调表示了强烈的愤慨之情。
但现在已有令人信服的证据表明，随机过程的观点是错误的。事实上，这些涨落与决定论混沌中的涨落一样，是伪随机的。理论上，他们包含有足够的规律性，使你可以从中赚钱。但并不是说那些图表分析家兜售的每一个金融方案都能让你发财；他们的建议可能多半是毫无价值的。不过，关于价格涨落不只是一个随机过程的观点本身，并不像那个愤怒的经济学家所认为的那样，是一种狂热的想法。（事实上，圣菲研究所的两个物理学家多依纳·法默（Doyne Farmer）和诺尔曼·派卡德（Nor… man Packard）已经停止了他们的科学研究工作，而去创办了一个投资公司。他们应用从决定论混沌及近混沌系统理论中得出的方法，来寻找金融市场中的规律，并由此进行投资。一开始，他们花了几个月的时间练习赌钱，然后开始利用一个大银行提供的资金进行真正的投资。迄今为止，他们干得相当不错。）
这里，我们已经遇到了关于“随机”一词的三种不同的专门用法：1。 随机比特串是指该比特串非常不规则，从而找不到任何规律来压缩对它的描述。2。 随机（random）过程是指偶然的或随机的（stochastic）过程。在产生具有给定长度的比特串时，它主要得出随机的、完全不可压缩的比特串；有时得出包含一定的规律性，因而具有一定程度的可压缩性的比特串；极少数情况下能够得到非常规则的、具有很大可压缩性的比特串，这些比特串一点也不随机。3。 随机数表通常由伪随机过程——一个事实上没有利用偶然性的决定论计算过程——产生的，但它非常紊乱（比如混沌式的杂乱），所以在很多场合下同随机过程非常相似，并且满足一些真正的统计过程通常所满足的统计标准。当应用这样的伪随机过程来产生比特串时，所得到的数串在相当大的程度上类似于一个真正的随机过程所产生的数串。莎士比亚和著名的猴子
下面我们将要讨论，为什么算法随机性或算法信息量与我们对于复杂性的直觉概念不完全相符。现在我们看一个著名的例子，一个猴子站在打字机旁，假定它随机地敲击各个键，每次击键时，任何符号或空格键被敲击的可能性是相等的。我怀疑实际中的猴子是否会那么做，但对我们所要讨论的问题来说，这并不重要。问题是，在特定的时间内那些猴子打出莎士比亚著作（或大英博物馆中的所有书籍——博物馆的这一部分现在称为大英图书馆）的可能性有多大。显然，如果一定数量的猴子中每只打出足够多的页数，那么整个这些片断包含莎士比亚著作（不妨假设是佛里奥版本）中的一个连贯的段落的概率是非零的。然而，那个概率极小。即使全世界所有的猴子花一万年的时间，每天各打字8 小时，打出的文章包含佛里奥版本的莎士比亚著作中一个连贯的部分的概率也是可以忽略不计的。在鲁塞尔·马洛尼（Russell Maloney）几年前发表于《纽约人》杂志上的题为《不变的逻辑》（Inflexible Logic）一文中，作者虚构了这样一个故事：6 个黑猩猩开始系统地用打字机打大英博物馆中的书籍，一本接一本，毫不犹豫，也不出错。但这些黑猩猩的结局却很悲惨：一个科学家为了维护自己的概率定律而将它们杀掉了。最后一只猩猩在一阵临死挣扎时，“猛然摔在它的打字机跟前。它痛苦地用自己的左手从打字机上拿下刚打完的，佛罗里欧（Florio）写的《蒙田》一书中的最后一页。它摸索着找到一张白纸，将它放入打字机里，然后用一个手指打着，‘《汤姆叔叔的小屋》（Uncle Tom’s Cabin），哈里特·比切尔·斯陀著。第一章？？’，然后它也死去了。”
考虑一只著名的非“纽约人”猴子，让它打一份与佛里奥版本同样长的材料，将那只猴子的一个典型的成品与莎士比亚的著作进行比较。哪个具有更大的算法信息量呢？显然，猴子打出来的作品具有更大的AIC。以随机过程（这里，随机是我们所给出的第二个意思）的方式，猴子极可能打出一个随机或近随机的符号序列（这里随机是第一个意思）。如果猴子的作品用某种标准方式编译成一个比特串，那么，在具有同样长度的比特串中，该比特串具有最大或近似最大算法随机性的可能性非常大。莎士比亚著作的随机性显然要小些。英语语法规则，拼写（纵然莎士比亚漫不经心地使用一个本来文法就不严的系统），合理性的需要及许多别的因素都使莎士比亚的文章具有一定的非随机性，从而使它比猴子所打的任何可能的、同样长的段落具有更低的算法信息量（或算法随机性）。对任何使用英语的作家来说也是如此；我们还没有考虑莎士比亚的独特性呢！有效复杂性
很明显，尽管AIC 或算法随机性有时被称为算法复杂性，但在大多数情况下它们与“复杂性”所指的意思没有多大的关系。为了定义有效复杂性，我们需要与在随机比特串中获得最大值的量截然不同的东西。事实上，正是系统或比特串的那些非随机性的方面，才促成了它的有效复杂性。有效复杂性，大致可
