Let's define information content

Let's try to define information content.

Information content of s string x can be defined (as by Kolmogorov, Chaitin, etc) as the size of the smallest program which produces x as output. So, which language (or class of language) should we use?

We only want to include universal languages, so we'll restrict ourselves to languages which can accept a function description and parameters, such that the same function description can be used to compute the function over any set of parameters. We'll use Turing Machines, since everyone likes to use them.

So, we choose a TM which produces F(w) when its input tape contains a description of F and w.

We can use a UTM for this, it turns out. F is thus the description of the TM to be emulated, and w is the initial contents of the tape for the emulation to run on.

It also turns out that for any output U(F,w) there is an equal output U'(F',null) such that the size of F' is equal to the size of F,w. So, for the purposes of information content, we can restrict ourselves to programs which do not take input.

So, now we are only concerned with the following: What is the best way (or class of way) to encode Turing Machines for use in a UTM?

For starters, we'll exclude any encoding which has more than one representation for any given Turing Machine. We only want encodings which have exactly one representation for any given TM.

If we were real smart, we'd also exclude all but one of any set of TMs which produce the same output when given the same input.

Now, we also want our encoding to be instantaneous, so we'll use some sort of full prefix code.

So, we can enumerate our set of all Turing Machines, omit any doubles (where same input = same output), assign weights to the TMs such that the sum of all the weights is 1, and create an instantaneous code based on these weights with, say, Huffman.

So, how do we choose a method of weighting these TMs?

We cannot weight them uniformly. There is an infinite number of TMs, so uniform weighting would result in all weights being 0 and all codes being infinitely long.

Which TMs should be weighted more than others? In the universal sense, there is no justifiable reason for weighting one TM over another, so any choice we make in our weighting method is purely a choice we make, and not universal.

In other words, there is nothing universal telling us to favor one set of weights over another, and thus Kolmogorov complexity is not unique.