计算理论10_不可压缩性

1、W可计算理论2022-1-261 Chapter 6.4: Definition of Information by Descriptive / Kolmogorov Complexity若干补充若干补充 Incompressible Strings Chapter 6 Arguments by Incompressibility Learning theoryW可计算理论2022-1-262Standard information theory considers each n bit-string in 0,1n equal (all have probability 2n).Howeve

2、r, we feel a difference between the stringA=“0101010101010101010101010101010101”有规律地 重复01串 17次，可压缩为 01#17and the string (of equal length)B=“0101110101001010001110001100011011”.比较复杂，几句化说不清的，信息量较大直观感觉：长话短说 的 最短尺寸，可用来度量其信息量W可计算理论2022-1-263Standard information theory considers each n bit-string in 0,1n

3、equal (all have probability 2n).However, we feel a difference between the stringA=“0101010101010101010101010101010101” 有规律地 重复01串 17次，可压缩为 01#17and the string (of equal length)B=“0101110101001010001110001100011011”.比较复杂，几句化说不清的，信息量较大直观感觉：长话短说 的 最短尺寸，可用来度量其信息量W可计算理论2022-1-264Standard information theo

4、ry considers each n bit-string in 0,1n equal (all have probability 2n).However, we feel a difference between the stringA=“0101010101010101010101010101010101”有规律地 重复01串 17次，可压缩为 01#17and the string (of equal length)B=“0101110101001010001110001100011011”. 比较复杂的，短话说不清的，信息量较大直观感觉：表达语义的 最短尺寸，可用来度量其信息量W可计

5、算理论2022-1-265We can give a short description of “0101010101010101010101010101010101” by “17 times 01”.For the other “0101110101001010001110001100011011” this seems more problematic.Suggests: 规律性使得描述较短（信息量较小）A regular string is a string that has a short description; an irregular one has no such summa

6、ry.W可计算理论2022-1-266We can give a short description of “0101010101010101010101010101010101” by “17 times 01”.For the other “0101110101001010001110001100011011” this seems more problematic.Suggests: 规律性 使得描述较短（有规律的，信息量较小）A regular string is a string that has a short description; an irregular one has n

7、o such summary.W可计算理论2022-1-267Problem: What do we consider a description?What may be an obvious description for one, may be illegible for somebody else:3.14.011001001000011111101101010100010001000010110100011000010001101001100010011000110011000101000101110000000110111000001110011010001001010010 We

8、need a proper definition of a description.W可计算理论2022-1-268Problem: What do we consider a description?What may be an obvious description for one, may be illegible for somebody else:3.14.0110010010000111111011010101000100010000101101000110000100011010011000100110001100110001010001011100000001101110000

9、01110011010001001010010 We need a proper definition of a description.W可计算理论2022-1-269 重复17次 01 TM M w 说明可用w的长度来描述信息量X 的复杂度（信息量）为 Min ( |+|w| : x=M(w), M is TM )例 用Winzip 压缩A.doc 成为A.zip , 121K | |+|A.zip| 能描述Z.Doc的复杂度Some details need to be sorted out first though规律的描述和输入W可计算理论2022-1-2610 重复17次 01 T

10、M M w 说明可用w的长度来描述信息量X 的 复杂度（信息量）为 Min ( |+|w| : x=M(w), M is TM )例 用Winzip 压缩A.doc 成为A.zip , 121K | |+|A.zip| 能描述Z.Doc的复杂度Some details need to be sorted out first though又例：某个问题用亿次机算，最少要用1个月 TM M time规律的描述和输入W可计算理论2022-1-2611 重复17次 01 TM M w 说明可用w的长度来描述信息量X 的 复杂度（信息量）为 Min ( |+|w| : x=M(w), M is TM )

