計(jì)算理論10_不可壓縮性

1、W可計(jì)算理論2022-5-261/77 Chapter 6.4: Definition of Information by Descriptive / Kolmogorov Complexity若干補(bǔ)充若干補(bǔ)充 Incompressible Strings Chapter 6 Arguments by Incompressibility Learning theoryW可計(jì)算理論2022-5-262/77Standard information theory considers each n bit-string in 0,1n equal (all have probability 2n).

2、However, we feel a difference between the stringA=“0101010101010101010101010101010101”有規(guī)律地 重復(fù)01串 17次，可壓縮為 01#17and the string (of equal length)B=“0101110101001010001110001100011011”.比較復(fù)雜，幾句化說(shuō)不清的，信息量較大直觀感覺(jué)：長(zhǎng)話短說(shuō) 的 最短尺寸，可用來(lái)度量其信息量W可計(jì)算理論2022-5-263/77Standard information theory considers each n bit-string

3、 in 0,1n equal (all have probability 2n).However, we feel a difference between the stringA=“0101010101010101010101010101010101” 有規(guī)律地 重復(fù)01串 17次，可壓縮為 01#17and the string (of equal length)B=“0101110101001010001110001100011011”.比較復(fù)雜，幾句化說(shuō)不清的，信息量較大直觀感覺(jué)：長(zhǎng)話短說(shuō) 的 最短尺寸，可用來(lái)度量其信息量W可計(jì)算理論2022-5-264/77Standard info

4、rmation theory considers each n bit-string in 0,1n equal (all have probability 2n).However, we feel a difference between the stringA=“0101010101010101010101010101010101”有規(guī)律地 重復(fù)01串 17次，可壓縮為 01#17and the string (of equal length)B=“0101110101001010001110001100011011”. 比較復(fù)雜的，短話說(shuō)不清的，信息量較大直觀感覺(jué)：表達(dá)語(yǔ)義的 最短尺寸，

5、可用來(lái)度量其信息量W可計(jì)算理論2022-5-265/77We can give a short description of “0101010101010101010101010101010101” by “17 times 01”.For the other “0101110101001010001110001100011011” this seems more problematic.Suggests: 規(guī)律性使得描述較短（信息量較?。〢 regular string is a string that has a short description; an irregular one ha

6、s no such summary.W可計(jì)算理論2022-5-266/77We can give a short description of “0101010101010101010101010101010101” by “17 times 01”.For the other “0101110101001010001110001100011011” this seems more problematic.Suggests: 規(guī)律性 使得描述較短（有規(guī)律的，信息量較小）A regular string is a string that has a short description; an i

7、rregular one has no such summary.W可計(jì)算理論2022-5-267/77Problem: What do we consider a description?What may be an obvious description for one, may be illegible for somebody else:3.14.0110010010000111111011010101000100010000101101000110000100011010011000100110001100110001010001011100000001101110000011100

8、11010001001010010 We need a proper definition of a description.W可計(jì)算理論2022-5-268/77Problem: What do we consider a description?What may be an obvious description for one, may be illegible for somebody else:3.14.0110010010000111111011010101000100010000101101000110000100011010011000100110001100110001010

9、00101110000000110111000001110011010001001010010 We need a proper definition of a description.W可計(jì)算理論2022-5-269/77 重復(fù)17次 01 TM M w 說(shuō)明可用w的長(zhǎng)度來(lái)描述信息量X 的復(fù)雜度（信息量）為 Min ( |+|w| : x=M(w), M is TM )例 用Winzip 壓縮A.doc 成為A.zip , 121K | |+|A.zip| 能描述Z.Doc的復(fù)雜度Some details need to be sorted out first though規(guī)律的描述和輸入W

10、可計(jì)算理論2022-5-2610/77 重復(fù)17次 01 TM M w 說(shuō)明可用w的長(zhǎng)度來(lái)描述信息量X 的 復(fù)雜度（信息量）為 Min ( |+|w| : x=M(w), M is TM )例 用Winzip 壓縮A.doc 成為A.zip , 121K | |+|A.zip| 能描述Z.Doc的復(fù)雜度Some details need to be sorted out first though又例：某個(gè)問(wèn)題用億次機(jī)算，最少要用1個(gè)月 TM M time規(guī)律的描述和輸入W可計(jì)算理論2022-5-2611/77 重復(fù)17次 01 TM M w 說(shuō)明可用w的長(zhǎng)度來(lái)描述信息量X 的 復(fù)雜度（信息量）

