How Accurate Is Kolmogorov Complexity?
Just how accurate is Kolmogorov Complexity as a measure of complexity?

Well, it is fairly intuitive that, given a specific language or method of representation, the size of the smallest representation of a given string is unique. The question is: does this apply to all languages at once? In other words, does a given string have some kind of intrinsic minimum size based on the contents of that string?

Kolmogorov's fundamental theorem states that there exists a language A such that, for any language B, there exists a finite value C such that given any string x, KC_A(x) <= KC_B(x) + C.

It turns out, after a short thinking excercise, that any efficient language, that is any language that does not "waste bits", meets the requirements to be A, i.e. A is not unique. So, the KC of a string under any two languages differs at most by a finite amount, independant of the string (but dependant on the two languages)

Apparently, based on this, Kolmogorov (and many others) conjectured that since the KC of a string under any language is only off by at most a finite amount, there must be some universal value that is being approximated here, and C in Kolmogorov's inequality is like the margin of error of that approximation. The conjecture suggests a Magical perfect language M such that KC_M(x) = intrinsic information in x.

So, if we choose a language, and somehow find the KC of a string under that language, we have an approximation of that string's intrinsic information content. But, how accurate is that approximation? What is the average margin of error?

It turns out that given an efficient language P, and a string x, we can create another efficient language Q such that KC_Q(x) = KC_P(x) + Z, where Z is an arbitrarily large (but finite) positive number, or an arbitrarily large finite negative number up to (but not including) -KC_P(x).

Now, let P = M. The error in the approximation, Z, can be arbitrarily positively large, and negatively large only up to -KC_M(x).

So, what is our average error, or average Z, over all x? Well, in the set of all languages, all the possible constructed Q's are present. In order to get an average, we need to choose a distribution for the languages. Call this p. The average error is thus:

Sum over all Q and x of p(Q) * ( KC_Q(x) - KC_M(x) )

But what does this turn out to be?

The answer is in two parts:

1) We can choose some mostly uniform-looking distribution, conjecturing that this is somehow an unbiased or universal distribution. Now, for every string x there exists languages Q such that Z is as large as we want positively, but negativily only up to -KC_M(x). So, the average error is unboundedly positive. The average error in measuring intrinsic information content with Kolmogorov Complexity would be undefined. In other words, it would not a measure of it at all.

2) We can choose a distribution such that the average language converges to some language, and thus the average error converges to some finite value. But, the problem here is that we can choose any language as the point of convergence, and construct a distribution to "prove" that it is M! (This is done by weighting the languages closer to the chosen M more heavily than those further from the chosen M)

Furthermore, we cannot assume that any particular language is close to M, since M is what we're trying to measure with that language! It would be like picking up a twig and saying, "Hmm. I have no idea how long a yard is, but I can assume that this twig is close to a yard and thus get a reasonable approximation of a yard."

Basically, any distribution p that we choose will reflect the bias in our choice.

The implication is this: Kolmogorov's theorem (KC_A <= KC_B + C) does NOT suggest the existance of intrinsic information content of a string.