5 ms·

An Introduction to Kolmogorov Complexity

42 points by jnape 11y ago

pacaro 11y ago
For some reason I'm constantly reminded of the story of the discovery of Karatsuba multiplication. At a seminar Kolmogorov suggests that the classic multiplication algorithm was optimal, to multiply two numbers with n digits was O(n^2). Karatsuba, who is a student attending, come back a week later with an O(n^(log_2 3)) algorithm - which Kolmogorov was so excited about he cancelled the rest of the seminar and wrote up and published the algorithm without even telling Karatsuba (although he did list his as the author) There's a lesson in there somewhere
- fit2rule 11y ago
  >There's a lesson in there somewhere Communicate with ones peers even if its mundane?
radicality 11y ago
I don't think this is right. The Kolmgorov complexity as you wrote is the shortest description of some program in a universal language. If you have program P and you shorten it to an isomorphic program P', k(P) = k(P') as we have the true shortest program P* where k(P) = |P| <= k(P). P' has the same Kolmgorov complexity as P.
jfarmer 11y ago
You should disable auto smart-quotes on whatever publishing platform you're using. It's changing puts 'My name is George and my age is 31' into puts ‘My name is George and my age is 31’ I noticed because the syntax highlighting on the Ruby code was incorrect.
- jnape 11y ago
  Yes...sadly, the code highlighting plugin I'm using is not very good. I'll try to find a better one: thanks for the feedback.
j2kun 11y ago
> between two extrinsically identical algorithms, the one that can be expressed - or implemented, as it were - with less characters is fundemantally [sic] simpler in the context of the problem domain. It does not make sense to say "an algorithm can be expressed in fewer characters" because an algorithm is its description in the fixed (universal) description language. This confusion between the Kolmogorov complexity of a string and the Kolmogorov complexity of an algorithm [1] haunts the entire article. [1] Or what, the Kolmogorov complexity of a language? Saying "extrinsically identical algorithms" makes it unclear whether the author understands the difference between an algorithm and a function.
- jnape 11y ago
  > It does not make sense to say "an algorithm can be expressed in fewer characters" because an algorithm is its description in the fixed (universal) description language. If you don't find it fitting to describe an implementation of an algorithm as an expression of that algorithm, fair enough. > This confusion between the Kolmogorov complexity of a string and the Kolmogorov complexity of an algorithm [1] haunts the entire article. "The Kolmogorov complexity of an algorithm" was intended to be "the Kolmogorov complexity of the implementation of an algorithm in some language by some engineer", but perhaps the entire article is rendered ineffective due to this lack of clear distinction. I'll accept that. > Saying "extrinsically identical algorithms" makes it unclear whether the author understands the difference between an algorithm and a function. Perhaps I was too lazy and should have said "extrinsically identical _implementations_ of some algorithm". It is true that algorithms are by most definitions (I like Turing's) necessarily more abstract than the computational mechanisms we use to reify them, but it didn't seem like a crucial failure to not be pedantic about this distinction. Perhaps it was. Hopefully subsequent articles will benefit from your points. Thanks very much for the feedback!
  - j2kun 11y ago
    I think you may be still seriously confused by the definition of Kolmogorov complexity. It's not a fine distinction I'm trying to make, but rather that your definition has a type error! You should think hard about how Kolmogorov complexity (which is defined for strings) can make sense when you try to extend the definition to algorithms in the way you want. They way you've done it is not consistent from what you've written. I suggest you read a few more tutorials on Kolmogorov complexity.
chriswarbo 11y ago
As others have pointed out, the author is confusing a few ideas. First of all, Kolmogorov complexity talks about the output from programs at a "higher-level". For example, to define the Kolmogorov complexity of plain text, we must talk about programs which output text. To define Kolmogorov complexity of, say, Ruby code, we must talk about programs which output Ruby code. And so on. The author mixes up the complexity of the text (eg. in the 3 line example) with the complexity of the code. These are two different things: the complexity of the text depends on the shortest program which outputs that text; the complexity of the code depends on the shortest program which outputs that code. Secondly, writing different programs with the same output doesn't change the Kolmogorov complexity; it merely improves an approximation (since Kolmogorov complexity is undecidable, we must approximate it). The author also uses the word "count" when talking about these approximate numbers, which I think is better than calling them "complexity". A couple more points about the author's argument: 1) When comparing different languages, like Ruby and Python, it might be nice to point out that the complexity can only change by a constant amount. This is because, in the worst possible scenario, we can write an interpreter for the other language. For example, if we use Python as our meta-language, we can denote the complexity of some text T as P(T); if we switch to using Ruby instead, the complexity R(T) <= P(T) + I, where I is the complexity of a Python interpreter written in Ruby. Since I doesn't depend on T, it is a constant, and therefore the choice of language becomes less important as the complexity of T increases. 2) Using Kolmogorov complexity as a benchmark doesn't seem like a great idea to me. It's true that repetition gets eliminated, eg. using loops, but it can also lead to really bizarre things, like crazy integer arithmetic which just-so-happens to produce the correct ASCII characters. Code becomes shorter, but after a certain point it can get unintelligible. In effect, pursuing Kolmogorov complexity means trying to compress your source code. Eventually you'll end up with something like this: def decompress(str): # Insert crazy, program-specific arithmetic here eval(decompress('!"£$%^&*()"£$%^&*(!"£$%^&*')) In particular, code which approaches the limit of Kolmogorov complexity becomes incredibly inter-dependent, lacks all modularity and loses the ability to make incremental changes (making small changes in a compressed encoding leads to large changes in the output). Just look at http://codegolf.stackexchange.com http://codegolf.stackexchange.com for example ;)
- jnape 11y ago

42 points by jnape 11y ago

For some reason I'm constantly reminded of the story of the discovery of Karatsuba multiplication. At a seminar Kolmogorov suggests that the classic multiplication algorithm was optimal, to multiply two numbers with n digits was O(n^2). Karatsuba, who is a student attending, come back a week later with an O(n^(log_2 3)) algorithm - which Kolmogorov was so excited about he cancelled the rest of the seminar and wrote up and published the algorithm without even telling Karatsuba (although he did list his as the author) There's a lesson in there somewhere

fit2rule 11y ago
>There's a lesson in there somewhere Communicate with ones peers even if its mundane?

radicality 11y ago

I don't think this is right. The Kolmgorov complexity as you wrote is the shortest description of some program in a universal language. If you have program P and you shorten it to an isomorphic program P', k(P) = k(P') as we have the true shortest program P* where k(P) = |P| <= k(P). P' has the same Kolmgorov complexity as P.

jfarmer 11y ago

You should disable auto smart-quotes on whatever publishing platform you're using. It's changing puts 'My name is George and my age is 31' into puts ‘My name is George and my age is 31’ I noticed because the syntax highlighting on the Ruby code was incorrect.

jnape 11y ago
Yes...sadly, the code highlighting plugin I'm using is not very good. I'll try to find a better one: thanks for the feedback.

j2kun 11y ago

> between two extrinsically identical algorithms, the one that can be expressed - or implemented, as it were - with less characters is fundemantally [sic] simpler in the context of the problem domain. It does not make sense to say "an algorithm can be expressed in fewer characters" because an algorithm is its description in the fixed (universal) description language. This confusion between the Kolmogorov complexity of a string and the Kolmogorov complexity of an algorithm [1] haunts the entire article. [1] Or what, the Kolmogorov complexity of a language? Saying "extrinsically identical algorithms" makes it unclear whether the author understands the difference between an algorithm and a function.

jnape 11y ago
> It does not make sense to say "an algorithm can be expressed in fewer characters" because an algorithm is its description in the fixed (universal) description language. If you don't find it fitting to describe an implementation of an algorithm as an expression of that algorithm, fair enough. > This confusion between the Kolmogorov complexity of a string and the Kolmogorov complexity of an algorithm [1] haunts the entire article. "The Kolmogorov complexity of an algorithm" was intended to be "the Kolmogorov complexity of the implementation of an algorithm in some language by some engineer", but perhaps the entire article is rendered ineffective due to this lack of clear distinction. I'll accept that. > Saying "extrinsically identical algorithms" makes it unclear whether the author understands the difference between an algorithm and a function. Perhaps I was too lazy and should have said "extrinsically identical _implementations_ of some algorithm". It is true that algorithms are by most definitions (I like Turing's) necessarily more abstract than the computational mechanisms we use to reify them, but it didn't seem like a crucial failure to not be pedantic about this distinction. Perhaps it was. Hopefully subsequent articles will benefit from your points. Thanks very much for the feedback!
- j2kun 11y ago
  I think you may be still seriously confused by the definition of Kolmogorov complexity. It's not a fine distinction I'm trying to make, but rather that your definition has a type error! You should think hard about how Kolmogorov complexity (which is defined for strings) can make sense when you try to extend the definition to algorithms in the way you want. They way you've done it is not consistent from what you've written. I suggest you read a few more tutorials on Kolmogorov complexity.

chriswarbo 11y ago

As others have pointed out, the author is confusing a few ideas. First of all, Kolmogorov complexity talks about the output from programs at a "higher-level". For example, to define the Kolmogorov complexity of plain text, we must talk about programs which output text. To define Kolmogorov complexity of, say, Ruby code, we must talk about programs which output Ruby code. And so on. The author mixes up the complexity of the text (eg. in the 3 line example) with the complexity of the code. These are two different things: the complexity of the text depends on the shortest program which outputs that text; the complexity of the code depends on the shortest program which outputs that code. Secondly, writing different programs with the same output doesn't change the Kolmogorov complexity; it merely improves an approximation (since Kolmogorov complexity is undecidable, we must approximate it). The author also uses the word "count" when talking about these approximate numbers, which I think is better than calling them "complexity". A couple more points about the author's argument: 1) When comparing different languages, like Ruby and Python, it might be nice to point out that the complexity can only change by a constant amount. This is because, in the worst possible scenario, we can write an interpreter for the other language. For example, if we use Python as our meta-language, we can denote the complexity of some text T as P(T); if we switch to using Ruby instead, the complexity R(T) <= P(T) + I, where I is the complexity of a Python interpreter written in Ruby. Since I doesn't depend on T, it is a constant, and therefore the choice of language becomes less important as the complexity of T increases. 2) Using Kolmogorov complexity as a benchmark doesn't seem like a great idea to me. It's true that repetition gets eliminated, eg. using loops, but it can also lead to really bizarre things, like crazy integer arithmetic which just-so-happens to produce the correct ASCII characters. Code becomes shorter, but after a certain point it can get unintelligible. In effect, pursuing Kolmogorov complexity means trying to compress your source code. Eventually you'll end up with something like this: def decompress(str): # Insert crazy, program-specific arithmetic here eval(decompress('!"£$%^&*()"£$%^&*(!"£$%^&*')) In particular, code which approaches the limit of Kolmogorov complexity becomes incredibly inter-dependent, lacks all modularity and loses the ability to make incremental changes (making small changes in a compressed encoding leads to large changes in the output). Just look at http://codegolf.stackexchange.com http://codegolf.stackexchange.com for example ;)

jnape 11y ago