lecturenotesforcomputationtheory

lecturenotesforcomputationtheory内容摘要：

that K(xx)  K(x) + c, for every string x. 双倍串的的复杂度 不比原串的复杂度 大很多，直观地，增加一句话， ‖输出重复一次 ‖ 但把上述观察叙述清楚，应该如下叙述： Proof: Take the TM M that given input Nx: 1) Calculate the output s of N on x 2) Output ss Let d(x) be the minimum description of x, then Md(x) will give a description of xx. Hence, K(xx)  |M| + |d(x)| = K(x) + c. Univ. 可计算理论 2020/11/17 35/77 Concatenation 一个意料之外的例子 You 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)  K(x) + K(y) + 2log(K(x)) + c, for all strings x and y. X的编码长度的 2倍 为 l 描述 X,Y的分割点付出的代价，下页 Univ. 可计算理论 2020/11/17 36/77 Log Cost of Concatenation ep216 cp147 Theorem (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 the string ―1m0 |d(x)| d(x)‖ gives a selfdelimitin－ description of x. (We need 2m bits to indicate the length of d(x).) Hence the input ―1m0 |d(x)| d(x) d(y)‖ gives an unambiguous description of xy. Univ. 可计算理论 2020/11/17 37/77 Log Cost of Concatenation ep216 cp147 Theorem (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 the string ―1m0 |d(x)| d(x)‖ gives a selfdelimitin－ description of x. (We need 2m bits to indicate the length of d(x).) Hence the input ―1m0 |d(x)| d(x) d(y)‖ gives an unambiguous description of xy. Univ. 可计算理论 2020/11/17 38/77 不可压缩串  X是串， c0 , K(x)|x|c, 称 x是 C可压缩（长度压了 C）  反之 不可 c压缩 , c=1时 称为不可压缩的， 最小描述比原串长度小 C 反过来， 对不可压缩的串 x。 描述就不能太小。 一个图灵机 M ,M 长度 2020 , 一个串 w 复杂度2020,且不可压缩， M 一定不能描述 W. 我们称为 小马 拉 大车 这一直观感觉 在后面有用 许多软件。 增加能力，增加 EXE的字节数（ Win) 升级软件要求升级硬盘。 符合这一深层次的信息压缩定理。 1k长的程序不能描述 windows Univ. 可计算理论 2020/11/17 39/77 不可压缩串  X是串， c0 , K(x)|x|c, 称 x是 C可压缩（长度压了 C）  反之 不可 c压缩 , c=1时 称为不可压缩的， 最小描述比原串长度小 C 反过来 ， 对不可压缩的串 x。 描述就不能太小。 一个图灵机 M ,M 长度 2020 , 一个串 w 复杂度2020,且不可压缩， M 一定不能描述 W. 我们称为 小马 拉 大车 这一直观感觉 在后面有用 许多软件。 增加能力后， EXE的字节数增加了。 （ Win) 升级软件要求升级硬盘。 符合这一深层次的信息压缩定理。 1k长的程序不能描述 windows Univ. 可计算理论 2020/11/17 40/77 不可压缩串  X是串， c0 , K(x)|x|c, 称 x是 C可压缩（长度压了 C）  反之 不可压缩 c, c=1时 称为不可压缩的， 最小描述比原串长度小 C 反过来 ， 对不可压缩的串 x。 描述就不能太小。 一个图灵机 M ,M 长度 2020 , 一个串 w 复杂度2020,且不可压缩， M 一定不能描述 W. 适当规定 大小 概念。 则 小马 不能拉 大车 这一直观感觉 在后面有用 许多软件。 增加能力后， EXE的字节数增加了。 （ Win) 升级软件要求升级硬盘。 符合这一深层次的信息压缩定理。 1k长的程序不能描述 windows Univ. 可计算理论 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的串的个数少 Univ. 可计算理论 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)的串的总数 ， 长度为 n的串的总数 目标 待压 Univ. 可计算理论 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 ， 就短多了。 设 N=2m,N个符号只要编码成长度为 log(N) =m的串 Hence K(x)  cS + log(N) = cS + log(|S|), with constant cS depending on the description of S. Univ. 可计算理论 2020/11/17 44/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 ， 就短多了。 例： 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. Univ. 可计算理论 2020/11/17 45/77 Frequency Compression 频率压缩 Let x {0,1}n with 75% zeros and 25% ones. 高频率者用短码，低频率用长码，使得总体码长较小 Consider the set S{0,1}n of all such strings. The description of S requires  c + 2log(n) bits. The size of S is |S|  . The description of x requires no more than c + 2log(n) + log(|S|) = c + 2log(n) + bits. For large enough n: K(x)  (approximately). Univ. 可计算理论 2020/11/17 46/77 Shannon Entropy of Strings 桑龙 串熵 ep217 We can press a bitstring {0,1}n, depending on the 0/1 distribution. The Shannon entropy of this distribution (p,1–p) gives an upper bound on the Kplexity. Univ. 可计算理论 2020/11/17 47/77 Best Splits (Cont.) 补充 熵概念  用 8=23个字符（ a1,..a8)写密码信 , 需要压缩编码，节约资源  用 huffman编码，编码长度与使用频度反比，用得频繁的码长短 ，  设 8 各字符出现的为频率分布如表。  编码 如下页 k i 1 pilog2 pi 字符 频率 A1 188。 A2 188。 A3 1/8 A4 1/8 A5 1/16 A6 1/16 A7 1/16 A8 1/16 Univ. 可计算理论 2020/11/17 48/77 Best Splits (Cont.)。