計算理論10_不可壓縮性

1、W可計算理論2022-5-261/77 Chapter 6.4: Definition of Information by Descriptive / Kolmogorov Complexity若干補充若干補充 Incompressible Strings Chapter 6 Arguments by Incompressibility Learning theoryW可計算理論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ù)雜，幾句化說不清的，信息量較大直觀感覺：長話短說 的 最短尺寸，可用來度量其信息量W可計算理論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ù)雜，幾句化說不清的，信息量較大直觀感覺：長話短說 的 最短尺寸，可用來度量其信息量W可計算理論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ù)雜的，短話說不清的，信息量較大直觀感覺：表達語義的 最短尺寸，

5、可用來度量其信息量W可計算理論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可計算理論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ī)律的，信息量較?。〢 regular string is a string that has a short description; an i

7、rregular one has no such summary.W可計算理論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可計算理論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可計算理論2022-5-269/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規(guī)律的描述和輸入W

10、可計算理論2022-5-2610/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又例：某個問題用億次機算，最少要用1個月 TM M time規(guī)律的描述和輸入W可計算理論2022-5-2611/77 重復(fù)17次 01 TM M w 說明可用w的長度來描述信息量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又例：某個問題用億次計算機，最少要用1個月 TM M time規(guī)律的描述和輸入壓縮程序復(fù)雜一些，壓縮出來的文件可能小一些W可計算理論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).為了一致地比較，用通用圖靈機 U,模擬M on y int U () return ( M(y) ); How does the encoding work?W可計算理論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).為了一致、公平 地比較，用通用圖靈機 U,模擬M on y int U () return ( M(y) ); How does the encoding work?W可計算理論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進位，M 分隔符 wW可計算理論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. 無最長，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可計算理論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). 無最長描述，(2). 較長的不惟一，(3). 最短的是唯一的有一個公理（策默駱）自然數(shù)的子集中必有最小數(shù)Hence from now on: = y.For the length of this implies: | = | + |y| 直觀解釋： 解碼機長 密碼長 =復(fù)雜度， Note that the y0,1* is encoded trivially.如果 M 變化，則用于比較的標(biāo)準(zhǔn) 不統(tǒng)一W可計算理論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可計算理論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:最小的描述長度 xoutputs y and M on U:yMmin)x(KyMAlso known as: algorithmic complexity, 算術(shù)復(fù)雜度or Kolmogorov (Solomonoff-Chaitin) complexity.W可計算理論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可計算理論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可計算理論2022-5-2621/77R. SolomonoffW可計算理論2022-5-2622/77A. KolmogorovW可計算理論2022-5-2623/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 should say KU instead of KM

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

23、. 且差值與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é)論：用通用機來估計復(fù)雜度，只相差一個常數(shù).W可計算理論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、同串不同機的極小描述 相差不會太大、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é)論：用通用機來估計復(fù)雜度，只相差一個常數(shù).W可計算理論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ù)雜度 不會比原文長太多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、計算理論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ù)雜度 不會比原文長度 大太多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可計算理論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可計算理論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可計算理論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. 要多花一些代價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的編碼長度的2倍為l 描述X,Y的分割點付出的代價，下頁W可計算理論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可計算理論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é)（不難，意義較小）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可計算理論2022-5-2634/77nX是串，

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

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

35、， 對不可壓縮的串x。描述就不能太小。 一個圖靈機M , 長度2002 , 一個串 w 復(fù)雜度2003,且不可壓縮， M 一定不能描述 W. 適當(dāng)規(guī)定大小概念。則 小馬 不能拉 大車 這一直觀感覺 在后面有用 許多軟件。增加能力后，EXE的字節(jié)數(shù)增加了。（Win) 升級軟件要求升級硬盤。符合這一深層次的信息壓縮定理。 1k長的程序不能描述windowsW可計算理論2022-5-2637/77Theorem 6.26: For every n there exists at least one incompressible string x0,1n with K(x)n.存在任意長的不可壓縮串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.長度從1-(n-1)的串比長度為n的串的個數(shù)少W可計算理論2022-5-2638/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-(n-1)的串的總數(shù)， 長度為n的串的總數(shù) 目標(biāo) 待壓W可計算理論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. 用編號j代替字符串sj ， 就短多了。設(shè)N=2m,N個符號只要編碼成長度為log(N) =m的串Hence K(x) cS + log(N) = cS + log(|S|), with constant cS depending

