【導(dǎo)讀】有規(guī)律地重復(fù)01串17次，可壓縮為01#17. 比較復(fù)雜，幾句化說不清的，信息量較大。長話短說的最短尺寸，可用來度量其信息量。Suggests:規(guī)律性使得描述較短

　　

【正文】 ) If answer ―no‖ //描述小，則找下一個詞 then increase s lexicographically。 go to 2) 4) If answer ―yes‖, then print s and halt. The descriptive length of Mn is cM+log(n)… RichardBerry Paradox Theorem: The set C = { x,n | K(x) ? n } is not decidable. Proof by contradiction: Assume C decidable. 程序是合理的 Univ. 可計算理論 2020/11/17 62/77 RichardBerry Formalized 上頁 描述 ―Mn‖的長度為 cM+log(n). 注意 n 比 log(n)增加得快。 n=1024, log(n)=10 所以 n 足夠大時， n cM+log(n). 則描述的長度 Mn 小于 n, 但被他描述的串 s 的復(fù)雜度 K(s) ? n. 小馬拉大車了。 與最小描述的定義矛盾。例如 K(s)=n+1表示 s的最小描述 w為 n+1, 結(jié)論 The set { x,n | K(x) ? n } is not decidable. (But it is coTM recognizable.) Univ. 可計算理論 2020/11/17 63/77 Compression and G246。del (1) 用不可用壓縮定理證明哥德爾不完全定理 自學(xué) The impossibility of calculating K gives a simple way of rephrasing G246。del‘s inpleteness thm. 給定 Th(N,+,?)，設(shè) A是 找出其中完全公理和推導(dǎo)到規(guī)則的 程序（ TM), AAttempt。 反證法，設(shè)是完全的。 由前面結(jié)論，知道小馬不能拉大車。 給定 A長度有限，其描述能力是有上限的，記為 nA （依賴于 A的描述大小 )， 針對 小馬，造大車： A //小馬，描述能力 nA 不能描述下列這些復(fù)雜命題 { x | x =true, K(x) nA } // 大車 Univ. 可計算理論 2020/11/17 64/77 Compression and G246。del (2)自學(xué) 對任意串 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) 問題出在這里，足夠長的命題是不能被枚舉出來的 Univ. 可計算理論 2020/11/17 65/77 Compression and G246。del (3)自學(xué) 1) Enumerate a statements that follows from A 2) If this statement is of the form ―K(x) n‖, then print(x) and stop 3) Otherwise: generate next statement and go to 2) The above program can be expressed with less than 2|A| + 2log(n) + c bits. (The constant c does not depend on A or n.) Also, the program outputs a string x with K(x)n. Contradiction if n 2|A| + 2log(n) + c. 下頁 Univ. 可計算理論 2020/11/17 66/77 Compression and G246。del (4)自學(xué) 比喻 ： 舉重運動員，不能舉起 2*體重＋ 100公斤的重量 程序不能證明 2*size+C的程序 1) Enumerate a statements that follows from A 2) If this statement is of the form ―K(x) nA‖, then print(x) and stop 3) Otherwise: generate next statement and go to 2) Summary: Consider a system of axioms/derivations A. Take an足夠大的 nA with nA 2|A| + 2log(nA) + c. This program of length 2|A| + 2log(nA) + c: would print an x with K(x) 2|A| + 2log(nA) + c. Contradiction: A cannot prove K(x) nA. Univ. 可計算理論 2020/11/17 67/77 Compression and G246。del (5)自學(xué) Summary: Consider a system of axioms/derivations A. Take an nA with nA 2|A| + 2log(nA) + c. With A we cannot prove ―K(x) nA‖ for any x. This is a very strong result: ? For all but 2n+1–1 strings, ―K(x) nA‖ is true. ? The statement ―K(x) nA‖ does not use the content of A at all, only the size |A|. “ You can’t prove a theorem of one kilogram with only one pound of axioms.” Univ. 可計算理論 2020/11/17 68/77 Compression and G246。del (5) 直觀解釋 ： 要證明一個程序 A不死循環(huán)，需要用一個不太小的程序 B 來分析處理它 要求大概 size(B)*2+CSize(A) ？？？） Univ. 可計算理論 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. 可計算理論 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)該是簡單的 If initially we have X, ‘Nature’ will do Y(X). Univ. 可計算理論 2020/11/17 71/77 Occam’s Razor in Physics Nature is pleased with simplicity 自然喜歡簡單 Rule 1 in the Principia, Isaac Newton (1642–1727) 牛頓第一定律， Univ. 可計算理論 2020/11/17 72/77 Physical Laws as Descriptions 一條知識 代替大量的數(shù)據(jù)，本質(zhì)律描述大量觀察事實 Newton‘s laws for the physics of gravity and mechanics give a very short description of a lot of observations. 221|r|mmdtvdGFmF???? Univ. 可計算理論 2020/11/17 73/77 Learning Theory 學(xué)習(xí)理論 X ? Y(X) Assume that there is a TM M inside the box. (The function Y is Turing putable.) Given a (finite) set of observations about Y, we know that certain TMs are impossible, while other TM models M are consistent with our data. How likely do we consider the different models? Kapproach: Probability(TM model M) ? 2–K(M). Univ. 可計算理論 2020/11/17 74/77 Homework 1) Prove with the pigeonhole principle that there are infinitely many natural numbers N ? {0,1,2,…} that have K(N) ? log(N). 2) Let S be a finite set of bitstrings. We know that there is an x?S with K(x) ? log(|S|). But, what can you say about the average K(s)? Prove that for |S|= 2n–1 you have: 2n)x(KSx|S|1 ????Problem and . Univ. 可計算理論 2020/11/17 75/77 Practice Problems 習(xí)題 ep221 cp151 Problem . () Show that there is a constant c such that for all bitstrings x?{0,1}2n, with n zeros and n ones K(x) is smaller than 2n – 189。 log(n) + c. Your proof you should use the indexing trick and Stirling‘s approximation: (Note that this proves that random strings with K(x) ? |x| will never have exactly 50% zeros and 50% ones.) ? ? n2!n nen ?? Univ. 可計算理論 2020/11/17 76/77 小結(jié) Chapter : Definition of Information by Descriptive / Kolmogorov Complexity 若干補充 Inpressible Strings Chapter 6 Arguments by Inpressibility Learning theory Univ. 可計算理論 2020/11/17 77/77 Any Question ? Thank you !!!