逻辑深度的量化研究

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