11、例 用Winzip 压缩A.doc 成为A.zip , 121K | |+|A.zip| 能描述Z.Doc的复杂度Some details need to be sorted out first though又例：某个问题用亿次计算机，最少要用1个月 TM M time规律的描述和输入压缩程序复杂一些，压缩出来的文件可能小一些W可计算理论2022-1-2612We 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

12、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-1-2613We 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)

13、 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-1-2614The description of the TM M and its input y isgoing to be one long bit-string:_1010

14、1010011 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. 相当于编码为4进位，M 分隔符 wW可计算理论2022-1-2615For the encoding of M and x we concatenate the self-delimiting/double bit descrip

15、tion 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 变化，则标准不统一W可计算理论2022-1-2616For the encoding of M and x we concatenate the self-delimiting/double bit description of M with y.为什么选极小描述?

16、(1). 无最长描述，(2). 较长的不惟一，(3). 最短的是唯一的有一个公理（策默骆）自然数的子集中必有最小数Hence from now on: = y.For the length of this implies: | = | + |y| 直观解释： 解码机长 密码长 =复杂度， Note that the y0,1* is encoded trivially.如果 M 变化，则用于比较的标准 不统一W可计算理论2022-1-2617(Fix a universal Turing machine U.) （例如固定为WinZip.exe)The minimal description