39、 on the description of S.W可計算理論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. 用編號j代替字符串sj ， 就短多了。 例：ASCII用碼代替 字符位圖設(shè)N=2m,N個符號只要編碼成長度為log(N) =m的串1024個串用10位編碼就可

40、區(qū)別了，Hence K(x) cS + log(N) = cS + log(|S|), with constant cS depending on the description of S.W可計算理論2022-5-2641/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(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可計算理論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可計算理論2022-5-2643/77n用8=23個字符（a1,.a8)寫密碼信, 需要壓縮編碼，節(jié)約資源n用huffman編碼，編碼長度與使用頻度反比，用得頻繁的碼長短 ，n設(shè) 8 各字符出現(xiàn)的為頻率分布如表。n編碼 如下頁字符頻率A1A2A31/8A41/8A51/16A61/16A71/16A81/16W可計算理論2022-5-2644/77字符頻率編碼碼長計算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)最小平均碼長 （加權(quán)平均）長度越大 加權(quán)越小= - Pi log2(Pi) = 2.75 bit用它作為信息量的度量是合理的。稱為 熵。是分布不均勻度或混亂程度的度量記為H(A1,A8)性質(zhì)0H(x)log2(N)W可計算理論2022-5-2645/77n當(dāng)8 個字符均勻分布，每個字符出現(xiàn)頻率為1/8, 編碼從000111, 平均碼長為3 ，H=3 n(n個字符，平均為1/2n , H=n, 可見n越大，分布越平均，H越大。 情況越混亂， 熵H越大，要

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

45、分布越平均，H越大。 情況越混亂， 熵H越大，要表達它所需要的平均碼長越大，n春秋戰(zhàn)國，等兵力分布時，戰(zhàn)爭多，混亂，熵大，后來逐漸統(tǒng)一，熵變小，信息變小 （戰(zhàn)爭故事也不多，不精彩了）秦統(tǒng)一中國后，國家對立信息的 編碼只要0位即可n直觀感覺：要說清 混亂的事情，比較費口舌（費信息量）n男生寢室的熵比較大，例如一雙鞋子分居兩地，敘述起來要多說些話，作清潔后 熵變小。n自然現(xiàn)象中 耗散型，增加熵的多，作清潔和生命現(xiàn)象使無序到有序，減少熵（不考慮能量的耗散）W可計算理論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. 圖靈機給出描述數(shù)學(xué)對象如素數(shù)、程序。理論的一一般模型Together with the incompressibility theorem, this allows us to make general statements about these objects

47、.再用不可壓縮定理，可得出一些一般的性質(zhì)W可計算理論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. 圖靈機給出描述數(shù)學(xué)對象如素數(shù)、程序。理論的一一般模型Together with

48、 the incompressibility theorem, this allows us to make general statements about these objects.再用不可壓縮定理，可得出一些一般的性質(zhì)W可計算理論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可計算理論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. （有點意外）W可計算理論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可計算理論2022-5-2652/77如何估計X的復(fù)雜度 K(x)? K(x) n 只對少數(shù)特殊的串成立，有規(guī)律或結(jié)構(gòu) 如 全0串，01交替串，等等， 對于描述 K

52、(x) n 的串應(yīng)該證明 較小的圖靈機的確不能產(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可計算理論2022-5-2653/77如何估計X的復(fù)雜度 K(x)? K(x) n 只對少數(shù)特殊的串成立，有規(guī)律或結(jié)構(gòu) 如 全0串，01交替串，等等， 對于描述 K(x) n 的串應(yīng)該證明 較小的圖靈機的確不能產(chǎn)生它。比喻： x是 最少8馬力才能拉的

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

55、詞定義的最小的數(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可計算理論2022-5-2656/77Consider the following TM M (on input n):1) Tak

56、e 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.Proof by contradiction: Assume C decidable.程序是合理的W可計算理論202

57、2-5-2657/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

58、 not decidable.Proof by contradiction: Assume C decidable.程序是合理的W可計算理論2022-5-2658/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的最小描述w為n+1,結(jié)論 The set | K(x) n is not decidable.(But it is co-

59、TM recognizable.)W可計算理論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長度有限，其描述能力是有上限的，記為nA （依賴于 A的描述大小)， 針對 小馬，造大車： A /小馬，描述能力 nA 不能描述下列這些復(fù)雜命題 x | x =true, K(x) nA

60、 / 大車W可計算理論2022-5-2660/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 statement and go to 2)問題出在這里，足夠長的命題是不能被枚舉出來的W可計算理論2022-5-2661/771