【正文】 11000001110011010001001010010… ? We need a proper definition of ?a description‘. Univ. 可計(jì)算理論 2020/11/17 13/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 an irregular one has no such summary. Univ. 可計(jì)算理論 2020/11/17 10/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ī)律性 使得描述較短（有規(guī)律的，信息量較?。? A regular string is a string that has a short description。| Winzip|+|| 能描述 Some details need to be sorted out first though… 又例：某個(gè)問題用億次機(jī)算，最少要用 1個(gè)月 TM M time 規(guī)律的描述和輸入 壓縮程序復(fù)雜一些， ?壓縮出來的文件可能小一些 Univ. 可計(jì)算理論 2020/11/17 16/77 Measuring the size of (M,y) We want to express the size of the TM M and y in a number of bits. But how many bits is a specific (M,y) pair? Other key idea: We fix a universal Turing machine U that,on input M,y, simulates the TM M on y (yielding output x). 為了一致地比較，用通用圖靈機(jī) U,模擬 M on y int U (M,y) { return ( M(y) )。 一個(gè)圖靈機(jī) M ,M 長度 2020 , 一個(gè)串 w 復(fù)雜度2020,且不可壓縮， M 一定不能描述 W. 我們稱為 小馬 拉 大車 這一直觀感覺 在后面有用 許多軟件。描述就不能太小。符合這一深層次的信息壓縮定理。則 小馬 不能拉 大車 這一直觀感覺 在后面有用 許多軟件。 1k長的程序不能描述 windows Univ. 可計(jì)算理論 2020/11/17 41/77 Inpressibility 不可壓縮的串 ep217,cp149 Theorem : For every n there exists at least one inpressible string x?{0,1}n with K(x)?n. 存在任意長的不可壓縮串 Proof (by pigeonhole argument): 用 鴿巢原理 – There are 2n different strings x in {0,1}n. – There is one description of length 0, two descriptions of length 1,…, and 2 n–1 descriptions of length n–1. In total: 2n–1 descriptions of length smaller than , there has to be an x?{0,1}n that has a minimal description of at least n bits. 長度從 1(n1)的串比長度為 n的串的個(gè)數(shù)少 Univ. 可計(jì)算理論 2020/11/17 42/77 Inpressibility 不可壓縮的串 ep217,cp149 Theorem : For every n there exists at least one inpressible string x?{0,1}n with K(x)?n. 存在任意長的不可壓縮串 Proof (by pigeonhole argument): 用 鴿巢原理 – There are 2n different strings x in {0,1}n. 1+2+4+…,+ 2 n–1= 2n–1 2n 長度從 1(n1)的串的總數(shù) ， 長度為 n的串的總數(shù) 目標(biāo) 待壓 Univ. 可計(jì)算理論 2020/11/17 43/77 Indexing Trick Compression idea: If S is a small set that is easy to describe, then we can describe an x?S by: description of enumeration of S index of x in S Let S = {s1,…,s N}. We can indicate every x?S by the 1?j?N such that sj=x. 用編號 j代替字符串 sj ， 就短多了。 A2 188。 情況越混亂， 熵 H越大，要表達(dá)它所需要的平均碼長越大， ? 春秋戰(zhàn)國，等兵力分布時(shí)，戰(zhàn)爭多，混亂，熵大，后來逐漸統(tǒng)一，熵變小，信息變小 （戰(zhàn)爭故事也不多，不精彩了）秦統(tǒng)一中國后，國家對立信息的 編碼只要 0位即可 ? 直觀感覺：要說清 混亂的事情，比較費(fèi)口舌（費(fèi)信息量） ? 男生寢室的熵比較大，例如一雙鞋子分居兩地，敘述起來要多說些話，作清潔后 熵變小。理論的一一般模型 Together with the inpressibility theorem, this allows us to make general statements about these ，可得出一些一般的性質(zhì) Univ. 可計(jì)算理論 2020/11/17 52/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é)對象如素?cái)?shù)、程序。log(log(N)). The total description MyN requires no more than c + m 比喻 ： x是 最少 8馬力才能拉的車， 3馬力 一定拉不動它 ， 小馬不能拉大車 K can only be approximated ?from above‘. True statements like ―K(x) ? n‖ are recognizable, but not Univ. 可計(jì)算理論 2020/11/17 58/77 RichardBerry Paradox “ The least number that cannot be defined in fewer than twenty words.” 不能用少于 20個(gè)單詞定義的最小的數(shù)（已經(jīng)用 12詞說清了） { N | K(N)20} By formalizing this paradox we will see that the problem lies in recognizing that a number cannot be described in fewer than 20 words. (There is no problem with formalizing ―defined‖.) 悖論是否與不可判定性 有關(guān)？下頁 Univ. 可計(jì)算理論 2020/11/17 59/77 RichardBerry Paradox “ The least number that cannot be defined in fewer than twenty words.” 不能用少于 20個(gè)單詞定義的最小的數(shù)（已經(jīng)用 12詞說清了） { N | K(N)20} By formalizing this paradox we will see that the problem lies in recognizing that a number cannot be described in fewer than 20 words. (There is no problem with formalizing ―defined‖.) 悖論是否與不可判定性 有關(guān)？下頁 Univ. 可計(jì)算理論 2020/11/17 60/77 RichardBerry Formalized Consider the following TM M (on input n): 1) Take s=? //空字 2) Decide s,n ? C? //開始應(yīng)該為 no 3) If answer ―no‖, then increase s lexicographically。 與最小描述的定義矛盾。 反證法，設(shè)是完全的。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. 可計(jì)算理論 2020/11/17 66/77 Compression and G246。 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. 可計(jì)算理論 2020/11/17 76/77 小結(jié) Chapter : Definition of Information by Descriptive / Kolmogorov Complexity 若干補(bǔ)充 Inpressible Strings Chapter 6 Arguments by Inpressibility Learning theory Univ. 可計(jì)算理論 2020/11/17 77/77 Any Question ? Thank you !!!