### 技术控

今日:55| 主题:53525

# [其他] Kolmogorov Complexity – A Primer – Math ∩ Programming

485 2

### 立即注册CoLaBug.com会员，免费获得投稿人的专业资料，享用更多功能，玩转个人品牌！

x
The Complexity of Things

Previously on this blog (quite a while ago), we’ve investigated some simple ideas of using randomness in artistic design ( psychedelic art , and earlier randomized css designs ), and measuring the complexity of such constructions . Here we intend to give a more thorough and rigorous introduction to the study of the complexity of strings. This naturally falls into the realm of computability theory and complexity theory, and so we refer the novice reader to our other primers on the subject ( Determinism and Finite Automata , Turing Machines , and Complexity Classes ; but Turing machines will be the most critical to this discussion).
The Problem with Randomness

What we would really love to do is be able to look at a string of binary digits and decide how “random” it is. On one hand, this is easy to do at a high level. A child would have no difficulty deciding which of the following two strings is more random:
And yet, by the immutable laws of probability, each string has an equal chance (

Kolmogorov Complexity – A Primer – Math ∩ Programming

) in being chosen at random from all sequences of 50 binary digits. So in a sense, the huge body of mathematics underlying probability has already failed us at this basic juncture because we cannot speak of how random one particular outcome of an experiment is. We need a new notion that overcomes this difficulty.
Definition: The Kolmogorov complexity of a string , denoted

Kolmogorov Complexity – A Primer – Math ∩ Programming

is the length of the shortest program which outputs given no input.
While this definition is not rigorous enough to be of any use (we will reformulate it later), we can easily see why the first of the two strings above is less random. We can write a very short Python program that outputs it:
1. print "01" * 25

On the other hand, it is not hard to see that the shortest program that produces the second string is
1. print "00011101001000101101001000101111010100000100111101"

The dutiful reader will cry out in protest. How do you know that’s the shortest program? Why restrict to Python? This whole discussion is so arbitrary!
Indeed, this is probably not the strictly shortest Python program that prints out the string. In the following we’ll work entirely in binary, so the picky reader should interpret this as a print command referring to a block of binary memory. We will reify these ideas in full rigor shortly, but first let us continue with this naivete to make the coming definitions a bit easier to parse.
If we abstract away the lengths of these strings, we see that the length of the first program is

Kolmogorov Complexity – A Primer – Math ∩ Programming

, since we need

Kolmogorov Complexity – A Primer – Math ∩ Programming

bits to represent the number

Kolmogorov Complexity – A Primer – Math ∩ Programming

in the string product. On the other hand, the second string has a program length of

Kolmogorov Complexity – A Primer – Math ∩ Programming

, as we require the entire output string as program text.
This intuition would lead us to define a sequence of length to be random if it has Kolmogorov complexity at least . One way to interpret this is: a string is “random” if the shortest program that outputs the string basically encodes the entire string in its source code.
We can extend this idea to talk about relative complexity. Specifically, we can speak of Python programs which accept input, and compute their output based on that input. For instance, the first of the two strings above has the program:
1. n = input()
2. print "01" * n/2

With respect to the input “50”, we see that the first string has constant complexity (indeed, this is also true of many numbers, such as 25). In other words, the string “50” contains a lot of information about the string we wish to generate (it’s length).
On the other hand, the same technique still won’t work for the second string. Even though it has length 50, that is not enough information to determine the contents of the string, which vary wildly. So the shortest program is still (probably) the one which prints out the string verbatim.
In the future, we plan to revisit the idea of relative complexity in the context of machine learning and classification; briefly, two items are similar if one has low complexity relative to the other. But for now, let us turn to the more precise definitions.
Actual Kolmogorov Complexity

We keep saying of the second string above that the shortest program is probably the one which prints the string verbatim. In fact, short of testing every single python program of shorter length, we will never know if this is true! Even if we did, our following definitions will make that discovery irrelevant. More generally, it’s an important fact that Kolmogorov complexity is an uncomputable function. That is, there is no Turing machine

Kolmogorov Complexity – A Primer – Math ∩ Programming

which accepts as input a word and produces its Kolmogorov complexity as output. In order to prove such miraculous things, we need to formalize the discussion in the context of Turing machines.
Let us fix a universal programming language

Kolmogorov Complexity – A Primer – Math ∩ Programming

and speak of the Kolmogorov complexity with respect to :
Definition: The Kolmogorov complexity of a string with respect to , denoted