11、為 Min ( |+|w| : x=M(w), M is TM )例 用Winzip 壓縮A.doc 成為A.zip , 121K | |+|A.zip| 能描述Z.Doc的復(fù)雜度Some details need to be sorted out first though又例：某個(gè)問(wèn)題用億次計(jì)算機(jī)，最少要用1個(gè)月 TM M time規(guī)律的描述和輸入壓縮程序復(fù)雜一些，壓縮出來(lái)的文件可能小一些W可計(jì)算理論2022-5-2612/77We want to express the size of the TM M and y in a number of bits.But how many bits

12、 is a specific (M,y) pair?Other key idea: We fix a universal Turing machine U that,on input , simulatesthe TM M on y (yielding output x).為了一致地比較，用通用圖靈機(jī) U,模擬M on y int U () return ( M(y) ); How does the encoding work?W可計(jì)算理論2022-5-2613/77We want to express the size of the TM M and y in a number of bit

13、s.But how many bits is a specific (M,y) pair?Other key idea: We fix a universal Turing machine U that,on input , simulatesthe TM M on y (yielding output x).為了一致、公平 地比較，用通用圖靈機(jī) U,模擬M on y int U () return ( M(y) ); How does the encoding work?W可計(jì)算理論2022-5-2614/77The description of the TM M and its input

14、 y isgoing to be one long bit-string:_10101010011 yinput Mmachine Turing How do we know where stops and starts?We will use a self-delimiting code for : two bits “00” for zero, two bits “11” for one, and “01” for end of string. 相當(dāng)于編碼為4進(jìn)位，M 分隔符 wW可計(jì)算理論2022-5-2615/77For the encoding of M and x we conca

15、tenate the self-delimiting/double bit description of M with y.為什么選最小描述? 1. 無(wú)最長(zhǎng)，2. 較長(zhǎng)的不惟一，3. 最短的是唯一的Hence from now on: = y.For the length of this implies: | = | + |y|Note that the y0,1* is encoded trivially.如果 M 變化，則標(biāo)準(zhǔn)不統(tǒng)一W可計(jì)算理論2022-5-2616/77For the encoding of M and x we concatenate the self-delimiti

16、ng/double bit description of M with y.為什么選極小描述? (1). 無(wú)最長(zhǎng)描述，(2). 較長(zhǎng)的不惟一，(3). 最短的是唯一的有一個(gè)公理（策默駱）自然數(shù)的子集中必有最小數(shù)Hence from now on: = y.For the length of this implies: | = | + |y| 直觀解釋： 解碼機(jī)長(zhǎng) 密碼長(zhǎng) =復(fù)雜度， Note that the y0,1* is encoded trivially.如果 M 變化，則用于比較的標(biāo)準(zhǔn) 不統(tǒng)一W可計(jì)算理論2022-5-2617/77(Fix a universal Turing ma

17、chine U.) （例如固定為WinZip.exe)The minimal description d(x) is the shorteststring y such that U on y outputs x.用|d(x)| 描述X的復(fù)雜度The length |d(x)| will be the complexity of xW可計(jì)算理論2022-5-2618/77(Fix a universal Turing machine U.)The descriptive complexity K(x) of a string x is the length |d(x)| of its mini

