【正文】 and its input y is going to be one long bitstring: ___10101010011 yi n p u t Mm a c h i n e T u r i n g?? ??? ?? ??????? ??????? ?? ???How do we know where M stops and y starts? We will use a selfdelimiting code for M: two bits ―00‖ for ?zero‘, two bits ―11‖ for ?one‘, and ―01‖ for ?end of string‘. 相當(dāng)于編碼為 4進(jìn)位， M 分隔符 w Univ. 可計(jì)算理論 2020/11/17 19/77 Description Length of M,y For the encoding of M and x we concatenate the selfdelimiting/double bit description of M with y. 為什么選最小描述 ? 1. 無(wú)最長(zhǎng)， 2. 較長(zhǎng)的不惟一，3. 最短的是唯一的 Hence from now on: M,y = My. For the length of M,y this implies: |M,y| = |M| + |y| Note that the y?{0,1}* is encoded trivially. 如果 M 變化，則標(biāo)準(zhǔn) 不統(tǒng)一 Univ. 可計(jì)算理論 2020/11/17 20/77 Description Length of M,y For the encoding of M and x we concatenate the selfdelimiting/double bit description of M with y. 為什么選極小描述 ? (1). 無(wú)最長(zhǎng)描述， (2). 較長(zhǎng)的不惟一， (3). 最短的是唯一的 有一個(gè)公理（策默駱）自然數(shù)的子集中必有最小數(shù) Hence from now on: M,y = My. For the length of M,y this implies: |M,y| = |M| + |y| 直觀解釋 ： 解碼機(jī)長(zhǎng) ＋密碼長(zhǎng) =復(fù)雜度， Note that the y?{0,1}* is encoded trivially. 如果 M 變化，則 用于比較的標(biāo)準(zhǔn) 不統(tǒng)一 Univ. 可計(jì)算理論 2020/11/17 21/77 Minimum Description x (Fix a universal Turing machine U.) （例如固定為 ) The minimal description d(x) is the shortest string My such that U on My outputs x. 用 |d(x)| 描述 X的復(fù)雜度 The length |d(x)| will be the plexity of x… Univ. 可計(jì)算理論 2020/11/17 22/77 Descriptive Complexity of x Kkolmogolov , cp147 (Fix a universal Turing machine U.) The descriptive plexity K(x) of a string x is the length |d(x)| of its minimal description: 最小的描述長(zhǎng)度 ? ? xo u tp u ts y a n d M on U:yMm in)x(KyM ???Also known as: algorithmic plexity, 算術(shù)復(fù)雜度 or Kolmogorov (SolomonoffChaitin) plexity. Univ. 可計(jì)算理論 2020/11/17 23/77 Descriptive Complexity of x Kkolmogolov ,cp147 (Fix a universal Turing machine U.) The descriptive plexity K(x) of a string x is the length |d(x)| of its minimal description: ? ? xo u tp u ts y a n d M on U:yMm in)x(KyM ???Also known as: algorithmic plexity, 算術(shù)復(fù)雜度 or Kolmogorov (SolomonoffChaitin) plexity. Univ. 可計(jì)算理論 2020/11/17 24/77 Kolmogorov( ) Complexity The idea of measuring the plexity of bitstrings by the smallest possible Turing machine that produces the string has been proposed by: 三位研究研究者 R. Solomonoff A. Kolmogorov B. G. Chaitin Univ. 可計(jì)算理論 2020/11/17 25/77 Kolmogorov(?) Complexity R. Solomonoff Univ. 可計(jì)算理論 2020/11/17 26/77 Kolmogorov(?) Complexity A. Kolmogorov Univ. 可計(jì)算理論 2020/11/17 27/77 How Universal is K? 如何通用？有多大誤差？ Recall: (Fix a universal Turing machine U.) 下面的與定義６ .20 稍有差別， 等價(jià) ? ? xo u tp u ts y a n d M on U:yMm in)x(KyM ???Problem: The function K depends on the universal U that is used: we should say KU instead of K… Maybe that for another TM V, the plexity measure KV is much smaller than KU? Univ. 可計(jì)算理論 2020/11/17 28/77 How Universal is K? 如何通用？有多大誤差？ Recall: (Fix a universal Turing machine U.) ? ? xo u tp u ts y a n d M on U:yMm in)x(KyM ???Problem: The function K depends on the universal U that is used: we should say KU instead of K… Maybe that for another TM V, the plexity measure KV is much smaller than KU? K似乎與通用圖靈機(jī)的選擇有關(guān)， 下頁(yè)證明 即使與 U有關(guān)， 也影響不大 Univ. 可計(jì)算理論 2020/11/17 29/77 Invariance Theorem ep217 Theorem : Let U be a universal TM, then for 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. 且差值與 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ù) . Univ. 可計(jì)算理論 2020/11/17 30/77 Invariance Theorem ep217 Theorem ６ .2１ : Let U be a universal TM, then for 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. 且差值與 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ù) . Univ. 可計(jì)算理論 2020/11/17 31/77 An Obvious First Result ep215 可自學(xué) Theorem ６ .21: There exists a constant c, such that K(x) ? |x| + c, for every x. (―The plexity of a string can never be much bigger than its length.‖) 串的復(fù)雜度 不會(huì)比原文長(zhǎng)太多 Proof: Let M be the TM that simply outputs its input string y: M(y)=y. Then Mx is a description of x, and hence K(x) ? |M| + |x|. Let c=|M|. (Here we benefit from our way of encoding (M,y). Univ. 可計(jì)算理論 2020/11/17 32/77 An Obvious First Result ep215 可自學(xué) Theorem ６ .21: There exists a constant c, such that K(x) ? |x| + c, for every x. (―The plexity of a string can never be much bigger than its length.‖) 串的復(fù)雜度 不會(huì)比原文長(zhǎng)度 大太多 Proof: Let M be the TM that simply outputs its input string y: M(y)=y. Then Mx is a description of x, and hence K(x) ? |M| + |x|. Let c=|M|. (Here we benefit from our way of encoding (M,y). Univ. 可計(jì)算理論 2020/11/17 33/77 Data Compression ep215 cp14７ 可自學(xué) Theorem C６ .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 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. 可計(jì)算理論 2020/11/17 34/77 Data Compression ep215 cp147 Theorem : There is a constant c such