這篇筆記緊跟著上一篇。

在這篇記錄中，所謂隨機(jī)字符串被這么定義：
如果字符串只能被直接將其打印出這一種圖靈機(jī)所輸出，而不能成為別的任何比這圖靈機(jī)更精簡(jiǎn)的別的圖靈機(jī)的輸出，那么這個(gè)字符串就稱為是隨機(jī)的。
這個(gè)表達(dá)繼承自這么一個(gè)思路：隨機(jī)字符串不能成為任何函數(shù)的結(jié)果。
而這個(gè)表達(dá)本身又關(guān)聯(lián)到AIT^[1]的一個(gè)有趣的理論：K氏復(fù)雜度，或者說(shuō)描述復(fù)雜度，或者說(shuō)算法熵。

一個(gè)字符串s的K氏復(fù)雜度可以這么表示：
K(s)=min(len(t), t屬于T_s)
其中T_s表示所有輸出結(jié)果為s的圖靈機(jī)構(gòu)成的集合，t是T_s的元素，len(t)表示t在通用圖靈機(jī)中作為輸入的字符串長(zhǎng)度。
因此，s的K氏復(fù)雜度是所有可以輸出s的圖靈機(jī)中最“短”的圖靈機(jī)的字符量。
由此引申出的兩個(gè)概念就是：

1. 如果K(s)>len(s)，那么s就是隨機(jī)的；
2. 如果K(s)<len(s)，那么s可以被壓縮。

也就是說(shuō)，隨機(jī)字符串是不可壓縮的——廢話。

當(dāng)然，我們可以做一個(gè)小小的改變——假定P(s)是所有直接打印s的圖靈機(jī)中字符量最少的那個(gè)圖靈機(jī)的字符量，于是上面的結(jié)論可以修改為：

1. 如果K(s)>P(s)，那么s就是隨機(jī)的；
2. 如果K(s)<P(s)，那么s可以被壓縮。

當(dāng)然，這么改進(jìn)并不會(huì)從本質(zhì)上改變什么，只不過(guò)在s本身足夠簡(jiǎn)短的時(shí)候讓上面的結(jié)果更有效一點(diǎn)罷了（但是我們卻擔(dān)負(fù)上了什么是“直接打印”的定義疑難）。

到這里一切都看上去蠻正常的。

但，有一個(gè)問題最近卻冒了上來(lái)——
假定t是輸出s的所有圖靈機(jī)中最“短”的那個(gè)，同時(shí)在通用圖靈機(jī)U看來(lái)，t本身也是字符串（萬(wàn)物皆數(shù)據(jù)，萬(wàn)物皆函數(shù)，萬(wàn)物皆圖靈機(jī)，lambda教萬(wàn)歲～～）。
現(xiàn)在有一個(gè)問題：t輸出s，那么s的信息是不是都蘊(yùn)含在t中呢？
這里我們假定t不接受任何輸入——即便接受輸入，比如t(x)=s，那么我們可以構(gòu)造t'=()->t(x)來(lái)作為這里的t，只不過(guò)“微調(diào)”了最“短”這個(gè)要求的定義而已——那么也就是說(shuō)，通過(guò)t獲得s的過(guò)程完全不借助外界，外界信息流入為0，從而流出的信息，也就是s所蘊(yùn)含的信息，必然全部來(lái)源于圖靈機(jī)t。
從而，圖靈機(jī)t與字符串s必然擁有相同的信息量。
而，在U看來(lái)，t是否可壓縮？如果t可壓縮，那么和最短要求矛盾。
因此，t是不可壓縮的，從而按照K氏復(fù)雜度的定義，不可壓縮的就是隨機(jī)的，從而具有極高算法熵——那么問題來(lái)了，t和s具有相同信息量，s可壓縮，從而不是隨機(jī)de；t不可壓縮，從而是隨機(jī)的。
那么，這就是說(shuō)，隨機(jī)與否和是否含有信息沒關(guān)系，這里隨機(jī)與否僅僅與是否可壓縮有關(guān)。
可，這樣的“隨機(jī)”真的夠“隨機(jī)”么？

舉例來(lái)說(shuō)，一副800px × 600px的風(fēng)景畫，每個(gè)像素上都是rgb256色值，完全不做壓縮就以這個(gè)800 × 600 × 8 × 8 × 8 = 2.4576億個(gè)字節(jié)地寫下來(lái)，那么這幅畫的信息量當(dāng)然是很大的。然后，這幅風(fēng)景畫通過(guò)無(wú)損壓縮成為PNG文件，這個(gè)PNG文件與原來(lái)的風(fēng)景畫含有完全相同的信息，但這個(gè)PNG文件已經(jīng)幾乎不可能再被進(jìn)一步壓縮了。
因此，這就是說(shuō)，可壓縮的字符串（2.4576億字節(jié)）與不可壓縮的字符串（PNG）具有（幾乎）相同的信息量，但在可壓縮性上兩者完全不同。

