邏輯深度的量化研究

給定自然數(shù) $s$ 组橄，令 $K（x）$ 表示數(shù)據(jù) $x$ 的Kolmogorov復(fù)雜度荞膘，若長度不大于 $K（x）+s$ 的程序均無法用少于 $t$ 步的運(yùn)行生成 $x$ ，則稱 $t$ 的最大值為 $x$ 在顯著因子 $s$ 下的邏輯深度玉工。

令 $R（n）$ 代表任一超指數(shù)增長的遞歸函數(shù)（例如Ackermann函數(shù)）羽资，定義下列程序 $Exclude（n）$ ：

運(yùn)行全體長度小于 $n-1$ 的程序至多 $R(n)$ 步，收集其中停機(jī)者的全部輸出遵班，匯總為集合A屠升。

于是潮改，生成集合A需要上述程序和數(shù)據(jù) $n$ ,總長度為 $\log n+C$ 。集合A中的元素?zé)o法多于定義中的程序腹暖，故A的大小不超過2的 $n-1$ 次方汇在。

任給一恒小于這一上界的增函數(shù) $f(n)$ ，則不在A中且長度不超過 $n$ 的 $x$ 總數(shù)不小于2的 $n-1$ 次方脏答，從而大于 $f（n）$ 糕殉。因此，若按字母序列出前 $f（n）$ 個(gè)不在A中的數(shù)據(jù)殖告，其長度均不超過 $n$ 阿蝶。

據(jù)此我們構(gòu)造下列程序（包含可變參數(shù) $n,K$ ）：

調(diào)用 $Exclude（n）$ 生成集合A，然后依字母序枚舉不在A中的元素黄绩，輸出其中第K個(gè)羡洁。要求 $K\leq f（n）$

我們注意到，需要輸入的長度是 $\log n+\log K+C$ 爽丹，代入上述約束得最終程序長度不超過 $\log n+\log f（n）+C$ 焚廊。

我們選取 $f(n)$ 使得： $\log f(n)\leq n-（\log n+s +1+C）$

則總長度不大于n-s-1。

于是习劫，我們用不大于n-s-1的信息量可以輸出一個(gè)不在A中的數(shù)據(jù)咆瘟。但這種數(shù)據(jù)無法用小于n-1的信息量在R（n）步內(nèi)輸出（否則它就會(huì)落入A中）。從而這些數(shù)據(jù)的邏輯深度至少是R（n）诽里，顯著因子為s袒餐。

此類數(shù)據(jù)的個(gè)數(shù)就是K值的上限 $f(n)$ ,根據(jù)選取它的條件可以得知：無論R（n）是增長多快的遞歸函數(shù)，長度上限n的數(shù)據(jù)中都有2的 $n-（\log n+s +1+C）$ 次方個(gè)案例達(dá)到所要求的邏輯深度谤狡！

由于長度不超過n的數(shù)據(jù)（含空串）共 $O（2^n）$ 個(gè)灸眼，我們根據(jù)上式可知，無論我們將增長多快的遞歸函數(shù)作為“爆炸式增長”的標(biāo)準(zhǔn)墓懂，長度不超過n的數(shù)據(jù)中都會(huì)有 $\Theta （1/n）$ 的比例發(fā)生“深度爆炸”焰宣，達(dá)到天文數(shù)字的邏輯深度。這一特征可稱作邏輯深度特有的長度反比律捕仔。

推論：全體長度不超過n的數(shù)據(jù)的平均邏輯深度隨n的增長快于n的任意遞歸增函數(shù)匕积。

同理可知，將顯著因子s增大可以指數(shù)地減少這些邏輯極深數(shù)據(jù)的比例榜跌。這也是它這一名稱的來由闪唆。

最后編輯于：2020.03.24 22:22:38

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者