【正文】 位研究研究者 R. Solomonoff A. Kolmogorov B. G. Chaitin Univ. 可計(jì)算理論 2020/11/17 25/77 Kolmogorov(?) Complexity R. Solomonoff Univ. 可計(jì)算理論 2020/11/17 26/77 Kolmogorov(?) Complexity A. Kolmogorov Univ. 可計(jì)算理論 2020/11/17 27/77 How Universal is K? 如何通用？有多大誤差？ Recall: (Fix a universal Turing machine U.) 下面的與定義６ .20 稍有差別， 等價(jià) ? ? xo u tp u ts y a n d M on U:yMm in)x(KyM ???Problem: The function K depends on the universal U that is used: we should say KU instead of K… Maybe that for another TM V, the plexity measure KV is much smaller than KU? Univ. 可計(jì)算理論 2020/11/17 28/77 How Universal is K? 如何通用？有多大誤差？ Recall: (Fix a universal Turing machine U.) ? ? xo u tp u ts y a n d M on U:yMm in)x(KyM ???Problem: The function K depends on the universal U that is used: we should say KU instead of K… Maybe that for another TM V, the plexity measure KV is much smaller than KU? K似乎與通用圖靈機(jī)的選擇有關(guān)， 下頁證明 即使與 U有關(guān)， 也影響不大 Univ. 可計(jì)算理論 2020/11/17 29/77 Invariance Theorem ep217 Theorem : Let U be a universal TM, then for any other description method V, we have KU(x) — KV(x) ? c for all strings x. 通用機(jī)描述與其它 描述的差別 有界，不會(huì)太大、 Note that the constant c depends on V and U, but not on x. 且差值與 x 無關(guān) Proof: Because U is universal, we can give a finite description to U how it should simulate V. Let this description be of size c. 結(jié)論：用通用機(jī)來估計(jì)復(fù)雜度，只相差一個(gè)常數(shù) . Univ. 可計(jì)算理論 2020/11/17 30/77 Invariance Theorem ep217 Theorem ６ .2１ : Let U be a universal TM, then for any other description method V, we have KU(x) — KV(x) ? c for all strings x. 同串不同機(jī)的極小描述 相差不會(huì)太大、 Note that the constant c depends on V and U, but not on x. 且差值與 x 無關(guān) Proof: Because U is universal, we can give a finite description to U how it should simulate V. Let this description be of size c. 結(jié)論 ：用通用機(jī)來估計(jì)復(fù)雜度，只相差一個(gè)常數(shù) . Univ. 可計(jì)算理論 2020/11/17 31/77 An Obvious First Result ep215 可自學(xué) Theorem ６ .21: There exists a constant c, such that K(x) ? |x| + c, for every x. (―The plexity of a string can never be much bigger than its length.‖) 串的復(fù)雜度 不會(huì)比原文長太多 Proof: Let M be the TM that simply outputs its input string y: M(y)=y. Then Mx is a description of x, and hence K(x) ? |M| + |x|. Let c=|M|. (Here we benefit from our way of encoding (M,y). Univ. 可計(jì)算理論 2020/11/17 32/77 An Obvious First Result ep215 可自學(xué) Theorem ６ .21: There exists a constant c, such that K(x) ? |x| + c, for every x. (―The plexity of a string can never be much bigger than its length.‖) 串的復(fù)雜度 不會(huì)比原文長度 大太多 Proof: Let M be the TM that simply outputs its input string y: M(y)=y. Then Mx is a description of x, and hence K(x) ? |M| + |x|. Let c=|M|. (Here we benefit from our way of encoding (M,y). Univ. 可計(jì)算理論 2020/11/17 33/77 Data Compression ep215 cp14７ 可自學(xué) Theorem C６ .22: There is a constant c such that K(xx) ? K(x) + c, for every string x. 雙倍串的的復(fù)雜度 不比原串的復(fù)雜度 大很多 Proof: Take the TM M that given input Nx: 1) Calculate the output s of N on x 2) Output ss Let d(x) be the minimum description of x, then Md(x) will give a description of xx. Hence, K(xx) ? |M| + |d(x)| = K(x) + c. Univ. 可計(jì)算理論 2020/11/17 34/77 Data Compression ep215 cp147 Theorem : There is a constant c such that K(xx) ? K(x) + c, for every string x. 雙倍串的的復(fù)雜度 不比原串的復(fù)雜度 大很多，直觀地，增加一句話， ‖輸出重復(fù)一次 ‖ 但把上述觀察敘述清楚，應(yīng)該如下敘述： Proof: Take the TM M that given input Nx: 1) Calculate the output s of N on x 2) Output ss Let d(x) be the minimum description of x, then Md(x) will give a description of xx. Hence, K(xx) ? |M| + |d(x)| = K(x) + c. Univ. 可計(jì)算理論 2020/11/17 35/77 Concatenation 一個(gè)意料之外的例子 You would expect that for all strings x and y: K(xy) ? K(x) + K(y) + c, for some c ？ However, this is not true. 要多花一些代價(jià) The problem lies –again– in the separation between d(x) and d(y). Instead, we have a constant c such that: K(xy) ? K(x) + K(y) + 2log(K(x)) + c, for all strings x and y. X的編碼長度的 2倍 為 l 描述 X,Y的分割點(diǎn)付出的代價(jià)，下頁 Univ. 可計(jì)算理論 2020/11/17 36/77 Log Cost of Concatenation ep216 cp147 Theorem (log): There is a c such that K(xy) ? K(x) + K(y) + 2log(K(x)) + c, for all x,y. 自學(xué)（不難，意義較?。? Proof: Let m be the logarithm of |d(x)|, then the string ―1m0 |d(x)| d(x)‖ gives a selfdelimitin－ description of x. (We need 2m bits to indicate the length of d(x).) Hence the input ―1m0 |d(x)| d(x) d(y)‖ gives an unambiguous description of xy. Univ. 可計(jì)算理論 2020/11/17 37/77 Log Cost of Concatenation ep216 cp147 Theorem (log): There is a c such that K(xy) ? K(x) + K(y) + 2log(K(x)) + c, for all x,y. 自學(xué)（不難，意義較?。? Proof: Let m be the logarithm of |d(x)|, then the string ―1m0 |d(x)| d(x)‖ gives a selfdelimitin－ description of x. (We need 2m bits to indicate the length of d(x).) Hence the input ―1m0 |d(x)| d(x) d(y)‖ gives an unambiguous description of xy. Univ. 可計(jì)算理論 2020/11/17 38/77 不可壓縮串 ? X是串， c0 , K(x)|x|c, 稱 x是 C可壓縮（長度壓了 C） ? 反之 不可 c壓縮 , c=1時(shí) 稱為不可壓縮的， 最小描述比原串長度小 C 反過來， 對不可壓縮的串 x。| Winzip|+|| 能描述 Some details need to be sorted out first though… 規(guī)律的描述和輸入 Univ. 可計(jì)算理論 2020/11/17 14/77 ‘ Turing Describable’ ep215 cp141 重復(fù) 17次 01 TM M w 說明可用 Mw的長度來描述信息量 X 的 復(fù)雜度（信息量）為 Min ({ |M|+|w| :: x=M(w), M is TM } ) 例 用 Winzip 壓縮 成為 , 121K Univ. 可計(jì)算理論 2020/11/17 1/77 Lecture Notes for Computation Theory Book :《 計(jì)算理論導(dǎo)引 》 Introduction to the Theory of Computation by Michael Sipser Section 信息的定義 (可考慮部分略講 ) Instructor : 唐常杰 Studen