蛴谖耷疃欢显龀ぃ绻牵龀さ目炻绾巍Ｋ蛩辉趺垂匦哪掣鯝IC 与另一个AIC 之间由于系统描述中的种种不定性而引起的无关紧要的差异。
我们可以从那些理论家那里获得一些有趣的经验，那就是，即使我们不限于研究那些趋于无限大的系统，我们也应该懂得，随着比特串逐渐变长，关于简单性与复杂性的讨论变得越来越有意义。在另一种极端情形，即比特串中只有一个比特，谈论简单性与复杂性显然是毫无意义的。信息的定义
现在我们必须对算法信息量与信息作出区分。这方面有一些人，比如，现代信息理论的奠基人克劳德·香农（Claude Shan…non）曾经讨论过。信息主要涉及到从被选物中作出抉择，如果那些被选物可以简化为一序列两种选择，其中每种选择的或然性完全一样，那么，我们可用一种最简单的方式将其表示出来。例如，假若你得知抛硬币的结果是反面而不是正面，那么你就获得了一个比特的信息。如果你获悉三次连续抛币的结果是正面、反面和正面，那说明你已经获得三个比特的信息。
“二十个问题”的游戏在或然性相同或或然性近乎相同的一连串两种选择中，提供了一个表示各种极不相同的信息的极好例子。游戏由两个人来玩，第一个人构思一个东西，然后第二个人要在被告知它是动物、蔬菜、还是无机物之后，用20 或不到20 个问题来猜出这个东西。问题的答案只能是“是”或“否”；每次回答都是一次两种选择。对第二个人来说，他提出的问题要尽可能在两个或然性接近相同的被选物之间作出选择，这将会对自己最有利。例如，在知道该东西是无机物时，提问者不应该直截了当地问它是不是霍普（Hope）钻石。他可以问，“它是天然的（而不是人工制造或改造的）吗？”这里，肯定回答和否定回答的概率是大致相等的。如果回答是“否”，那么下一个问题可以问：“它是一个特殊的物体而非一类物体吗？”当回答“是”与“否”的概率相等时，每个问题将引出一个比特的信息（这是一个问题所能引出的最多的信息）。20 个比特的信息相当于从1，048，576 个或然性相等的被选物中作出一个选择，其中1，048，576 是20 个2 的乘积（2 的20 次方）。这一乘积是长度为20 的各种不同比特串的数目。
要特别提及的是，在讨论AIC 与信息时，比特串的用法是不一样的。在算法信息量情形下，考虑的是单个的比特串（最好是长比特串），它内部的规律是用一个通用计算机打印出该比特串到停机的最短程序长度（用比特表示）来测度的。与之形成对比的是，在信息的情形下，你可能考虑从具有给定长度的所有各种不同的比特串中作出一个选择。若它们的或然性均相同的话，他们的长度就是信息的比特数。
你也可以考虑一组比特串，比如或然性相同的一组，每个比特串都有其特定的AIC 值。在这种情况下，定义一个由比特串的数目及该组比特串的平均的AIC 值所决定的信息数量，往往很有用。压缩和随机串
算法信息量有一个很奇特的性质，为了对它进行讨论，我们有必要先来看看不同消息串的相对“可压缩性”。对于一个有给定长度（不妨假设很长）的比特串来说，我们可以探究，何时其算法复杂性高，何时其算法复杂性低。如果一个长的比特串为110110110110110110110？110110，那么，我们可以通过一个表达“将110 打印若干次”的极短的程序来得到它。这样一个比特串具有一个很低的AIC，尽管它的长度很长。这意味着它具有很大的可压缩性。
与此相对照的是，在数学上可以证明，大多数具有某一给定长度的比特串是不能压缩的。换句话说，能够产生这些串（并进而使计算机停机）的最短程序为，在PRINT 后写上整个数串。具有给定长度的这样一个比特串有着最大的AIC。这儿没有任何规则、算法及理论能够进一步简化这种比特串的描述，从而使之能被用一更短的信息来描述。这样的比特串被称为“随机”串，因为它没有规律可循，因此不能被压缩。随机串具有最大的AIC，这一事实可以解释为什么AIC（算法信息量）又可称为算法随机性。AIC 的不可计算性
AIC 的奇特性在于它的不可计算性。尽管大多数比特串是随机的，但是我们没法准确地知道究竟哪些是随机的。一般来说，我们不能肯定某个给定比特串的AIC 一定不低于我们所认定的。这是因为总可能有一个理论、一种算法能使该比特串被进一步压缩，只是这个理论、算法我们永远也发现不了。更严格地说，我们无法找到能导致进一步压缩的所有理论。格里高里·蔡廷曾在几年前证明过这一论点，他的工作很容易使人想起库特·哥德尔一个著名结论的一部分。哥德尔是一个数学逻辑学家，他在30 年代早期所作出的关于数学公理系统的局限性的发现，曾经震动了整个数学界。在他之前，数学家们曾希望可以设计这样一个数学公理系统，理论上它可以被证明是自治的，并能用来推证所有数学定理的正确性或谬误性。哥德尔证明这些目的一个也不能实现。
像这样的否定性结果往往象征着数学或科学上的巨大进步。我们可以比较一下爱因斯坦关于没有绝对时间或空间，而只有联合时空的发现。事实上，哥德尔和爱因斯坦是好朋友。50 年代早期，在新泽西的普林斯顿高级研究院，我常常看见他们一起步行去工作，但看起来他们这一对给人一种古怪的感觉。哥德尔个子很小，在他的衬托下，爱因斯坦看起来相当高。他们曾经讨论过深奥的数学或物理问题吗？（哥德尔不时地研究一些与广义相对论有关的问题。）或者他们的谈话仅仅是关于天气和他们自身的健康问题？
哥德尔的结论中与我们的讨论有关的部分，是关于不可判定性的问题，即：对于任何一个数学公理系统，原则上总存在一些命题，这些命题在已有的公理基础上不可判定。换句话说，理论上有一些定理既不能被证实，也不能被证伪。
最突出的不可判定的命题是与公理无关的一种陈述。你可以通过引入这样一个陈述作为一个新公理，或引入一个与之相反的陈述，来扩充已有的那组公理。
但是，另外一些不可判定的命题则具有不同的性质。例如，假定一个关于正整数的不可判定的命题的形式如下：“每个大于2 的偶数都有如下性质？？”如果这样一个命题有任何例外，原则上我们可以把它找出来。我们可用足够长的时间，连续检验每个偶数（4，6，8，10，？？），直到发现一个不具备命题中所说性质的数为止。这样就直接证明了该命题是错误的，同时也推翻了它的不可判定性，因为不可判定性的严格意义是，命题不能被证实或证伪。因而，这一命题没有例外情形。一般来说，“真实”这一词的意义是说，该命题是真实的。
下面我们将更加具体地讨论这一点。考虑这样一个特殊的命题，它的正确性经过几个世纪的科学家们的努力也没有得到证明，尽管也没有发现任何例外情况。这个命题就是哥德巴赫猜想（Goldbach’s conjecture），其内容是，每个大于 2 的偶数等于两个素数之和。素数是大于1，且不能被自身和1 以外的任何数整除的数。根据这一点可知，最小的几个素数是2，3，5，7，11，13，17，19，23，29，31 和37。从列出的这些数中可以看出，4 和62 之间的任何偶数都可以用至少一对素数之和来表示。计算机的计算表明，某个相当相当大的数以内的各个偶数都有这样的性质。然而，这样的计算还不能说那个猜想就被证实了，因为对于更大的数它仍然可能失败。只有严密的数学证明才能将猜想变成一个已证明的定理。
没有理由认为哥德巴赫猜想是不可判定的，我们只是假定它是不可判定的。那么由此可知，它应该是真实的，尽管不能证明这一点，因为它可能没有任何例外的情况。任何大于2 的偶数而不能表示为2 个素数之和的存在，将会否证这个猜想，并因此推翻它的不可判定性。
如蔡廷所证明的那样，在问题的背景中往往隐藏着这样一些正确但不可证的理论，或许其中有一个理论能使一个我们认为不可压缩的长信息串能被压缩，或使一个我们认为是最短的信息串能被进一步压缩。因此，一般来说，我们不能确定算法信息量的值；只能给出一个它不能超出的上限。既然只能确定它在低于这一上限值的范围内，因而AIC 是不可计算的。不可计算性这一性质给我们带来种种不便，但使我们不能用算法信息量来定义复杂性的，还有另一个不同的原因。尽管通过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 和有花的牌）都在牌桌的某一部分，他就赌大的。这个方法仅当使用一副牌的时候管用。不久后，所有的赌场都改变了赌博规则（可以说是对“学者们”适应的结果），而开始同时使用好几副牌。杰斯于是转向其他方面的赌博。
有一次，他曾经向兰德公司请了好几个月的假，去赌赛马。他的方法是，对预测赛马胜负的人进