因此，如果說(shuō)隨機(jī)表示無(wú)信息或者信息量很低，那么顯然在上面的例子中，不可壓縮的字符串與可壓縮的字符串具有幾乎相同的信息量，從而使得是否可壓縮與是否含有較高信息、是否隨機(jī)沒有了完全必然的聯(lián)系。

進(jìn)一步，事實(shí)上K氏復(fù)雜度本身有表示了算法上，我們發(fā)現(xiàn)在上述例子中，原始字符串與壓縮后的字符串很可能共享了相同的K氏復(fù)雜度，而這也就是說(shuō)這兩個(gè)字符串具有相同的算法熵。
算法熵相同，那么信息量應(yīng)該也可以理解為相同——從這個(gè)角度來(lái)說(shuō)，是否可壓縮完全不影響信息含量。

換言之，如果<u>隨機(jī)只是被理解為不可壓縮，從而表示“不能由直接打印字符串本身以外的任何方法來(lái)獲得”</u>，那么這樣的隨機(jī)與熵的高低以及信息含量的多少?zèng)]有關(guān)系。

但，反過(guò)來(lái)，如果將隨機(jī)理解為熵極大的狀態(tài)，從而信息量盡可能地小，這樣的隨機(jī)字符串是否依然可壓縮呢？
這個(gè)問題倒是還沒有想明白。

如果說(shuō)熵極大隨機(jī)不可壓縮，那么也就是說(shuō)熵極大隨機(jī)自然就包含在了不可壓縮隨機(jī)之中，從而熵極大隨機(jī)自然也是“不能由直接打印字符串本身以外的任何方法來(lái)獲得”的。
而如果熵極大隨機(jī)可壓縮，這就好玩了，它表示可以通過(guò)某些圖靈機(jī)來(lái)生成熵極大隨機(jī)的字符串，極端情況下，就是說(shuō)，可以通過(guò)某些函數(shù)來(lái)生成熵極大的隨機(jī)字符串——這點(diǎn)本身似乎是難以想象的。
所以，個(gè)人這里傾向于認(rèn)為熵極大的隨機(jī)是不可壓縮的。
而這就表示了這么一種情況：
一個(gè)字符串可以被分解為這么兩部分：可以被壓縮而去掉的“冗余”部分，以及不可被去掉的“信息”部分。
K氏復(fù)雜度實(shí)際上給出的是不可被壓縮去除的信息所對(duì)應(yīng)的算法熵。

Kolmogorov與Martin-Lof關(guān)于隨機(jī)的理念包括這么兩條^[2]：

1. 不可預(yù)測(cè)：如果知道隨機(jī)序列的前n項(xiàng)，無(wú)法推測(cè)出第n+1項(xiàng)；
2. 不可壓縮。

下面，我們來(lái)看一個(gè)問題：
數(shù)列0, 1, 2, 3, 4, 5, 6, 7, 8......
這樣的序列當(dāng)然是有規(guī)律的不隨機(jī)的，然后假定可以生成這貨的最短函數(shù)為：f(i)->i。
這樣，該數(shù)列q的K氏復(fù)雜度也就是f的K氏復(fù)雜度，為7，且f不可進(jìn)一步壓縮。
那么，我如果直接給你f(i)->i，它到底是否隨機(jī)呢？是否可預(yù)測(cè)呢？是否有信息呢？
信息方面，顯然是有的，而要說(shuō)隨機(jī)，這貨明顯是一個(gè)函數(shù)啊。。。
可預(yù)測(cè)性這個(gè)問題就比較微妙了，或許我們可以看下面這個(gè)問題：

如果你已經(jīng)知道了f(i)->，你是否可能知道下一位是i？

這個(gè)問題就很微妙了——如果你已經(jīng)知道原始數(shù)列是0, 1, 2, 3, 4, 5, 6, 7, 8......，那么你自然可以推斷出下一位是i。但要知道這個(gè)的前提是你必須知道一組原始信息。
也就是說(shuō)，現(xiàn)在我們面對(duì)的是這么一個(gè)情況：

• 如果不知道一組原始數(shù)據(jù)，那么我們其實(shí)很難知道f(i)->的下一位是什么

下一位可以是i，也可以是1，也可以是i+1，或者2*i，或者exp(i,2)，都有可能

• 如果知道原始數(shù)據(jù)，那么我們應(yīng)該可以有較大地把握知道下一位是什么，但此時(shí)需要額外輸入——原始數(shù)據(jù)。