18、mal description:最小的描述長(zhǎng)度 xoutputs y and M on U:yMmin)x(KyMAlso known as: algorithmic complexity, 算術(shù)復(fù)雜度or Kolmogorov (Solomonoff-Chaitin) complexity.W可計(jì)算理論2022-5-2619/77(Fix a universal Turing machine U.)The descriptive complexity K(x) of a string x is the length |d(x)| of its minimal description: xou

19、tputs y and M on U:yMmin)x(KyMAlso known as: algorithmic complexity, 算術(shù)復(fù)雜度or Kolmogorov (Solomonoff-Chaitin) complexity.W可計(jì)算理論2022-5-2620/77The idea of measuring the complexity of bit-stringsby the smallest possible Turing machine that produces the string has been proposed by: 三位研究研究者R. Solomonoff A

20、. KolmogorovB. G. ChaitinW可計(jì)算理論2022-5-2621/77R. SolomonoffW可計(jì)算理論2022-5-2622/77A. KolmogorovW可計(jì)算理論2022-5-2623/77Recall: (Fix a universal Turing machine U.)下面的與定義.20 稍有差別， 等價(jià) xoutputs y and M on U:yMmin)x(KyMProblem: The function K depends on the universalU that is used: we should say KU instead of KM

21、aybe that for another TM V, the complexity measure KV is much smaller than KU?W可計(jì)算理論2022-5-2624/77Recall: (Fix a universal Turing machine U.) xoutputs y and M on U:yMmin)x(KyMProblem: The function K depends on the universalU that is used: we should say KU instead of KMaybe that for another TM V, the

22、 complexity measure KV is much smaller than KU?K似乎與通用圖靈機(jī)的選擇有關(guān)，下頁(yè)證明 即使與U有關(guān)， 也影響不大W可計(jì)算理論2022-5-2625/77Theorem 6.21: Let U be a universal TM, thenfor 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

23、. 且差值與x 無(wú)關(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ī)來(lái)估計(jì)復(fù)雜度，只相差一個(gè)常數(shù).W可計(jì)算理論2022-5-2626/77Theorem 6.21: Let U be a universal TM, thenfor any other description method V, we have KU(x) KV(x) c for all strings x.

24、同串不同機(jī)的極小描述 相差不會(huì)太大、Note that the constant c depends on V and U, but not on x. 且差值與x 無(wú)關(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ī)來(lái)估計(jì)復(fù)雜度，只相差一個(gè)常數(shù).W可計(jì)算理論2022-5-2627/77Theorem 6.21: There exists a constant c, such

25、that K(x) |x| + c, for every x. (“The complexity ofa string can never be much bigger than its length.”) 串的復(fù)雜度 不會(huì)比原文長(zhǎng)太多Proof: Let M be the TM that simply outputs itsinput string y: M(y)=y. Then x is a description of x, and hence K(x) | + |x|. Let c=|.(Here we benefit from our way of encoding (M,y).W可

26、計(jì)算理論2022-5-2628/77Theorem .21: There exists a constant c, suchthat K(x) |x| + c, for every x. (“The complexity ofa string can never be much bigger than its length.”) 串的復(fù)雜度 不會(huì)比原文長(zhǎng)度 大太多Proof: Let M be the TM that simply outputs itsinput string y: M(y)=y. Then x is a description of x, and hence K(x) |

27、+ |x|. Let c=|.(Here we benefit from our way of encoding (M,y).W可計(jì)算理論2022-5-2629/77Theorem C6.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 x:1) Calculate the output s of N on x2) Output ssLet d(x) be the minimum des

28、cription of x,then d(x) will give a description of xx.Hence, K(xx) | + |d(x)| = K(x) + c.W可計(jì)算理論2022-5-2630/77Theorem 6.22: 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 x:1) Calculate

29、 the output s of N on x2) Output ssLet d(x) be the minimum description of x,then d(x) will give a description of xx.Hence, K(xx) | + |d(x)| = K(x) + c.W可計(jì)算理論2022-5-2631/77You 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 l