Kolmogorov Complexity – A Primer – Math ∩ Programming

is the shortest program written in the language which produces as output. The conditional Kolmogorov complexity with respect to a string , denoted

Kolmogorov Complexity – A Primer – Math ∩ Programming

(spoken given , as in probability theory), is the length of the shortest program which, when given as input, outputs .
Before we can prove that this definition is independent of (for all intents and purposes), we need a small lemma, which we have essentially proved already:
Lemma: For any strings

Kolmogorov Complexity – A Primer – Math ∩ Programming

and any language , we have

Kolmogorov Complexity – A Primer – Math ∩ Programming

for some constant independent of

Kolmogorov Complexity – A Primer – Math ∩ Programming

, and

Kolmogorov Complexity – A Primer – Math ∩ Programming

for some constant

Kolmogorov Complexity – A Primer – Math ∩ Programming

independent of .
Proof. The program which trivially outputs the desired string has length

Kolmogorov Complexity – A Primer – Math ∩ Programming

, for whatever constant number of letters is required to dictate that a string be given as output. This is clearly independent of the string and any input.

Kolmogorov Complexity – A Primer – Math ∩ Programming

It is not hard to see that this definition is invariant under a choice of language up to a constant factor. In particular, let be a string and fix two languages

Kolmogorov Complexity – A Primer – Math ∩ Programming

. As long as both languages are universal , in the sense that they can simulate a universal Turing machine, we can relate the Kolmogorov complexity of with respect to both languages. Specifically, one can write an interpreter for in the language of

Kolmogorov Complexity – A Primer – Math ∩ Programming

and vice versa. Readers should convince themselves that for any two reasonable programming languages, you can write a finite-length program in one language that interprets and executes programs written in the other language.
If we let be the shortest program written in that outputs given , and be the interpreter for written in , then we can compute given the input

Kolmogorov Complexity – A Primer – Math ∩ Programming

by way of the interpreter . In other words,

Kolmogorov Complexity – A Primer – Math ∩ Programming

.

Kolmogorov Complexity – A Primer – Math ∩ Programming

Another easy way to convince oneself of this is to imagine one knows the language . Then the program would be something akin to:
1. input x
2. run the interpreter i on the program p with input x

Our inequalities above just describe the length of this program: we require the entire interpreter , and the entire program , to be part of the program text. After that, it’s just whatever fixed constant amount of code is required to initialize the interpreter on that input.
We call this result the invariance property of Kolmogorov complexity. And with this under our belt, we may speak of the Kolmogorov complexity of a string. We willingly ignore the additive constant difference which depends on the language chosen, and we may safely work exclusively in the context of some fixed universal Turing machine (or, say, Python, C, Racket, or Whitespace ; pick your favorite). We will do this henceforth, denoting the Kolmogorov complexity of a string .
Some Basic Facts

The two basic facts we will work with are the following:

• There are strings of arbitrarily large Kolmogorov complexity.
• Most strings have high complexity.
And we will use these facts to prove that

Kolmogorov Complexity – A Primer – Math ∩ Programming

is uncomputable.
The first point is that for any , there is a string such that

Kolmogorov Complexity – A Primer – Math ∩ Programming

. To see this, we need only count the number of strings of smaller length. For those of us familiar with typical combinatorics, it’s just the Pigeonhole Principle applied to all strings of smaller length.
Specifically, there is at most one string of length zero, so there can only be one string with Kolmogorov complexity zero; i.e., there is only one program of length zero, and it can only have one output. Similarly, there are two strings of length one, so there are only two strings with Kolmogorov complexity equal to one. More generally, there are

Kolmogorov Complexity – A Primer – Math ∩ Programming

strings of length , so there are at most

Kolmogorov Complexity – A Primer – Math ∩ Programming

strings of Kolmogorov complexity less than . However, as we have seen before , this sum is

Kolmogorov Complexity – A Primer – Math ∩ Programming

. So there are too many strings of length and not enough of smaller length, implying that at least one string of length has Kolmogorov complexity at least .
The second point is simply viewing the above proof from a different angle: at least 1 string has complexity greater than , more than half of the

Kolmogorov Complexity – A Primer – Math ∩ Programming

strings have complexity greater than

Kolmogorov Complexity – A Primer – Math ∩ Programming

, more than three quarters of the strings have complexity greater than

Kolmogorov Complexity – A Primer – Math ∩ Programming