17、d(x) is the shorteststring y such that U on y outputs x.用|d(x)| 描述X的复杂度The length |d(x)| will be the complexity of xW可计算理论2022-1-2618(Fix a universal Turing machine U.)The descriptive complexity K(x) of a string x is the length |d(x)| of its minimal description:最小的描述长度 xoutputs y and M on U:yMmin)x(

18、KyMAlso known as: algorithmic complexity, 算术复杂度or Kolmogorov (Solomonoff-Chaitin) complexity.W可计算理论2022-1-2619(Fix a universal Turing machine U.)The descriptive complexity K(x) of a string x is the length |d(x)| of its minimal description: xoutputs y and M on U:yMmin)x(KyMAlso known as: algorithmic

19、complexity, 算术复杂度or Kolmogorov (Solomonoff-Chaitin) complexity.W可计算理论2022-1-2620The idea of measuring the complexity of bit-stringsby the smallest possible Turing machine that produces the string has been proposed by: 三位研究研究者R. Solomonoff KolmogorovA. G. ChaitinW可计算理论2022-1-2621R. SolomonoffW可计算理论20

20、22-1-2622A. KolmogorovW可计算理论2022-1-2623Recall: (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 KMaybe that for another TM V, the complexity measure KV is much smaller th

21、an KU?W可计算理论2022-1-2624Recall: (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 complexity measure KV is much smaller than KU?K似乎与通用图灵机的选择有关，下页证明 即使与U有关，

22、也影响不大W可计算理论2022-1-2625Theorem 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. 且差值与x 无关Proof: Because U is universal, we can give a finite description to U

23、 how it should simulate V.Let this description be of size c.结论：用通用机来估计复杂度，只相差一个常数.W可计算理论2022-1-2626Theorem 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. 且差值与

24、x 无关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.结论：用通用机来估计复杂度，只相差一个常数.W可计算理论2022-1-2627Theorem 6.21: There exists a constant c, suchthat K(x) |x| + c, for every x. (“The complexity ofa string can never be much bigger

25、 than its length.”) 串的复杂度 不会比原文长太多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可计算理论2022-1-2628Theorem .21: There exists a constant c, suchthat K(x) |x| + c, for ev

26、ery x. (“The complexity ofa string can never be much bigger than its length.”) 串的复杂度 不会比原文长度 大太多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可计算理论2022-1-2629Theorem

27、 C6.22: There is a constant c such that K(xx) K(x) + c, for every string x.双倍串的的复杂度 不比原串的复杂度 大很多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 description of x,then d(x) will give a description of xx.Hence, K(xx) | + |d(x)| = K(x) + c.W

28、可计算理论2022-1-2630Theorem 6.22: There is a constant c such that K(xx) K(x) + c, for every string x.双倍串的的复杂度 不比原串的复杂度 大很多，直观地，增加一句话，”输出重复一次”但把上述观察叙述清楚，应该如下叙述：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 description of x,then d(x) will gi

29、ve a description of xx.Hence, K(xx) | + |d(x)| = K(x) + c.W可计算理论2022-1-2631You 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 lies again in the separation between d(x) and d(y). Instead, we have a constant c such that: K(xy

30、) K(x) + K(y) + 2log(K(x) + c, for all strings x and y.X的编码长度的2倍为l 描述X,Y的分割点付出的代价，下页W可计算理论2022-1-2632Theorem 6.23(log): There is a c such that K(xy) K(x) + K(y) + 2log(K(x) + c, for all x,y.自学（不难，意义较小）Proof: Let m be the logarithm of |d(x)|, then thestring “1m0 d(x)” gives a self-delimitin descripti

31、on 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-1-2633Theorem 6.23(log): There is a c such that K(xy) K(x) + K(y) + 2log(K(x) + c, for all x,y.自学（不难，意义较小）Proof: Let m be the logarithm of |d(x)|, then thestring

32、 “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-1-2634nX是串， c0 , K(x)|x|-c, 称x是C-可压缩（长度压了C）n反之 不可c压缩, c=1时 称为不可压缩的， 最小描述比原串长度小C 反过来， 对不可压缩的串x。描述就不能太小。 一个图灵机M , 长度200

33、2 , 一个串 w 复杂度2003,且不可压缩， M 一定不能描述 W. 我们称为 小马 拉 大车 这一直观感觉 在后面有用 许多软件。增加能力，增加EXE的字节数（Win) 升级软件要求升级硬盘。符合这一深层次的信息压缩定理。 1k长的程序不能描述windowsW可计算理论2022-1-2635nX是串， c0 , K(x)|x|-c, 称x是C-可压缩（长度压了C）n反之 不可c压缩, c=1时 称为不可压缩的， 最小描述比原串长度小C 反过来， 对不可压缩的串x。描述就不能太小。 一个图灵机M , 长度2002 , 一个串 w 复杂度2003,且不可压缩， M 一定不能描述 W. 我们称

34、为 小马 拉 大车 这一直观感觉 在后面有用 许多软件。增加能力后，EXE的字节数增加了。（Win) 升级软件要求升级硬盘。符合这一深层次的信息压缩定理。 1k长的程序不能描述windowsW可计算理论2022-1-2636nX是串， c0 , K(x)|x|-c, 称x是C-可压缩（长度压了C）n反之 不可压缩c, c=1时 称为不可压缩的， 最小描述比原串长度小C 反过来， 对不可压缩的串x。描述就不能太小。 一个图灵机M , 长度2002 , 一个串 w 复杂度2003,且不可压缩， M 一定不能描述 W. 适当规定大小概念。则 小马 不能拉 大车 这一直观感觉 在后面有用 许多软件。增

35、加能力后，EXE的字节数增加了。（Win) 升级软件要求升级硬盘。符合这一深层次的信息压缩定理。 1k长的程序不能描述windowsW可计算理论2022-1-2637Theorem 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. There is one description of length

36、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 least n bits.长度从1-(n-1)的串比长度为n的串的个数少W可计算理论2022-1-2638Theorem 6.26: For every n there exists at least one incompre

37、ssible 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)的串的总数， 长度为n的串的总数 目标 待压W可计算理论2022-1-2639Compression idea: If S is a small set that is easyto describe, then we can describe an xS by: index of x in SL

38、et S = s1,sN. We can indicate every xS by the 1jN such that sj=x. 用编号j代替字符串sj ， 就短多了。设N=2m,N个符号只要编码成长度为log(N) =m的串Hence K(x) cS + log(N) = cS + log(|S|), with constant cS depending on the description of S.W可计算理论2022-1-2640Compression idea: If S is a small set that is easyto describe, then we can des

39、cribe 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用码代替 字符位图设N=2m,N个符号只要编码成长度为log(N) =m的串1024个串用10位编码就可区别了，Hence K(x) cS + log(N) = cS + log(|S|), with constant cS depending on the description of S.W可计算理论2022-1-2641Let x 0,1n

40、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 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 (approx

41、imately). W可计算理论2022-1-2642We 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-complexity.W可计算理论2022-1-2643n用8=23个字符（a1,.a8)写密码信, 需要压缩编码，节约资源n用huffman编码，编码长度与使用频度反比，用得频繁的码长短 ，n设 8 各字符出现的为频率分布如表。n编码 如下页字符频率A1A2

42、A31/8A41/8A51/16A61/16A71/16A81/16W可计算理论2022-1-2644字符频率编码码长计算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(P5)A6P6=1/1610104-Log2(P6)A7P7=1/1610114-Log2(P7)A8P8=1/1611004-Log2(P8)最小平均码长 （加权平均）长度越大 加权越小= - Pi log2(Pi) = 2.75 bit用它作为信息量的度量是合理的。

43、称为 熵。是分布不均匀度或混乱程度的度量记为H(A1,A8)性质0H(x)log2(N)W可计算理论2022-1-2645n当8 个字符均匀分布，每个字符出现频率为1/8, 编码从000111, 平均码长为3 ，H=3 n(n个字符，平均为1/2n , H=n, 可见n越大，分布越平均，H越大。 情况越混乱， 熵H越大，要表达它所需要的平均码长越大，n春秋战国，等兵力分布时，战争多，混乱，熵大，后来逐渐统一，熵变小，信息变小 （战争故事也不多，不精彩了）秦统一中国后，国家对立信息的 编码只要0位即可n直观感觉：要说清 混乱的事情，比较费口舌（费信息量）n男生寝室的熵比较大，例如一双鞋子分居两地

44、，叙述起来要多说些话，作清洁后 熵变小。n自然现象中 耗散型，增加熵的多，作清洁和生命现象使无序到有序，减少熵（不考虑能量的耗散）W可计算理论2022-1-2646n当8 个字符均匀分布，每个字符出现频率为1/8, 编码从000111, 平均码长为3 ，H=3 n(n个字符，平均为1/2n , H=n, 可见n越大，分布越平均，H越大。 情况越混乱， 熵H越大，要表达它所需要的平均码长越大，n春秋战国，等兵力分布时，战争多，混乱，熵大，后来逐渐统一，熵变小，信息变小 （战争故事也不多，不精彩了）秦统一中国后，国家对立信息的 编码只要0位即可n直观感觉：要说清 混乱的事情，比较费口舌（费信息量）

45、n男生寝室的熵比较大，例如一双鞋子分居两地，叙述起来要多说些话，作清洁后 熵变小。n自然现象中 耗散型，增加熵的多，作清洁和生命现象使无序到有序，减少熵（不考虑能量的耗散）W可计算理论2022-1-2647Kolmogorov complexity gives a rigorousdefinition for the notion of order or regularity.严格描述了阶或正则概念The TM model gives us the most general way of describing mathematical objects like primes, computer

46、 programs, or theories. 图灵机给出描述数学对象如素数、程序。理论的一一般模型Together with the incompressibility theorem, this allows us to make general statements about these objects.再用不可压缩定理，可得出一些一般的性质W可计算理论2022-1-2648Kolmogorov complexity gives a rigorousdefinition for the notion of order or regularity.严格描述了阶或正则概念The TM mo

47、del gives us the most general way of describing mathematical objects like primes, computer programs, or theories. 图灵机给出描述数学对象如素数、程序。理论的一一般模型Together with the incompressibility theorem, this allows us to make general statements about these objects.再用不可压缩定理，可得出一些一般的性质W可计算理论2022-1-2649Q: How many prime

48、s 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 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

49、N.W可计算理论2022-1-2650Q: 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.注意：2=Pj 2ej N ej log(N).Thus requires mlog(log(N) bits.Incompressibility: N 的描述 K(N) log(N).Conclusion: 因子数m log(N) / log(log(N) for t

50、hose N. （有点意外）W可计算理论2022-1-2651 . Hence givesa description of N. For each j we have: ej log(N).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 i

51、mplies m log(N)/log(log(N) c/log(log(N) for arbitrary big N. W可计算理论2022-1-2652如何估计X的复杂度 K(x)? K(x) n 只对少数特殊的串成立，有规律或结构 如 全0串，01交替串，等等， 对于描述 K(x) n 的串应该证明 较小的图灵机的确不能产生它。比喻： x是 最少8马力才能拉的车， 3马力 一定拉不动它 ， 小马不能拉大车K can only be approximated from above.True statements like “K(x) n” are recognizable,but not

52、TM-decidable.u W可计算理论2022-1-2653如何估计X的复杂度 K(x)? K(x) n 只对少数特殊的串成立，有规律或结构 如 全0串，01交替串，等等， 对于描述 K(x) 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-1-2654“The least num

53、ber that cannot be defined in fewer than twenty words.” 不能用少于不能用少于20个单词定义的最小的数（已经用个单词定义的最小的数（已经用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”.

54、)悖论是否与不可判定性 有关？下页W可计算理论2022-1-2655“The least number that cannot be defined in fewer than twenty words.” 不能用少于不能用少于20个单词定义的最小的数（已经用个单词定义的最小的数（已经用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.

55、(There is no problem with formalizing “defined”.)悖论是否与不可判定性 有关？下页W可计算理论2022-1-2656Consider the following TM M (on input n):1) Take s= /空字2) Decide C? /开始应该为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(

56、n) Richard-Berry Paradox Theorem:The set C = | K(x) n is not decidable.Proof by contradiction: Assume C decidable.程序是合理的W可计算理论2022-1-2657Consider the following TM M (on input n):1) Take s= /初始化为空字2) Decide C? /开始应该为no3) If answer “no” /描述小，则找下一个词 then increase s lexicographically; go to 2)4) If answ

