关于复杂程度公式的一种说明

horizontal rule

张学文

zhangxw@mail.xj.cninfo.net 

20045

原刊于熵、信息、复杂性网站82期

组成论在广义集合、分布函数概念的基础上给出公式(7.5

7.5

本式是从“特殊的平均值”的角度引入了数量C,经过事后分析,它具有刻画广义集合内部状态的丰富程度的含义,于是它就成为复杂程度的定义公式了。但是一个合适的公式可以通过多种角度去认识。是否也可以“事先”通过对复杂程度含义的分析引出这个公式(尤其是对公式中为什么有对数)?下面是一个尝试(数学知识12可以略过不看)

数学知识1变量r如果与变量k乘正比例,如r扩大了3倍,而k也扩大3倍,写为

rk

它对应一个等式

r=ck

这里的c是它们的比例系数。如长方形的面积s在宽度不变的情况下与长度的L成正比例:

sL

当宽度为c时,有s=cL 如果变量r在变量k不变的情况下还与另外一个变量y成反正比例,那么可以分别写为

r2k/y

写为等式就是

r2=c2k/y

例子:当面积不变时长方形的宽度r2与长方形的长度y成反正比例。

数学知识2dk/k=dlnk 这是微积分知识。就不多说了。

 

1)组成论中复杂程度C的公式(7.8

有很多全都一样的球(个体)组成了一个系统(广义集合)。由于各个个体情况都相同,我们认为这个系统(这些球)的内部状态十分简单、不复杂,其复杂程度最底(=0)。假设情况有变化,例如每个球的颜色(颜色是一种特征,也可以是其他的特征如直径、质量等)都与其他的球不同,于是球(们)的颜色情况就比较复杂了。这个系统的复杂性加大了,复杂程度提高了。

如何定量分析各个球的颜色增加(没有涉及球的总数的增加)以及它引起的复杂程度的增加?

让我们先分析另外一个问题。

一个人得到1000元,他高兴,他高兴的程度固然可以设想为与其得到的财富成正比例,但是其高兴程度也与当时他原有的财富得到多少有关。因为把1000元给穷人或者给富翁的效果(引起的高兴程度)是不同的。不妨说,原有财富越多,相同的1000元引起的高兴程度就少。计算高兴程度只用财富的增加量度量是不大妥当。应当同时考虑他原有财产状况。我们认为考虑增加的“百分比”要妥当一些,确实使贫穷者增加10%的财富和使富翁增加10%的财富,他们的高兴程度类似。

现在我们把“高兴程度”的分析思路用到 “复杂程度”的场合:把增加***元改为使系统(很多球)里增加了一个新颜色,如从9个增加到10个,或者在99个颜色的基础上增加为100个颜色(它们的增加量都是1)。这时我们认为复杂程度C的增加量(ΔC)与颜色种类k所增加的百分比(Δk/k)成正比例,而不是仅与颜色增加量成正比例。(在全部球的颜色都相同时,k=1)。

于是有

ΔC∝Δk/k

或者ΔC=rΔk/k r=比例系数)

Δk=1时, k在前面的例子中是取9妥当,还是取10妥当?利用微积分的技术知识,恰当的处理办法是让Δk趋于0,注意到dk/k=dlnk于是以上的关系就变成了

dC=rdlnk

r是比例系数。积分得(积分下限是1—所有的球都有相同时的1个颜色,上限为k,并且注意ln1=0

C=rlnk

即系统内的各个个体的特征(如颜色)都相同,其复杂程度为0,如果有k个不同的特征,其复杂程度与k 的对数,lnk,成正比例。

上面分析了系统在其他情况不变化,只是特征、状态(如颜色)的数量变化时,它与复杂程度变化之间的关系。

如何考虑公式中比例系数r?由于组成论中有个体概念,即广义集合内的物质的多少是用个体数量的多与少来度量的。我们认为复杂程度是物理学中所谓的“广延量”,所以复杂程度还应当与物质的多少(不是颜色的多少)成正比例。于是一个个体个数为N的系统(广义集合)中复杂程度与个体数量N成正比例是妥当的。令计算中出现的比例系数r等于个体数量就妥当了。这样复杂程度变成了:

C=Nlnk 1

这里的复杂程度公式是一个个体总量为N,具有k个标志值时的复杂程度值计算公式。但是具体使用时还得做一些说明。如N=100k=10,即100个球(个体)有10种标志值(颜色)。但是公式中没有说明每种标志值占据了几个个体(不同颜色的球各有多少)。不同标志值占据的个体的数量的不同也应当对复杂程度有影响。而目前的公式体现不了这些新问题。看来这个公式的局限性。

现在我们不忙于克服这个局限性,先规定这样得到的公式应当用在每个标志值占据的个体的数量都相等的这个特殊(它也应当是复杂程度最得到体现的场合)情况。即100个个体,如果有10种标志值,也就意味着每种标志值占据了10个个体。于是就得到了一个要做附加说明的复杂程度计算公式。

下面我们再分析这个公式的更特殊的一个情况:每个标志值都仅占有一个个体。这时k=N,于是复杂程度等于:

C=NlnN 7.8

于是我们得到了组成论书中的公式(7.8)。在N个个体的标志值(颜色)彼此都不相同时,该系统的复杂程度就用这个公式计算。

k=1时,依公式C=Nlnk,既便一个系统内有100个个体,其复杂程度依然等于0。这就是所谓清一色(大家状态都相同)的系统(无论有多少个个体)的复杂程度总是等于零。

如果一个系统仅有一个个体,那么N=k=1,其复杂程度也是0。即,如果你把一个事物不做细的区分,它就没有内部的复杂程度,C=0

2)从(7.8)引出复杂程度通用公式(7.5

组成论书中的公式(7.8)和这里的公式(1)仅适用于比较特殊的场合,即各个个体的标志值都彼此不同,或者不同标志值的个体占有的比例都相同(=k/N)。对于相同标志值占有不同数量的个体的广义集合,它们是不适用的。如何得到一个在各种情况下都适用的复杂程度?

这里我们再举一个类比:一个人有1万元,后来一无所有,问他减少了多少元。显然是减少了1万元。类似地,如果有N个个体组成的一个集体(广义集合),最初N个个体彼此都不相同(全异),那么其复杂程度为NlnN,如果它们的标志值都变成了彼此没有区别(全同),那么根据前面的讨论,这个系统的复杂程度就变成了0。于是我们得到一个结论:N个全异个体变成全同个体,其复杂程度就减少NlnN

根据这个分析,我们规定:N个全异个体组成的广义集合,如果其中的n1个个体从全异变成全同,其复杂程度应当从NlnN减少了n1lnn1。即

C=NlnN- n1lnn1

C=-N-nln1/N- n1lnn1/N

C=-[N-n)个ln1/N]- n1lnn1/N

如果N个个体中另外有n2个个体彼此全同但是又与其他的任何个体不同,那么总体的复杂程度还要再减少n2lnn2。依此类推,自然有:

一个N 个个体组成的系统(广义集合)中,如果有n1个个体彼此相同,另外n2个个体彼此相同,ni个个体彼此相同,而它们之间又彼此不同,那么这个系统的复杂程度C 就是

C=- n1lnn1/N- n2lnn2/N…- nilnni/N…- nklnnk/N

C=-nilnni/N 7.5

它就是我们从另外思路得到的普遍适用的复杂程度公式(7.5)。

这个推导中的后一半在组成论书中已经有了。为了完整性,这里才把它再介绍一遍。