, etc.
Rigorously, we will prove that the probability of picking a string with

Kolmogorov Complexity – A Primer – Math ∩ Programming

is smaller than

Kolmogorov Complexity – A Primer – Math ∩ Programming

. Letting

Kolmogorov Complexity – A Primer – Math ∩ Programming

be the set of all such strings, we have an injection

Kolmogorov Complexity – A Primer – Math ∩ Programming

the set of all strings of length less than

Kolmogorov Complexity – A Primer – Math ∩ Programming

, and there are

Kolmogorov Complexity – A Primer – Math ∩ Programming

such strings, so

Kolmogorov Complexity – A Primer – Math ∩ Programming

, giving the inequality:

Kolmogorov Complexity – A Primer – Math ∩ Programming

In other words, the probability that a randomly chosen string of length has

Kolmogorov Complexity – A Primer – Math ∩ Programming

is at least

Kolmogorov Complexity – A Primer – Math ∩ Programming

.
The strings of high Kolmogorov complexity have special names.
Definition: We call a string such that

Kolmogorov Complexity – A Primer – Math ∩ Programming

a  Kolmogorov random string , or an  incompressible string .
This name makes sense for two reasons. First, as we’ve already mentioned, randomly chosen strings are almost always Kolmogorov random strings, so the name “random” is appropriate. Second, Kolmogorov complexity is essentially the ideal compression technique. In a sense, strings with high Kolmogorov complexity can’t be described in any shorter language; such a language would necessarily correspond to a program that decodes the language, and if the compression is small, so is the program that decompresses it (these claims are informal, and asymptotic).
Uncomputability

We will now prove the main theorem of this primer, that Kolmogorov complexity is uncomputable.
Theorem: The Kolmogorov complexity function

Kolmogorov Complexity – A Primer – Math ∩ Programming

is uncomputable.
Proof. Suppose to the contrary that is computable, and that is a Turing machine which computes it. We will construct a new Turing machine

Kolmogorov Complexity – A Primer – Math ∩ Programming

which computes strings of high complexity, but will have a short description, giving a contradiction.
Specifically, iterates over the set of all binary strings in lexicographic order. For each such string , it computes , halting once it finds a such that

Kolmogorov Complexity – A Primer – Math ∩ Programming

. Then we have the following inequality:

Kolmogorov Complexity – A Primer – Math ∩ Programming

Here, the angle bracket notation represents a description of the tuple

Kolmogorov Complexity – A Primer – Math ∩ Programming

, and is a constant depending only on , which is fixed. The reason the inequality holds is just the invariance theorem:

Kolmogorov Complexity – A Primer – Math ∩ Programming

is a description of in the language of Turing machines. In other words, the universal Turing machine which simulates on will output , so the Kolmogorov complexity of is bounded by the length of this description (plus a constant).
Then the length of is at most

Kolmogorov Complexity – A Primer – Math ∩ Programming

for some constant , and this is in turn

Kolmogorov Complexity – A Primer – Math ∩ Programming

for some constant

Kolmogorov Complexity – A Primer – Math ∩ Programming

(as the description of is constant). This gives the inequality

Kolmogorov Complexity – A Primer – Math ∩ Programming

But since

Kolmogorov Complexity – A Primer – Math ∩ Programming

, we may pick sufficiently large to achieve a contradiction.
We can interpret this philosophically: it is impossible to tell exactly how random something is. But perhaps more importantly, this is a genuinely different proof of uncomputability from our proof of the undecidability of the Halting problem. Up until now, the only way we could prove something is uncomputable is to reduce it to the Halting problem. Indeed, this lends itself nicely to many new kinds of undecidability-type theorems, as we will see below.
The reader may ask at this point, “Why bother talking about something we can’t even compute!?” Indeed, one might think that due to its uncomputability, Kolmogorov complexity can only provide insight into theoretical matters of no practical concern. In fact, there are many practical applications of Kolmogorov complexity, but in practice one usually gives a gross upper bound by use of the many industry-strength compression algorithms out there, such as Huffman codes . Our goal after this primer will be to convince you of its remarkable applicability, despite its uncomputability.
Consequences of Uncomputability and Incompressibility

