What Good Is Kolmogorov Complexity Since It Is Relative?

Question

Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a constant that depends on the choice of that pair. They can't disagree too much because one can always switch over to emulating the other. However, this amount of maximum disagreement can be arbitrarily large.

Given that, of what use is Kolmogorov complexity? I suppose if you have a sequence of bitstrings, then you can talk about the asymptotic growth of the complexity of these bitstrings, and you will know that this is independent of choice of UTM.

But I thought that Kolmogorov was supposed to be meaningful for individual finite strings. But every bitstring can be produced by an arbitrarily small program: imagine a language that functions just like Java but where an empty file produces the bitstring under consideration.

Doesn't this relativity make Kolmogorov complexity basically pointless? I must be mistaken, right?

Answer 1

The relativity is up to an additive constant. Suppose that you express Kolmogorov complexity relative to your favourite universal Turing machine $U$, but I do it relative to my favourite UTM $V$. If the shortest program for $V$ that outputs a string $x$ is $M$, then the shortest program for your machine $U$ can't be any longer than the one that simulates $V$ running $M$, and that has length $|M|+k$, where $k$ is the size of the simulator.

So, yes, you could pick a UTM that has a very efficient coding for some finite set of strings. However, that would increase the length of the coding of at least that the same number of other strings, and we're typically interested in the asymptotic behaviour of infinite families of strings, rather than individual strings.

Answer 2

I think the key point that is missing is that task for infinite families of bitstrings is not that different from fixed bitstrings.

The Kolmogorov Complexity measures the length of your Java code or any other language, it may also measure the compiled program length, which is still relative to architecture and OS. When you imagine a program taking input then you are probably thinking about conditional Kolmogorov Complexity.
The standard KC states that it is the length of a program in predetermined description, it is true that various languages, hardware and software will yield various result, but we are interested in particular configuration to find the minimal description. Taking it to any level, the minimal amount of information needed is the same. The constant that occurs due to invariance theorem is irrelevant for many theoretical aspects, and takes into account the UTM choice, which allows to concentrate on the main problem: how compressible is given bitstring and move on.

For finite amount of bitstrings we are interested in the sum of one programs length and inputs lengths that will recover the original representation, but such program will not be able to produce anything else. Good, it was not the point!

Answer 3

You're not wrong. All that Kolmogorov complexity theory can say is that most strings are incompressible, which is known by simple counting arguments, and is a purely informational, not computational property.

As to which strings are compressible and which ones aren't, this is entirely up to how your particular machine represents the small subset of compressible ones, where the constant matters a lot. What goes into the constant are all the things needed to extract this small special subset and so it ends up being everything about the choice of machine and nothing about the actual string. After all, you do not get something for free (compression) by playing programming games, even with a UTM; you merely move information around, e.g. into the machine's construction.

Since practically we care about compressible strings, not incompressible ones, Kolmogorov complexity theory in the original version is useless.

However, the interpretation of complexity in equivalent computational terms is insightful and has led to other variants of Kolmogorov complexity on constrained machines (not UTM's) that are more practically useful.