Burton Rosenberg writes:
> There is the concept of Kolomogorov complexity, the size of the
> smallest algorithm that can generate the message. A perfectly
> compressed message would have Kolomogorov complexity
> equal to itself.
>
> Kolomogorov complexity does have a freedom in its definition,
> but the exciting thing is that any two definitions will differ only
> by a constant.
Yes, the freedom is that the complexity is defined only with respect to a
particular Universal Turing Machine. For any given string you can find
a UTM which compresses it as small as you like, down to a single bit.
This makes it useless as an "absolute" definition of complexity in the
present context. (Also as Nick Szabo pointed out it is uncomputable
due to the halting problem.)