One immediate consequence of the existence of incompressible strings is the following: it is impossible to write a perfect lossless compression algorithm. No matter how crafty one might be, there will always be strings that cannot be compressed.
But there are a number of other, more unexpected places that Kolmogorov complexity fills a niche. In computational complexity, for instance, one can give a lower bound on the amount of time it takes a single-tape Turing machine to simulate a two-tape Turing machine. Also in the realm of lower bounds, one can prove that an incompressible string of length , which can be interpreted as a boolean function on variables, requires

Kolmogorov Complexity – A Primer – Math ∩ Programming

gates to express as a circuit.
It also appears outside of theoretical computer science. In, for instance, the study of entropy in dynamical systems (specifically, thermodynamics), one can make the following pictorial remark :

Kolmogorov Complexity – A Primer – Math ∩ Programming

In fact, the author of this image, Scott Aaronson (whom we’ve seen before in our exploration of the Complexity Zoo ) even proposes an empirical test of this fact: simulate a discretized coffee cup and try to compress the data at each step, graphing the resulting lengths to see the trends. This even sounds like a good project for this blog!
The applications don’t end there, though. Researchers have used the theory of Kolmogorov complexity to tackle problems in machine learning, clustering, and classification. Potentially, any subject which is concerned with relating pieces of information could benefit from a Kolmogorov-theoretic analysis.
Finally, we give a proof that the existence of Kolmogorov complexity provides an infinite number of mathematical statements which are unprovable.
Theorem: Fix a formalization of mathematics in which the following three conditions hold:

• If a statement is provable then it is true.
• Given a proof and a statement, it is decidable whether the proof proves the statement.
• For every binary string and integer , we can construct a statement

Kolmogorov Complexity – A Primer – Math ∩ Programming

which is logically equivalent to “the Kolmogorov complexity of is at least “.
Then there is some constant for which all statements with

Kolmogorov Complexity – A Primer – Math ∩ Programming

are unprovable.
Proof. We construct an algorithm to find such proofs as follows:
1. On an input k,
2. Set m equal to 1.
3. Loop:
4.    for all strings x of length at most m:
5.       for all strings P of length at most m:
6.          if P is a proof of S(x,k), output x and halt
7.    m = m+1

Suppose to the contrary that for all there is an for which the statement is provable. It is easy to see that the algorithm above will find such an . On the other hand, for all such proofs

Kolmogorov Complexity – A Primer – Math ∩ Programming

, we have the following inequality:

Kolmogorov Complexity – A Primer – Math ∩ Programming

Indeed, this algorithm is a description of , so its length gives a bound on the complexity of . Just as in the proof of the uncomputability of , this inequality can only hold for finitely many , a contradiction.
Note that this is a very different unprovability-type proof from Gödel’s Incompleteness Theorem. We can now construct with arbitrarily high probability arbitrarily many unprovable statements.
Look forward to our future posts on the applications of Kolmogorov complexity! We intend to explore some compression algorithms, and to use such algorithms to explore clustering problems, specifically for music recommendations.
Until then!

 小白一个 顶一下

 巴黎铁塔的风景也是蛮拼的

*滑动验证: #conqu3r_oc_viewthread_fastpost_content .clickCaptcha{top:-270px;}

• ## 恋上单车女生 骑单车唯美图片

不求你深深记我一辈子，只求别忘记你的世界 [...]

• ## 电商巨头抢占全球市场，亚马逊缘何对souq念

电商巨头亚马逊3月继续其全球扩张步伐，以6.5亿 [...]

• ## 脑洞大开的语音面具：公共场合打电话不再尴

吵闹的火车站里，打电话时只能提高音量;安静的图 [...]

• ## Uber CEO卡拉尼克：实现员工多元化当前首要

据《今日美国报》北京时间3月25日报道，Uber CEO [...]

• ## 周鸿祎："好领导者"的四个关键词

最近我和一批年轻的创业者去看了《鸣梁海战》， [...]

• ## Twitter considering subscription model a

In the latest segment of Twitter’s journey t [...]

• ## 别人家的迪士尼定制手机，夏普 SH-02G 体验

明星跨界定制手机这事并不少见，但相比早几年的 [...]

• ## 我还在原地等你，你却假装忘记曾来过这里…

【美图心语】青春如酒，成长正酣，所有美好的， [...]

• ## The Morning After: Weekend Edition

But we're all adults here — or at least [...]

• ## 总经理离职，儿子创业，曹德旺的接班人在哪

近日，福耀玻璃（600660.SH）发布一则公告，外界 [...]

© 2001-2017 Comsenz Inc. Design: Dean. DiscuzFans.