57、er “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可计算理论2022-1-2658 上页描述 “n”的长度为 cM+log(n). 注意 n 比 log(n)增加得快。n=1024, log(n)=10 所以 n 足够大时， n cM+log(n). 则描述的长度 n

58、 小于 n, 但被他描述的串s 的复杂度 K(s) n. 小马拉大车了。与最小描述的定义矛盾。例如 K(s)=n+1表示s的最小描述w为n+1,结论 The set | K(x) n is not decidable.(But it is co-TM recognizable.)W可计算理论2022-1-2659The impossibility of calculating K gives a simpleway of rephrasing Gdels incompleteness thm.给定Th(N,+,)，设A是找出其中完全公理和推导到规则的程序（TM), A-Attempt。反证法，

59、设是完全的。 由前面结论，知道小马不能拉大车。 给定A长度有限，其描述能力是有上限的，记为nA （依赖于 A的描述大小)， 针对 小马，造大车： A /小马，描述能力 nA 不能描述下列这些复杂命题 x | x =true, K(x) nA / 大车W可计算理论2022-1-2660对任意串 x,命题 “K(x) n” 可编码表示，从而是 Th(N,+,)中的元素.下列程序逻辑上是合理的：Consider the following program that uses A and n:用程序A枚举命题If this statement is of the form “K(x) n”, then

60、 print(x) and halt3) Otherwise: generate next statement and go to 2)问题出在这里，足够长的命题是不能被枚举出来的W可计算理论2022-1-26611) Enumerate a statements that follows from A2) If this statement is of the form “K(x) n”, then print(x) and stop3) Otherwise: generate next statement and go to 2)The above program can be expre