Invariance Theorem - Informally

Informally

A description language gives us some computational process by which we can transform descriptions of objects into actual objects. The idea behind Kolmogorov complexity is that the complexity of an object is the length of its shortest description in some fixed description language. Unfortunately, the length of the shortest description will depend on the choice of description language.

However, there are some description languages which are optimal, in the following sense: given any description of an object in a description language, I can use that description in my optimal description language with a constant overhead. The constant depends only on the languages involved, not on the description of the object, or the object being described.

Here is an example of an optimal description language. Our descriptions will have two parts:

• The first part describes another description language.
• The second part is a description of the object in that language.

In more technical terms, the first part of a description is a computer program, with the second part being the input to that computer program which produces the object as output.

The invariance theorem follows: Given any description language, our optimal description language is at least as efficient as, with some constant overhead.

Proof: If we have a description in, we can convert it into a description in our optimal language by first describing as a computer program (part 1), and then using the original description as input to that program (part 2). The total length of this new description is (approximately):

The length of is a constant that doesn't depend on . So, there is at most a constant overhead, regardless of the object we're trying to describe. Therefore, it follows that our optimal language is universal up to this additive constant.