给定自然数,令表示数据的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增大可以指数地减少这些逻辑极深数据的比例。这也是它这一名称的来由。