逻辑深度的量化研究
2020-03-23 本文已影响0人
十酒三
给定自然数,令
表示数据
的Kolmogorov复杂度,若长度不大于
的程序均无法用少于
步的运行生成
,则称
的最大值为
在显著因子
下的逻辑深度。
令代表任一超指数增长的递归函数(例如Ackermann函数),定义下列程序
:
运行全体长度小于
的程序至多
步,收集其中停机者的全部输出,汇总为集合A。
于是,生成集合A需要上述程序和数据,总长度为
。集合A中的元素无法多于定义中的程序,故A的大小不超过2的
次方。
任给一恒小于这一上界的增函数,则不在A中且长度不超过
的
总数不小于2的
次方,从而大于
。因此,若按字母序列出前
个不在A中的数据,其长度均不超过
。
据此我们构造下列程序(包含可变参数):
调用
生成集合A,然后依字母序枚举不在A中的元素,输出其中第K个。要求
我们注意到,需要输入的长度是,代入上述约束得最终程序长度不超过
。
我们选取使得:
则总长度不大于n-s-1。
于是,我们用不大于n-s-1的信息量可以输出一个不在A中的数据。但这种数据无法用小于n-1的信息量在R(n)步内输出(否则它就会落入A中)。从而这些数据的逻辑深度至少是R(n),显著因子为s。
此类数据的个数就是K值的上限,根据选取它的条件可以得知:无论R(n)是增长多快的递归函数,长度上限n的数据中都有2的
次方个案例达到所要求的逻辑深度!
由于长度不超过n的数据(含空串)共个,我们根据上式可知,无论我们将增长多快的递归函数作为“爆炸式增长”的标准,长度不超过n的数据中都会有
的比例发生“深度爆炸”,达到天文数字的逻辑深度。这一特征可称作逻辑深度特有的长度反比律。
推论:全体长度不超过n的数据的平均逻辑深度随n的增长快于n的任意递归增函数。
同理可知,将显著因子s增大可以指数地减少这些逻辑极深数据的比例。这也是它这一名称的来由。