The length (in bits) of the shortest effective description or program that, when run on a fixed universal Turing machine, outputs a given finite string, considered up to an additive constant depending on the choice of universal machine.

Principle

Use the minimal description length on a universal reference machine as an objective measure of the algorithmic information content and randomness of an individual finite object.

Demonstration

For the binary string S = '0101010101' a short program that outputs the repeating pattern has small Kolmogorov complexity, whereas for a string R produced by fair coin flips with no short pattern any program producing R is about as long as R itself; moreover Kolmogorov complexity is not computable in general, so only upper bounds can be produced by providing concrete programs.

Misapplication

Treating Kolmogorov complexity as a computable quantity for arbitrary strings, or equating it directly with Shannon entropy of a distribution without accounting that Kolmogorov complexity is a property of single objects and depends on the choice of universal machine only up to additive constants.

Consequence

Correct use gives an invariant (up to additive constant) classification of strings by compressibility, formalizes the notion of randomness for individual objects, and explains limits on algorithmic compression and the existence of incompressible strings.

Reversal

If one inverts the viewpoint and asks for maximal description length rather than minimal, one focuses on the notion of incompressibility: most strings of a given length have Kolmogorov complexity close to that length, so the reversed statement highlights typicality rather than compressibility.

Boundary

Definition applies to finite strings relative to a fixed universal Turing machine; it is only defined up to additive constants, is not computable in general, and does not directly quantify average-case or distributional information unless combined with probabilistic models.

Semantic Tension

Tension exists between Kolmogorov complexity (a property of single finite objects, noncomputable, machine-dependent up to constants) and Shannon entropy (a computable, statistical measure of random variables); they can coincide under stochastic process limits but serve different roles.

Synthesis

Kolmogorov complexity unifies algorithmic description length and a formal notion of randomness by taking the length of the shortest program on a fixed universal machine as the canonical measurement of how much information an individual finite string contains, while acknowledging machine-dependence and incomputability.