計算理論10_不可壓縮性

1、W可計算理論2021-12-271/77 Chapter 6.4: Definition of Information by Descriptive / Kolmogorov Complexity若干補(bǔ)充若干補(bǔ)充 Incompressible Strings Chapter 6 Arguments by Incompressibility Learning theoryW可計算理論2021-12-272/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ù)雜，幾句化說不清的，信息量較大直觀感覺：長話短說 的 最短尺寸，可用來度量其信息量W可計算理論2021-12-273/77Standard information theory considers each n bit-str

3、ing 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ù)雜，幾句化說不清的，信息量較大直觀感覺：長話短說 的 最短尺寸，可用來度量其信息量W可計算理論2021-12-274/77Standard

4、information 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ù)雜的，短話說不清的，信息量較大直觀感覺：表達(dá)語義的 最

5、短尺寸，可用來度量其信息量W可計算理論2021-12-275/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 o

6、ne has no such summary.W可計算理論2021-12-276/77We can give a short description of “0101010101010101010101010101010101” by “17 times 01”.For the other “0101110101001010001110001100011011” this seems more problematic.Suggests: 規(guī)律性 使得描述較短（有規(guī)律的，信息量較?。〢 regular string is a string that has a short description

7、; an irregular one has no such summary.W可計算理論2021-12-277/77Problem: What do we consider a description?What may be an obvious description for one, may be illegible for somebody else:3.14.011001001000011111101101010100010001000010110100011000010001101001100010011000110011000101000101110000000110111000

8、001110011010001001010010 We need a proper definition of a description.W可計算理論2021-12-278/77Problem: What do we consider a description?What may be an obvious description for one, may be illegible for somebody else:3.14.01100100100001111110110101010001000100001011010001100001000110100110001001100011001

9、1000101000101110000000110111000001110011010001001010010 We need a proper definition of a description.W可計算理論2021-12-279/77 重復(fù)17次 01 TM M w 說明可用w的長度來描述信息量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

10、規(guī)律的描述和輸入W可計算理論2021-12-2710/77 重復(fù)17次 01 TM M w 說明可用w的長度來描述信息量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又例：某個問題用億次機(jī)算，最少要用1個月 TM M time規(guī)律的描述和輸入W可計算理論2021-12-2711/77 重復(fù)17次 01 TM M w 說明可用w的長度來描述信息量X

11、 的 復(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又例：某個問題用億次計算機(jī)，最少要用1個月 TM M time規(guī)律的描述和輸入壓縮程序復(fù)雜一些，壓縮出來的文件可能小一些W可計算理論2021-12-2712/77We want to express the size of the TM M and y in a number of bits.But h

12、ow 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可計算理論2021-12-2713/77We want to express the size of the TM M and y in a

13、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 , simulatesthe TM M on y (yielding output x).為了一致、公平 地比較，用通用圖靈機(jī) U,模擬M on y int U () return ( M(y) ); How does the encoding work?W可計算理論2021-12-2714/77The description of the TM M

14、 and its input 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可計算理論2021-12-2715/77For the encoding of M

15、 and x we concatenate the self-delimiting/double bit description of M with y.為什么選最小描述? 1. 無最長，2. 較長的不惟一，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可計算理論2021-12-2716/77For the encoding of M and x we concatenate t

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

17、iversal Turing machine 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可計算理論2021-12-2718/77(Fix a universal Turing machine U.)The descriptive complexity K(x) of a string x is the length

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

19、al description: xoutputs y and M on U:yMmin)x(KyMAlso known as: algorithmic complexity, 算術(shù)復(fù)雜度or Kolmogorov (Solomonoff-Chaitin) complexity.W可計算理論2021-12-2720/77The idea of measuring the complexity of bit-stringsby the smallest possible Turing machine that produces the string has been proposed by: 三位

20、研究研究者R. Solomonoff A. KolmogorovB. G. ChaitinW可計算理論2021-12-2721/77R. SolomonoffW可計算理論2021-12-2722/77A. KolmogorovW可計算理論2021-12-2723/77Recall: (Fix a universal Turing machine U.)下面的與定義.20 稍有差別， 等價 xoutputs y and M on U:yMmin)x(KyMProblem: The function K depends on the universalU that is used: we shou

21、ld say KU instead of KMaybe that for another TM V, the complexity measure KV is much smaller than KU?W可計算理論2021-12-2724/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 th

22、at for another TM V, the complexity measure KV is much smaller than KU?K似乎與通用圖靈機(jī)的選擇有關(guān)，下頁證明 即使與U有關(guān)， 也影響不大W可計算理論2021-12-2725/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ī)描述與其它 描述的差別 有界，不會太大、Note that the constant c depends

