【正文】 ts : . 20202020, SCU Style : Lecture / Seminar Univ. 可計(jì)算理論 2020/11/17 2/77 Univ. 可計(jì)算理論 2020/11/17 3/77 Univ. 可計(jì)算理論 2020/11/17 4/77 Univ. 可計(jì)算理論 2020/11/17 5/77 Outline Chapter : Definition of Information by Descriptive / Kolmogorov Complexity 若干補(bǔ)充 Inpressible Strings Chapter 6 Arguments by Inpressibility Learning theory Univ. 可計(jì)算理論 2020/11/17 6/77 Measuring Information ep213 cp 146 Standard information theory considers each n bit string in {0,1}n equal (all have probability 2–n). However, we feel a difference between the string A=“0101010101010101010101010101010101‖ 有規(guī)律地 重復(fù) 01串 17次，可壓縮為 0117 and the string (of equal length) B=“0101110101001010001110001100011011‖. 比較復(fù)雜，幾句化說(shuō)不清的，信息量較大 直觀感覺(jué)： 長(zhǎng)話短說(shuō) 的 最短尺寸，可用來(lái)度量其信息量 Univ. 可計(jì)算理論 2020/11/17 7/77 Measuring Information ep213 cp 140 Standard information theory considers each n bit string in {0,1}n equal (all have probability 2–n). However, we feel a difference between the string A=“0101010101010101010101010101010101‖ 有規(guī)律地 重復(fù) 01串 17次，可壓縮為 0117 and the string (of equal length) B=“0101110101001010001110001100011011‖. 比較復(fù)雜，幾句化說(shuō)不清的，信息量較大 直觀感覺(jué)： 長(zhǎng)話短說(shuō) 的 最短尺寸，可用來(lái)度量其信息量 Univ. 可計(jì)算理論 2020/11/17 8/77 Measuring Information ep213 cp 140 Standard information theory considers each n bit string in {0,1}n equal (all have probability 2–n). However, we feel a difference between the string A=“0101010101010101010101010101010101‖ 有規(guī)律地 重復(fù) 01串 17次，可壓縮為 0117 and the string (of equal length) B=“0101110101001010001110001100011011‖. 比較復(fù)雜的，短話說(shuō)不清的，信息量較大 直觀感覺(jué) ： 表達(dá)語(yǔ)義的 最短尺寸，可用來(lái)度量其信息量 Univ. 可計(jì)算理論 2020/11/17 9/77 Regularity We can give a short description of ―0101010101 010101010101010101010101‖ by ―17 times 01‖. For the other ―01011101010010100011100011 00011011‖ this seems more problematic. Suggests: 規(guī)律性使得描述較短（信息量較小） A regular string is a string that has a short description。| Winzip|+|| 能描述 Some details need to be sorted out first though… 又例：某個(gè)問(wèn)題用億次機(jī)算，最少要用 1個(gè)月 TM M time 規(guī)律的描述和輸入 Univ. 可計(jì)算理論 2020/11/17 15/77 ‘ Turing Describable’ ep215 cp141 重復(fù) 17次 01 TM M w 說(shuō)明可用 Mw的長(zhǎng)度來(lái)描述信息量 X 的 復(fù)雜度（信息量）為 Min ({ |M|+|w| :: x=M(w), M is TM } ) 例 用 Winzip 壓縮 成為 , 121K 描述就不能太小。 1k長(zhǎng)的程序不能描述 windows Univ. 可計(jì)算理論 2020/11/17 39/77 不可壓縮串 ? X是串， c0 , K(x)|x|c, 稱 x是 C可壓縮（長(zhǎng)度壓了 C） ? 反之 不可 c壓縮 , c=1時(shí) 稱為不可壓縮的， 最小描述比原串長(zhǎng)度小 C 反過(guò)來(lái) ， 對(duì)不可壓縮的串 x。（ Win) 升級(jí)軟件要求升級(jí)硬盤。 一個(gè)圖靈機(jī) M ,M 長(zhǎng)度 2020 , 一個(gè)串 w 復(fù)雜度2020,且不可壓縮， M 一定不能描述 W. 適當(dāng)規(guī)定 大小 概念。 符合這一深層次的信息壓縮定理。 ? 編碼 如下頁(yè) k i 1 pilog2 pi 字符 頻率 A1 188。 是分布不均勻度或混亂程度的度量 記為 H(A1,…,A8) 性質(zhì) 0H(x)log2(N) Univ. 可計(jì)算理論 2020/11/17 49/77 Best Splits (Cont.) 補(bǔ)充 熵概念 ? 當(dāng) 8 個(gè)字符均勻分布，每個(gè)字符出現(xiàn)頻率為 1/8, 編碼從000— 111, 平均碼長(zhǎng)為 3 ， H=3 ? (n個(gè)字符，平均為 1/2n , H=n, 可見 n越大，分布越平均， H越大。 ? 自然現(xiàn)象中 耗散型，增加熵的多，作清潔和生命現(xiàn)象使無(wú)序到有序，減少熵（不考慮能量的耗散） Univ. 可計(jì)算理論 2020/11/17 51/77 An Application of KComplexity K復(fù)雜度的應(yīng)用 ep217 Kolmogorov plexity gives a rigorous definition for the notion of order or regularity. 嚴(yán)格描述了階或正則概念 The TM model gives us the most general way of describing mathematical objects like primes, puter programs, or theories. 圖靈機(jī)給出描述數(shù)學(xué)對(duì)象如素?cái)?shù)、程序。log(log(N)) bits. Inpressibility: N 的描述 K(N) ? log(N). Conclusion: 因子數(shù) m ? log(N) / log(log(N)) for those N. （有點(diǎn)意外） Univ. 可計(jì)算理論 2020/11/17 55/77 Careful Counting of Primes 改進(jìn)上頁(yè)結(jié)果 ，更精確一些 . Hence e1,…,e m gives a description of N. For each j we have: ej ? log(N). m21 eme2e1 pppN ???There is an encoding yN with |yN| ? m 比喻： x是 最少 8馬力才能拉的車， 3馬力 一定拉不動(dòng)它 ， 小馬不能拉大車 K can only be approximated ?from above‘. True statements like ―K(x) ? n‖ are recognizable, but not Univ. 可計(jì)算理論 2020/11/17 57/77 (Un)putability of K 自學(xué)或略講 如何估計(jì) X的復(fù)雜度 K(x)? ? K(x) ? n 只對(duì)少數(shù)特殊的串成立，有規(guī)律或結(jié)構(gòu) 如 全 0串， 01交替串，等等， ? 對(duì)于描述 K(x) ? n 的串應(yīng)該證明 較小的圖靈機(jī)的確不能產(chǎn)生它。 n=1024, log(n)=10 所以 n 足夠大時(shí)， n cM+log(n). 則描述的長(zhǎng)度 Mn 小于 n, 但被他描述的串 s 的復(fù)雜度 K(s) ? n. 小馬拉大車了。del‘s inpleteness thm. 給定 Th(N,+,?)，設(shè) A是 找出其中完全公理和推導(dǎo)到規(guī)則的 程序（ TM), AAttempt。del (2)自學(xué) 對(duì)任意串 x,命題 ―K(x) n‖ 可編碼表示，從而是 Th(N,+,?)中的元素 . 下列程序邏輯上是合理的： Consider the following program that uses A and n: 1) 用程序 A枚舉命題 2) If this statement is of the form ―K(x) n‖, then print(x) and halt 3) Otherwise: generate next statement and go to 2) 問(wèn)題出在這里，足夠長(zhǎng)的命題是不能被枚舉出來(lái)的 Univ. 可計(jì)算理論 2020/11/17 65/77 Compression and G246。del (5) 直觀解釋 ： 要證明一個(gè)程序 A不死循環(huán)，需要用一個(gè)不太小的程序 B 來(lái)分析處理它 要求大概 size(B)*2+CSize(A) ？？？） Univ. 可計(jì)算理論 2020/11/17 69/77 Another Application of K If we know a ?shorterthan|x|‘ description of x, then we have certain knowledge about x. 如果關(guān)于 x 的描述比較短， x一定是有某種規(guī)律性的結(jié)構(gòu)，容易描述的結(jié)構(gòu) Kolmogorov plexity gives us a meaningful way of discussing the accumulation of knowledge about objects or data. First approximation: ― Knowledge (M,y) about x‖ is ―|x| – |My|‖. Univ. 可計(jì)算理論 2020/11/17 70/77 A Model of Science 輸入 X Y? 輸出 Y(X) 科學(xué)家想了解 Y: what is inside the box 用 list of Y(0), Y(1), Y(2), … 是 笨描述（如三角函數(shù)表， DB） 描述越短，如 y=sin 表明越接近本質(zhì) , (KB) 核心規(guī)律 應(yīng)該是簡(jiǎn)單的 If initially we have X, ‘Nature’ will do Y(X). Univ. 可計(jì)算理論 2020/11/17 71/77 Occam’s Razor in Physics Nature is pleased with simplicity 自然喜歡簡(jiǎn)單 Rule 1 in the Principia, Isaac Newton (1642–1727)