如果讓我們反過(guò)來(lái)，我們已經(jīng)知道0, 1, 2, 3, 4, 5, 6, 7, 8這前九位值，是否可以合理地推斷出下一位呢？我們同樣有和上面一樣的兩個(gè)情況：

• 如果不知道正確的生成這個(gè)字符串的函數(shù)，那么我們較難確定下一位到底是多少；

比如說(shuō)，生成這個(gè)字符串前九位的函數(shù)可能是f(i)->i，那么下一位就是9；也可能是f(i)->floor(1.12*i)，那么下一位就是10；還可能是f(i)->i-floor(0.12*i)，那么下一位就是8。因此知道前九位并不能唯一確定第十位。

• 如果知道正確的生成這個(gè)字符串的函數(shù)，那么我們可以準(zhǔn)確知道下一位是多少。

如果將原始序列記為D，其前n位記為D(n)，第n位記為D_n，對(duì)應(yīng)的生成D的圖靈機(jī)記為T，其前n位字符串記為T(n)，第n位記為T_n，那么上面的關(guān)系實(shí)際上就是：

• 不知道T，那么通過(guò)D(n)我們<u>無(wú)法知道</u>唯一的D_{n+1}
• 不知道D，那么通過(guò)T(n)我們<u>無(wú)法知道</u>唯一的T_{n+1}
• 知道T，通過(guò)D(n)<u>完全可以</u>確定D_{n+1}
• 知道D，通過(guò)T(n)<u>應(yīng)該可以</u>確定T_{n+1}

我們發(fā)現(xiàn)這里的情況呈現(xiàn)出一種不對(duì)稱性。
在前兩組（不知道T和D）中，實(shí)際上不能確定的“程度”或者說(shuō)確定的“難度”也是不同的，在不知道T的情況下從D(n)推斷D_{n+1}，隨著n的增大，可選擇的預(yù)測(cè)范圍是可以縮小的；而在對(duì)偶的情況下，不知道D要從T(n)推斷T_{n+1}則是完全沒有可能。
在后兩組（知道T和D）中，這種不對(duì)稱就更加明顯了。
如果我們將從D(n)推斷D_{n+1}的難易程度成為D的可預(yù)測(cè)性，從T(n)推斷T_{n+1}的難易程度成為T的可預(yù)測(cè)性，那么上述不對(duì)稱性其實(shí)就是說(shuō)：無(wú)論知不知道D和T，D的可預(yù)測(cè)性都好于T。

事實(shí)上第四種情況與第一種情況還存在一組聯(lián)系，因?yàn)橐龅降谝粭l，我們實(shí)際上就是要先做到一個(gè)受限版本的第四條，而且隨著n的增加，這個(gè)限制也在減弱。
而，第二與第三條則無(wú)法構(gòu)成這種聯(lián)系。

在上一小節(jié)中的圖像壓縮的例子中，我們假定現(xiàn)在D是原始字符串，T是D經(jīng)過(guò)壓縮算法獲得壓縮字符串，那么上述不對(duì)稱性恐怕就會(huì)被打破：
如果知道T，我們當(dāng)然可以從D(n)推斷出D_{n+1}；反之，如果知道D我們自然也可以通過(guò)T(n)推斷出T_{n+1}。而，反過(guò)來(lái)，如果不知道T或者D，我們也就無(wú)法通過(guò)D(n)或T(n)來(lái)獲知D_{n+1}或T_{n+1}了。
這里兩者完全對(duì)稱——也就是說(shuō)此時(shí)D和T的可預(yù)測(cè)性相當(dāng)。

從這兩個(gè)例子，我們或許可以得到這樣的結(jié)論：
D壓縮后的字符串可以分解為兩部分，一部分是包含了構(gòu)造D的算法的，記為P；另一部分則包含了通過(guò)P構(gòu)造出D的核心數(shù)據(jù)，記為K。
從而，P的可預(yù)測(cè)性比D更弱，而K的可預(yù)測(cè)性與D相當(dāng)。

現(xiàn)在，我們可以將數(shù)據(jù)D分解為三部分：

1. D的可壓縮部分R；
2. D的生成算法部分P；
3. D的核心數(shù)據(jù)部分K。

其中，R可以被壓縮掉，P和K不可被壓縮，P的可預(yù)測(cè)性弱于D，K的可預(yù)測(cè)性與K相當(dāng)。

在論文《Logical Depth and Physical Complexity》中，就給出了與這里相同的結(jié)論，其中K便是字符串的邏輯深度，并被引申到了物理系統(tǒng)的復(fù)雜性這一跨界問題上。

好了，今天睡前要記的筆記就記到這里，歐耶～～～

1. Algorithmic Information Theory，算法信息論。 ?

2. 可以看我上次寫的文章。和原始的要求不同的是，這里略作了修改，加上了第三條。 ?