23、 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ī)來估計復(fù)雜度，只相差一個常數(shù).W可計算理論2021-12-2726/77Theorem 6.21: Let U be a universal TM, thenfor any other description method V, we have KU(x) K

24、V(x) c for all strings x. 同串不同機(jī)的極小描述 相差不會太大、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ī)來估計復(fù)雜度，只相差一個常數(shù).W可計算理論2021-12-2727/77Theorem 6.21: Ther

25、e 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ù)雜度 不會比原文長太多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 o

26、ur way of encoding (M,y).W可計算理論2021-12-2728/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ù)雜度 不會比原文長度 大太多Proof: Let M be the TM that simply outputs itsinput string y: M(y)=y. Then x is a descrip

27、tion of x, and hence K(x) | + |x|. Let c=|.(Here we benefit from our way of encoding (M,y).W可計算理論2021-12-2729/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

28、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可計算理論2021-12-2730/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 t

29、hat given input x:1) Calculate 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可計算理論2021-12-2731/77You would expect that for all strings x and y: K(xy) K(x) + K(y) + c, for some c ？However, this is

30、 not true. 要多花一些代價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)付出的代價，下頁W可計算理論2021-12-2732/77Theorem 6.23(log): There is a c such that K(xy) K(x) + K(y) + 2log(K

31、(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可計算理論2021-12-2733/77Theorem 6.23(log): T

32、here is a c such that K(xy) K(x) + 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

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

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

35、不可壓縮c, c=1時 稱為不可壓縮的， 最小描述比原串長度小C 反過來， 對不可壓縮的串x。描述就不能太小。 一個圖靈機(jī)M , 長度2002 , 一個串 w 復(fù)雜度2003,且不可壓縮， M 一定不能描述 W. 適當(dāng)規(guī)定大小概念。則 小馬 不能拉 大車 這一直觀感覺 在后面有用 許多軟件。增加能力后，EXE的字節(jié)數(shù)增加了。（Win) 升級軟件要求升級硬盤。符合這一深層次的信息壓縮定理。 1k長的程序不能描述windowsW可計算理論2021-12-2737/77Theorem 6.26: For every n there exists at least one incompressible

36、 string x0,1n with K(x)n.存在任意長的不可壓縮串Proof (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

37、 that has a minimal description of at least n bits.長度從1-(n-1)的串比長度為n的串的個數(shù)少W可計算理論2021-12-2738/77Theorem 6.26: For every n there exists at least one incompressible string x0,1n with K(x)n.存在任意長的不可壓縮串Proof (by pigeonhole argument): 用鴿巢原理 There are 2n different strings x in 0,1n.1+2+4+,+ 2n1= 2n1 2n長度從1

38、-(n-1)的串的總數(shù)， 長度為n的串的總數(shù) 目標(biāo) 待壓W可計算理論2021-12-2739/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. 用編號j代替字符串sj ， 就短多了。設(shè)N=2m,N個符號只要編碼成長度為log(N) =m的串Hence K(x) cS + log(N) = cS

39、 + log(|S|), with constant cS depending on the description of S.W可計算理論2021-12-2740/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. 用編號j代替字符串sj ， 就短多了。 例：ASCII用碼代替 字符位圖設(shè)N=

40、2m,N個符號只要編碼成長度為log(N) =m的串1024個串用10位編碼就可區(qū)別了，Hence K(x) cS + log(N) = cS + log(|S|), with constant cS depending on the description of S.W可計算理論2021-12-2741/77Let x 0,1n with 75% zeros and 25% ones.高頻率者用短碼，低頻率用長碼，使得總體碼長較小Consider the set S0,1n of all such strings.The description of S requires c + 2log(

41、n) bits.The size of S is |S| 20.81n.The description 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可計算理論2021-12-2742/77We can compressa bit-string 0,1n,depending on the0/1 distribution. The Shannon entropy of thisdistribu

42、tion (p,1p)gives an upper bound on the K-complexity.W可計算理論2021-12-2743/77n用8=23個字符（a1,.a8)寫密碼信, 需要壓縮編碼，節(jié)約資源n用huffman編碼，編碼長度與使用頻度反比，用得頻繁的碼長短 ，n設(shè) 8 各字符出現(xiàn)的為頻率分布如表。n編碼 如下頁字符頻率A1A2A31/8A41/8A51/16A61/16A71/16A81/16W可計算理論2021-12-2744/77字符頻率編碼碼長計算A1P1=1/4002-Log2(P1)A2P2=1/4 022-Log2(P2)A3P3=1/81003-Log2(P

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

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

45、0111, 平均碼長為3 ，H=3 n(n個字符，平均為1/2n , H=n, 可見n越大，分布越平均，H越大。 情況越混亂， 熵H越大，要表達(dá)它所需要的平均碼長越大，n春秋戰(zhàn)國，等兵力分布時，戰(zhàn)爭多，混亂，熵大，后來逐漸統(tǒng)一，熵變小，信息變小 （戰(zhàn)爭故事也不多，不精彩了）秦統(tǒng)一中國后，國家對立信息的 編碼只要0位即可n直觀感覺：要說清 混亂的事情，比較費(fèi)口舌（費(fèi)信息量）n男生寢室的熵比較大，例如一雙鞋子分居兩地，敘述起來要多說些話，作清潔后 熵變小。n自然現(xiàn)象中 耗散型，增加熵的多，作清潔和生命現(xiàn)象使無序到有序，減少熵（不考慮能量的耗散）W可計算理論2021-12-2747/77Kolmog

46、orov 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é)對象如素數(shù)、程序。理論的一一般模型Together with the incompressibility theorem, this allows us

47、 to make general statements about these objects.再用不可壓縮定理，可得出一些一般的性質(zhì)W可計算理論2021-12-2748/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 t

48、heories. 圖靈機(jī)給出描述數(shù)學(xué)對象如素數(shù)、程序。理論的一一般模型Together with the incompressibility theorem, this allows us to make general statements about these objects.再用不可壓縮定理，可得出一些一般的性質(zhì)W可計算理論2021-12-2749/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:因子分解m21eme2e1pp

49、pNHence gives a description of N.Furthermore, for 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可計算理論2021-12-2750/77Q: How many primes are there less than N?Let p1,pm be the m primes N.We know t

50、hat we can describe N by:m21eme2e1pppNHence gives 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可計算理論2021-12-2751/77 . Hence givesa description of N. For each j we have: ej log(N

51、).m21eme2e1pppNThere is an encoding yN with |yN| mlog(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可計算理論2021-12-2752/77如何估計X的復(fù)雜度 K

52、(x)? K(x) n 只對少數(shù)特殊的串成立，有規(guī)律或結(jié)構(gòu) 如 全0串，01交替串，等等， 對于描述 K(x) n 的串應(yīng)該證明 較小的圖靈機(jī)的確不能產(chǎn)生它。比喻： x是 最少8馬力才能拉的車， 3馬力 一定拉不動它 ， 小馬不能拉大車K can only be approximated from above.True statements like “K(x) n” are recognizable,but not TM-decidable.u W可計算理論2021-12-2753/77如何估計X的復(fù)雜度 K(x)? K(x) n 只對少數(shù)特殊的串成立，有規(guī)律或結(jié)構(gòu) 如 全0串，01交替串，

53、等等， 對于描述 K(x) n 的串應(yīng)該證明 較小的圖靈機(jī)的確不能產(chǎn)生它。比喻： x是 最少8馬力才能拉的車， 3馬力 一定拉不動它 ， 小馬不能拉大車K can only be approximated from above.True statements like “K(x) n” are recognizable,but not TM-decidable.u W可計算理論2021-12-2754/77“The least number that cannot be defined in fewer than twenty words.” 不能用少于不能用少于20個單詞定義的最小的數(shù)（已經(jīng)

54、用個單詞定義的最小的數(shù)（已經(jīng)用12詞說清了）詞說清了） 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)？下頁W可計算理論2021-12-2755/77“The least number that cannot be defined in

55、 fewer than twenty words.” 不能用少于不能用少于20個單詞定義的最小的數(shù)（已經(jīng)用個單詞定義的最小的數(shù)（已經(jīng)用12詞說清了）詞說清了） 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)？下頁W可計算理論2021-1

56、2-2756/77Consider the following TM M (on input n):1) Take s= /空字2) Decide C? /開始應(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.Pr

57、oof by contradiction: Assume C decidable.程序是合理的W可計算理論2021-12-2757/77Consider the following TM M (on input n):1) Take s= /初始化為空字2) Decide C? /開始應(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

58、(n) Richard-Berry Paradox Theorem:The set C = | K(x) n is not decidable.Proof by contradiction: Assume C decidable.程序是合理的W可計算理論2021-12-2758/77 上頁描述 “n”的長度為 cM+log(n). 注意 n 比 log(n)增加得快。n=1024, log(n)=10 所以 n 足夠大時， n cM+log(n). 則描述的長度 n 小于 n, 但被他描述的串s 的復(fù)雜度 K(s) n. 小馬拉大車了。與最小描述的定義矛盾。例如 K(s)=n+1表示s的最小描

59、述w為n+1,結(jié)論 The set | K(x) n is not decidable.(But it is co-TM recognizable.)W可計算理論2021-12-2759/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長度有限，其描述能力是有上限的，記為nA （依賴于 A的描述大小)，

60、 針對 小馬，造大車： A /小馬，描述能力 nA 不能描述下列這些復(fù)雜命題 x | x =true, K(x) nA / 大車W可計算理論2021-12-2760/77對任意串 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 state