Kolmogorov complexity

For a finite binary string x and a fixed universal Turing machine U, its Kolmogorov complexity K_U(x) is the length, in bits, of the shortest program p for which U outputs x. The choice of machine affects the exact value, but the invariance theorem says that the values for different universal machines differ by at most an additive constant independent of x. Consequently, comparisons for long strings are robust to the choice of a reasonable reference machine, while the constant may matter for short strings.

A string with a concise pattern can have a short program: for example, a long repetition of a small sequence can be generated by describing the repeated unit and its count. A string with no shorter effective description than listing its bits has complexity close to its length. Kolmogorov complexity therefore provides a theoretical measure of how much a particular object can be compressed by a general description, rather than measuring the uncertainty of a random variable as Shannon entropy does.

There is no general algorithm that computes the exact Kolmogorov complexity of every finite string. A natural strategy would run possible programs and identify the shortest one that outputs the target string, but some programs never halt; there is no general procedure for deciding which programs will eventually halt. The halting problem thus prevents a complete search from certifying that a shorter description does not exist. Practical compression tools can produce descriptions, but their outputs do not in general establish the exact Kolmogorov complexity.

Algorithmic information theory studies Kolmogorov complexity alongside algorithmic probability and formal notions of randomness for individual strings. In this setting, a string is regarded as algorithmically random when it has no substantially shorter effective description, subject to the chosen formal definition. These ideas support theoretical work on information, randomness, compression and induction. They should not be confused with Shannon information: the two approaches address related but distinct questions, with Shannon theory focusing on probability distributions and communication, and Kolmogorov complexity on individual objects.