30、ies 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的編碼長(zhǎng)度的2倍為l 描述X,Y的分割點(diǎn)付出的代價(jià)，下頁(yè)W可計(jì)算理論2022-5-2632/77Theorem 6.23(log): There is a c such that K(xy) K(x) + K(y) + 2log(K(x) + c, for all x,y.自學(xué)（不難，意義較?。?/p>

31、Proof: Let m be the logarithm of |d(x)|, then thestring “1m0 d(x)” gives a self-delimitin description of x.(We need 2m bits to indicate the length of d(x).)Hence the input “1m0 d(x) d(y)” gives an unambiguous description of xy.W可計(jì)算理論2022-5-2633/77Theorem 6.23(log): There is a c such that K(xy) K(x)

32、+ K(y) + 2log(K(x) + c, for all x,y.自學(xué)（不難，意義較?。㏄roof: Let m be the logarithm of |d(x)|, then thestring “1m0 d(x)” gives a self-delimitin description of x.(We need 2m bits to indicate the length of d(x).)Hence the input “1m0 d(x) d(y)” gives an unambiguous description of xy.W可計(jì)算理論2022-5-2634/77nX是串，

33、c0 , K(x)|x|-c, 稱x是C-可壓縮（長(zhǎng)度壓了C）n反之 不可c壓縮, c=1時(shí) 稱為不可壓縮的， 最小描述比原串長(zhǎng)度小C 反過(guò)來(lái)， 對(duì)不可壓縮的串x。描述就不能太小。 一個(gè)圖靈機(jī)M , 長(zhǎng)度2002 , 一個(gè)串 w 復(fù)雜度2003,且不可壓縮， M 一定不能描述 W. 我們稱為 小馬 拉 大車 這一直觀感覺(jué) 在后面有用 許多軟件。增加能力，增加EXE的字節(jié)數(shù)（Win) 升級(jí)軟件要求升級(jí)硬盤。符合這一深層次的信息壓縮定理。 1k長(zhǎng)的程序不能描述windowsW可計(jì)算理論2022-5-2635/77nX是串， c0 , K(x)|x|-c, 稱x是C-可壓縮（長(zhǎng)度壓了C）n反之 不可

34、c壓縮, c=1時(shí) 稱為不可壓縮的， 最小描述比原串長(zhǎng)度小C 反過(guò)來(lái)， 對(duì)不可壓縮的串x。描述就不能太小。 一個(gè)圖靈機(jī)M , 長(zhǎng)度2002 , 一個(gè)串 w 復(fù)雜度2003,且不可壓縮， M 一定不能描述 W. 我們稱為 小馬 拉 大車 這一直觀感覺(jué) 在后面有用 許多軟件。增加能力后，EXE的字節(jié)數(shù)增加了。（Win) 升級(jí)軟件要求升級(jí)硬盤。符合這一深層次的信息壓縮定理。 1k長(zhǎng)的程序不能描述windowsW可計(jì)算理論2022-5-2636/77nX是串， c0 , K(x)|x|-c, 稱x是C-可壓縮（長(zhǎng)度壓了C）n反之 不可壓縮c, c=1時(shí) 稱為不可壓縮的， 最小描述比原串長(zhǎng)度小C 反過(guò)來(lái)

35、， 對(duì)不可壓縮的串x。描述就不能太小。 一個(gè)圖靈機(jī)M , 長(zhǎng)度2002 , 一個(gè)串 w 復(fù)雜度2003,且不可壓縮， M 一定不能描述 W. 適當(dāng)規(guī)定大小概念。則 小馬 不能拉 大車 這一直觀感覺(jué) 在后面有用 許多軟件。增加能力后，EXE的字節(jié)數(shù)增加了。（Win) 升級(jí)軟件要求升級(jí)硬盤。符合這一深層次的信息壓縮定理。 1k長(zhǎng)的程序不能描述windowsW可計(jì)算理論2022-5-2637/77Theorem 6.26: For every n there exists at least one incompressible string x0,1n with K(x)n.存在任意長(zhǎng)的不可壓縮串P

36、roof (by pigeonhole argument): 用鴿巢原理 There are 2n different strings x in 0,1n. There is one description of length 0, twodescriptions of length 1, and 2n1 descriptionsof length n1. In total: 2n1 descriptions of length smaller than n.Hence, there has to be an x0,1n that has a minimal description of at

37、 least n bits.長(zhǎng)度從1-(n-1)的串比長(zhǎng)度為n的串的個(gè)數(shù)少W可計(jì)算理論2022-5-2638/77Theorem 6.26: For every n there exists at least one incompressible string x0,1n with K(x)n.存在任意長(zhǎng)的不可壓縮串Proof (by pigeonhole argument): 用鴿巢原理 There are 2n different strings x in 0,1n.1+2+4+,+ 2n1= 2n1 2n長(zhǎng)度從1-(n-1)的串的總數(shù)， 長(zhǎng)度為n的串的總數(shù) 目標(biāo) 待壓W可計(jì)算理論2022

