1701066138
用算法信息量度量复杂性
1701066139
1701066140
人们提出了许多改进方法来用熵度量复杂性。其中最著名的方法由柯尔莫哥洛夫（Andrey Kolmogorov）、查汀（Gregory Chaitin）和索罗蒙洛夫（Ray Solomonoff）分别独立提出，他们将事物的复杂性定义为能够产生对事物完整描述的最短计算机程序的长度。这被称为事物的算法信息量。 [88] “例如，考虑一个很短的（人工）DNA序列：
1701066141
1701066142
A C A C A C A C A C A C A C A C A C A C（序列1）
1701066143
1701066144
一个很短的计算机程序，“打印A C 10次”，就能输出这个序列。因此这个序列的算法复杂度很低。作为比较，下面是我用伪随机数发生器生成的一个序列：
1701066145
1701066146
A T C T G T C A A G A C G G A A C A T（序列2）
1701066147
1701066148
如果我的随机数发生器没有问题，这个序列就不会有可识别的特征，因此程序要长一些，比如“打印字符串A T C T G T C A A A A C G G A A C A T”。显然序列1可以压缩，而序列2则不能，因而包含更多算法信息。与熵类似，随机对象的算法信息量也会比我们直观上认为复杂的事物的信息量更大。
1701066149
1701066150
物理学家盖尔曼（Murray Gell-Mann）提出了一种称为“有效复杂性（effective complexity）”的相关度量， [89] 更符合我们对复杂性的直观认识。盖尔曼认为任何事物都是规则性和随机性的组合。例如，序列1就有非常简单的规则性：重复的A C模式。序列2则没有规则性，因为它是随机产生的。与之相比，生物的DNA则有一些规则性（例如，基因组不同部分之间存在重要关联），也有一些随机性（例如DNA中的垃圾）。
1701066151
1701066152
为了计算有效复杂性，首先要给出事物规则性的最佳描述；有效复杂性定义为包含在描述中的信息量或规则集合的算法信息量，两者等价。
1701066153
1701066154
序列1具有规则性，即A C不断重复。描述这个规则性所需的信息量就是它的算法信息量：程序“打印A C数次”的长度。因此，事物的结构可预测性越大，有效复杂性就越低。
1701066155
1701066156
序列2处于另一个极端，因为是随机的，所以没有规则性。因而也不需要信息来描述，虽然序列本身的算法信息量是最大的，序列规则性的算法信息量——其有效复杂性——却为零。简而言之，就如我们希望的，最有序和最随机的事物有效复杂性很低。
1701066157
1701066158
能够发育的生物的DNA具有许多独立和相关的规则性，这些规则需要可观的信息才能描述，因此会有很高的有效复杂性。显然，问题是我们如何给出这些规则？如果不同观察者对于系统的规则不能达成一致又怎么办？
1701066159
1701066160
盖尔曼用科学理论的形成做了类比，科学理论的形成实际就是寻找自然现象规律的过程。对于任何现象，都有多个描述其规律的可能理论，但显然理论有好有差，一些更加简洁优雅。盖尔曼对这个很有经验，他极为优雅的理论厘清了当时让人混淆的基本粒子类型及其相互作用，这让他获得了1969年的诺贝尔物理学奖。
1701066161
1701066162
类似的，对于提出的一个事物的各种不同规则集，我们可以利用奥卡姆剃刀（Occam’s Razor）来决定哪个是最好的。最好的规则集是能描述事物的最小规则集，同时还能将事物的随机成分最小化。例如，生物学家们现在已经发现了人类基因组的许多规律，包括基因、基因之间的相互作用，等等。但还有许多似乎不遵循任何规则的随机方面——也就是所谓的垃圾DNA。如果生物学的盖尔曼出现，他也许会找到约束更多基因组的极为简单的规则集。
1701066163
1701066164
有效复杂性是很有吸引力的思想，虽然同其他许多度量复杂性的提议一样，很难实际操作。也有批评意见指出，这个定义中的主观性也有待解决。 [90]
1701066165
1701066167
用逻辑深度度量复杂性
1701066168
1701066169
为了更加接近我们对复杂性的直觉，数学家班尼特在20世纪80年代初提出了逻辑深度（logical depth）的概念。一个事物的逻辑深度是对构造这个事物的困难程度的度量。高度有序的A、C、G、T序列（例如前面的序列1）显然很容易构造。同样，如果我要你给我一个A、C、G、T的随机序列，你也很容易就可以做出来，用个硬币或骰子就可以了。但如果我要你给我一个能够生成可发育的生物的DNA序列，如果不偷看真正的基因组序列，别说你，任何一个生物学家都会觉得很难办到。
1701066170
1701066171
用班尼特的话说，“有逻辑深度的事物 [91] ……从根本上必须是长时间计算或漫长动力过程的产物，否则就不可能产生”。或是像劳埃德说的，“用最合理的方法生成某个事物时需要处理的信息量 [92] 等同于这个事物的复杂性，这是一个很吸引人的想法”。
1701066172
1701066173
为了更精确地定义逻辑深度，班尼特将对事物的构造换成了对编码事物的0/1序列的计算。例如，我们可以用两位二进制数来编码核苷酸符号：A=00，C=01，G=10，T=11。用这个编码，我们就能将A、C、G、T转换成0/1序列。然后编写一个图灵机，用编写好的图灵机在空白带子上产生出这个序列，所需要的时间步就是其逻辑深度。
1701066174
1701066175
一般而言，多个图灵机都能产生出这个序列，所需的时间也可能不一样多。班尼特还必须说明应该用哪一个图灵机。他提出，应该根据前面提到的奥卡姆剃刀原则，选最短的那个（也就是状态和规则最少的那个）。
1701066176
1701066177
逻辑深度具有很好的理论特征，符合我们的直觉，但是也没有具体给出度量实际事物复杂性的方法，因为没有寻找生成指定事物的最小图灵机的可操作方法，更不要说如何确定机器运算所需的时间。此外，也没有考虑将事物表示成0/1序列的困难。
1701066178
1701066180
用热力学深度度量复杂性
1701066181
1701066182
20世纪80年代末，劳埃德和裴杰斯（Heinz Pagels）提出了一种新的复杂性度量 [93] ——热力学深度（thermodynamic depth）。劳埃德和裴杰斯的思想与班尼特的思想很相似：越复杂的事物越难构造。不过与图灵机生成对事物的描述所需的时间步不同，热力学深度首先是确定“产生出这个事物最科学合理的确定事件序列”，然后测量“物理构造过程所需的热力源和信息源的总量”。 [94]
1701066183
1701066184
例如，要确定人类基因组的热力学深度，我们得从最早出现的第一个生物的基因组开始，列出直到现代人类出现的所有遗传演化事件（随机变异、重组、基因复制等等）。可以想象，人类进化出来的时间比变形虫要长10亿年，热力学深度肯定也大得多。
1701066185
1701066186
同逻辑深度一样，热力学深度也只是在理论上有意义，要真的用来度量复杂性也存在一些问题。首先，我们要能列出事物产生过程中的所有事件。另外，也有批评意见指出， [95] 劳埃德和裴杰斯的定义中没有明确界定什么是“事件”。一次遗传变异到底是单个事件还是在原子和亚原子层面导致变异发生的上百万次事件呢？两个祖先的基因重组应当视为单个事件吗？还是应当将导致它们相遇、交配和产生后代的所有微观事件都包括进来呢？用更专业一点的话说，是不清楚如何将系统的状态“粗粒化”——也就是说，在列出事件时，如何确定哪些是相关的宏观状态。
[
上一页 ]
[ :1.701066137e+09 ]
[
下一页 ]