Understanding Kolmogorov Complexity and Information
In Kolmogorov complexity, the “information content” of an object/string is defined as the length (in bits) of the shortest program that produces the object and halts —i.e., the size of the shortest description/program...
In Kolmogorov complexity, the “information content” of an object/string is defined as the length (in bits) of the shortest program that produces the object and halts —i.e., the size of the shortest description/program for it.[:cite[1]{ln=1}] Concretely, if a string has regularities, it can be generated by a much shorter program than writing it out directly, so it contains less information in this sense (it’s “compressible”).[:cite[2]{ln=3}] If a string lacks such regularities, no significantly shorter program exists, so it has high information content.[:cite[2]{ln=3}] The key point is that this definition yields an objective measure (up to an additive constant) rather than depending on arbitrary human choices of encoding detail; for “reasonable” choices of programming languages, the quantity is invariant up to an additive constant, which is why it’s treated as the absolute measure called Kolmogorov complexity .[:cite[2]{ln=1}]