38、-5-2639/77Compression idea: If S is a small set that is easyto describe, then we can describe an xS by: index of x in SLet S = s1,sN. We can indicate every xS by the 1jN such that sj=x. 用編號(hào)j代替字符串sj ， 就短多了。設(shè)N=2m,N個(gè)符號(hào)只要編碼成長(zhǎng)度為log(N) =m的串Hence K(x) cS + log(N) = cS + log(|S|), with constant cS depending

39、 on the description of S.W可計(jì)算理論2022-5-2640/77Compression idea: If S is a small set that is easyto describe, then we can describe an xS by: index of x in SLet S = s1,sN. We can indicate every xS by the 1jN such that sj=x. 用編號(hào)j代替字符串sj ， 就短多了。 例：ASCII用碼代替 字符位圖設(shè)N=2m,N個(gè)符號(hào)只要編碼成長(zhǎng)度為log(N) =m的串1024個(gè)串用10位編碼就可

40、區(qū)別了，Hence K(x) cS + log(N) = cS + log(|S|), with constant cS depending on the description of S.W可計(jì)算理論2022-5-2641/77Let x 0,1n with 75% zeros and 25% ones.高頻率者用短碼，低頻率用長(zhǎng)碼，使得總體碼長(zhǎng)較小Consider the set S0,1n of all such strings.The description of S requires c + 2log(n) bits.The size of S is |S| 20.81n.The d

41、escription of x requires no more than c + 2log(n) + log(|S|) = c + 2log(n) + 0.81n bits.For large enough n: K(x) 0.81n (approximately). W可計(jì)算理論2022-5-2642/77We can compressa bit-string 0,1n,depending on the0/1 distribution. The Shannon entropy of thisdistribution (p,1p)gives an upper bound on the K-c

42、omplexity.W可計(jì)算理論2022-5-2643/77n用8=23個(gè)字符（a1,.a8)寫密碼信, 需要壓縮編碼，節(jié)約資源n用huffman編碼，編碼長(zhǎng)度與使用頻度反比，用得頻繁的碼長(zhǎng)短 ，n設(shè) 8 各字符出現(xiàn)的為頻率分布如表。n編碼 如下頁(yè)字符頻率A1A2A31/8A41/8A51/16A61/16A71/16A81/16W可計(jì)算理論2022-5-2644/77字符頻率編碼碼長(zhǎng)計(jì)算A1P1=1/4002-Log2(P1)A2P2=1/4 022-Log2(P2)A3P3=1/81003-Log2(P3)A4P4=1/8 1013-Log2(P4)A5P5=1/1610014-Log2(

43、P5)A6P6=1/1610104-Log2(P6)A7P7=1/1610114-Log2(P7)A8P8=1/1611004-Log2(P8)最小平均碼長(zhǎng) （加權(quán)平均）長(zhǎng)度越大 加權(quán)越小= - Pi log2(Pi) = 2.75 bit用它作為信息量的度量是合理的。稱為 熵。是分布不均勻度或混亂程度的度量記為H(A1,A8)性質(zhì)0H(x)log2(N)W可計(jì)算理論2022-5-2645/77n當(dāng)8 個(gè)字符均勻分布，每個(gè)字符出現(xiàn)頻率為1/8, 編碼從000111, 平均碼長(zhǎng)為3 ，H=3 n(n個(gè)字符，平均為1/2n , H=n, 可見(jiàn)n越大，分布越平均，H越大。 情況越混亂， 熵H越大，要

44、表達(dá)它所需要的平均碼長(zhǎng)越大，n春秋戰(zhàn)國(guó)，等兵力分布時(shí)，戰(zhàn)爭(zhēng)多，混亂，熵大，后來(lái)逐漸統(tǒng)一，熵變小，信息變小 （戰(zhàn)爭(zhēng)故事也不多，不精彩了）秦統(tǒng)一中國(guó)后，國(guó)家對(duì)立信息的 編碼只要0位即可n直觀感覺(jué)：要說(shuō)清 混亂的事情，比較費(fèi)口舌（費(fèi)信息量）n男生寢室的熵比較大，例如一雙鞋子分居兩地，敘述起來(lái)要多說(shuō)些話，作清潔后 熵變小。n自然現(xiàn)象中 耗散型，增加熵的多，作清潔和生命現(xiàn)象使無(wú)序到有序，減少熵（不考慮能量的耗散）W可計(jì)算理論2022-5-2646/77n當(dāng)8 個(gè)字符均勻分布，每個(gè)字符出現(xiàn)頻率為1/8, 編碼從000111, 平均碼長(zhǎng)為3 ，H=3 n(n個(gè)字符，平均為1/2n , H=n, 可見(jiàn)n越大，

45、分布越平均，H越大。 情況越混亂， 熵H越大，要表達(dá)它所需要的平均碼長(zhǎng)越大，n春秋戰(zhàn)國(guó)，等兵力分布時(shí)，戰(zhàn)爭(zhēng)多，混亂，熵大，后來(lái)逐漸統(tǒng)一，熵變小，信息變小 （戰(zhàn)爭(zhēng)故事也不多，不精彩了）秦統(tǒng)一中國(guó)后，國(guó)家對(duì)立信息的 編碼只要0位即可n直觀感覺(jué)：要說(shuō)清 混亂的事情，比較費(fèi)口舌（費(fèi)信息量）n男生寢室的熵比較大，例如一雙鞋子分居兩地，敘述起來(lái)要多說(shuō)些話，作清潔后 熵變小。n自然現(xiàn)象中 耗散型，增加熵的多，作清潔和生命現(xiàn)象使無(wú)序到有序，減少熵（不考慮能量的耗散）W可計(jì)算理論2022-5-2647/77Kolmogorov complexity gives a rigorousdefinition for

46、the notion of order or regularity.嚴(yán)格描述了階或正則概念The TM model gives us the most general way of describing mathematical objects like primes, computer programs, or theories. 圖靈機(jī)給出描述數(shù)學(xué)對(duì)象如素?cái)?shù)、程序。理論的一一般模型Together with the incompressibility theorem, this allows us to make general statements about these objects

