Hacker News Reader

Comment by pessimizer | Hacker News Reader

This post is a bit silly. Kolmogorov complexity doesn't have anything to do with computer languages, it has to do with instructions to describe something. The instructions include verysilly, the assembler/interpreter implementation of verysilly, and how to build the computer it's running on.

In that light, the constant factors are still trivial.

View on HN

The major problem with the post is that it does not cover the complexity of the language itself. L(p) should equal to L(d, p) where d is the definition of the language used to write p. So it becomes a whole different question now. And indeed for L(s) where s = (d,p) you can now find the most minimal language definition and an empty p such that it can produce x. K_L(x) = |s| = |d| + |p| And for input receiving programs we need to consider the input as part of the program itself as well.

But those are just formalities, the great beauty of Kolmogorov complexity starts to emerge when you start to consider archive utilities as an approximation for K(x). Think K(x) ~ |Zip(X)| or K(x) ~ |Rar(x)| now you have a real tool to approximate K(x) and guess what it is already installed. Now what about Kd(x,y) = K(x) - K(y)/K(x||y) ~ |Zip(x)| - |Zip(y)| / |Zip(x||y)| It is a distance metric for how entropically far is x from y and that is very interesting and can be very useful for anomaly detection for instance or password strength comparison.

How do you measure the length of the definition of the language used to write p? You just have the same problem all over again, because it depends on the meta-language you use to define your language.

I think the post is correct that we can define a language which makes the algorithmic complexity of a given string zero. This doesn't contradict the invariance theorem, as far as I can tell. The constant c in the invariance theorem

    |K_1(s) - K_2(s)| <= c

will be at least the complexity of the special string in the other language, but it still exists.

If you want to define KC as the minimal length of some set of instructions to describe the string, then you still haven't gotten away from the fact that a common language must still be fixed in advance. You just changed it from a computer language to English (or whatever language your instructions are written in).

Reply on news.ycombinator.com