# What Good Is Kolmogorov Complexity Since It Is Relative?

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?

• There is a slight refinement here. Not all bit strings are produced by small programs. Your question and this comment wasn't. Nov 24, 2017 at 3:11
• "They can't disagree too much because one can always switch over to emulating the other." - This isn't true either because you'd need to encode when you'd emulate and when you'd not for each string. There is no proof that you even get any agreement on asymptotics. Apr 7 at 0:45

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.

• Thanks for your answer! I understand how Kolmogorov complexity is useful for infinite families. However, I don't understand its utility for individual or a finite number of bitstrings. It feels like your prior belief on what machines are likely could easily be the greatest factor in how complex these bitstrings look to you. Oct 17, 2017 at 21:43
• I do not think that your second paragraph is true. It seems like a description of general compressor which is not the point of KC for finite strings, but the consequence. It describes the application of compressor for fixed values outside domain of inputs.
– Evil
Oct 18, 2017 at 3:48
• @NedRuggeri Can you give an example of Kolmogorov complexity being used to argue about finite collections of strings? Oct 18, 2017 at 7:29
• @Evil OK, maybe not all other strings, but at least as many as you shortened must lengthen. Oct 18, 2017 at 7:31
• arxiv.org/pdf/math/0110086.pdf and maybe paper from Lempel and Ziv from 1976 (researchgate.net/publication/…).
– Evil
Oct 18, 2017 at 8:02

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!

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.

• Can you update your answer with an example of "other variants of Kolmogorov complexity on constrained machines (not UTM's) that are more practically useful"? Multiple examples will be even better. Apr 15 at 1:36