47、.再用不可壓縮定理，可得出一些一般的性質(zhì)W可計(jì)算理論2022-5-2648/77Kolmogorov complexity gives a rigorousdefinition for the notion of order or regularity.嚴(yán)格描述了階或正則概念The TM model gives us the most general way of describing mathematical objects like primes, computer programs, or theories. 圖靈機(jī)給出描述數(shù)學(xué)對(duì)象如素?cái)?shù)、程序。理論的一一般模型Together with

48、 the incompressibility theorem, this allows us to make general statements about these objects.再用不可壓縮定理，可得出一些一般的性質(zhì)W可計(jì)算理論2022-5-2649/77Q: How many primes are there less than N?Let p1,pm be the m primes N.We know that we can describe N by:因子分解m21eme2e1pppNHence gives a description of N.Furthermore, for

49、 each j we have: ej log(N).Thus requires mlog(log(N) bits.Incompressibility: There are N with K(N) log(N).Conclusion: m log(N) / log(log(N) for those N.W可計(jì)算理論2022-5-2650/77Q: How many primes are there less than N?Let p1,pm be the m primes N.We know that we can describe N by:m21eme2e1pppNHence gives

50、a description of N.注意：2=Pj 2ej N ej log(N).Thus requires mlog(log(N) bits.Incompressibility: N 的描述 K(N) log(N).Conclusion: 因子數(shù)m log(N) / log(log(N) for those N. （有點(diǎn)意外）W可計(jì)算理論2022-5-2651/77 . Hence givesa description of N. For each j we have: ej log(N).m21eme2e1pppNThere is an encoding yN with |yN| ml

51、og(log(N). The total description yN requires no more thanc + mlog(log(N) bits.For N with K(N) log(N), we thus have the bound:log(N) mlog(log(N) + c, which implies m log(N)/log(log(N) c/log(log(N) for arbitrary big N. W可計(jì)算理論2022-5-2652/77如何估計(jì)X的復(fù)雜度 K(x)? K(x) n 只對(duì)少數(shù)特殊的串成立，有規(guī)律或結(jié)構(gòu) 如 全0串，01交替串，等等， 對(duì)于描述 K

52、(x) n 的串應(yīng)該證明 較小的圖靈機(jī)的確不能產(chǎn)生它。比喻： x是 最少8馬力才能拉的車， 3馬力 一定拉不動(dòng)它 ， 小馬不能拉大車K can only be approximated from above.True statements like “K(x) n” are recognizable,but not TM-decidable.u W可計(jì)算理論2022-5-2653/77如何估計(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)生它。比喻： x是 最少8馬力才能拉的

53、車， 3馬力 一定拉不動(dòng)它 ， 小馬不能拉大車K can only be approximated from above.True statements like “K(x) n” are recognizable,but not TM-decidable.u W可計(jì)算理論2022-5-2654/77“The least number that cannot be defined in fewer than twenty words.” 不能用少于不能用少于20個(gè)單詞定義的最小的數(shù)（已經(jīng)用個(gè)單詞定義的最小的數(shù)（已經(jīng)用12詞說(shuō)清了）詞說(shuō)清了） N | K(N)20 By formalizing

54、this paradox we will see that theproblem lies in recognizing that a numbercannot be described in fewer than 20 words.(There is no problem with formalizing “defined”.)悖論是否與不可判定性 有關(guān)？下頁(yè)W可計(jì)算理論2022-5-2655/77“The least number that cannot be defined in fewer than twenty words.” 不能用少于不能用少于20個(gè)單詞定義的最小的數(shù)（已經(jīng)用個(gè)單

55、詞定義的最小的數(shù)（已經(jīng)用12詞說(shuō)清了）詞說(shuō)清了） N | K(N)20 By formalizing this paradox we will see that theproblem lies in recognizing that a numbercannot be described in fewer than 20 words.(There is no problem with formalizing “defined”.)悖論是否與不可判定性 有關(guān)？下頁(yè)W可計(jì)算理論2022-5-2656/77Consider the following TM M (on input n):1) Tak

56、e s= /空字2) Decide C? /開(kāi)始應(yīng)該為no3) If answer “no”, then increase s lexicographically; go to 2)4) If answer “yes”, then print s and halt.The descriptive length of n is cM+log(n) Richard-Berry Paradox Theorem:The set C = | K(x) n is not decidable.Proof by contradiction: Assume C decidable.程序是合理的W可計(jì)算理論202

57、2-5-2657/77Consider the following TM M (on input n):1) Take s= /初始化為空字2) Decide C? /開(kāi)始應(yīng)該為no3) If answer “no” /描述小，則找下一個(gè)詞 then increase s lexicographically; go to 2)4) If answer “yes”, then print s and halt.The descriptive length of n is cM+log(n) Richard-Berry Paradox Theorem:The set C = | K(x) n is

58、 not decidable.Proof by contradiction: Assume C decidable.程序是合理的W可計(jì)算理論2022-5-2658/77 上頁(yè)描述 “n”的長(zhǎng)度為 cM+log(n). 注意 n 比 log(n)增加得快。n=1024, log(n)=10 所以 n 足夠大時(shí)， n cM+log(n). 則描述的長(zhǎng)度 n 小于 n, 但被他描述的串s 的復(fù)雜度 K(s) n. 小馬拉大車了。與最小描述的定義矛盾。例如 K(s)=n+1表示s的最小描述w為n+1,結(jié)論 The set | K(x) n is not decidable.(But it is co-

59、TM recognizable.)W可計(jì)算理論2022-5-2659/77The impossibility of calculating K gives a simpleway of rephrasing Gdels incompleteness thm.給定Th(N,+,)，設(shè)A是找出其中完全公理和推導(dǎo)到規(guī)則的程序（TM), A-Attempt。反證法，設(shè)是完全的。 由前面結(jié)論，知道小馬不能拉大車。 給定A長(zhǎng)度有限，其描述能力是有上限的，記為nA （依賴于 A的描述大小)， 針對(duì) 小馬，造大車： A /小馬，描述能力 nA 不能描述下列這些復(fù)雜命題 x | x =true, K(x) nA

60、 / 大車W可計(jì)算理論2022-5-2660/77對(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 halt3) Otherwise: generate next statement and go to 2)問(wèn)題出在這里，足夠長(zhǎng)的命題是不能被枚舉出來(lái)的W可計(jì)算理論2022-5-2661/771