Kolmogorov complexity is the length of the shortest program that produces a specified finite object and then halts, measured relative to a fixed universal computing system. It formalizes the idea that an object is simple when it has a short effective description and complex when no description substantially shorter than the object itself exists. A million repetitions of the same symbol can be generated by a compact instruction; a typical million-bit string cannot. The theory concerns the information content of individual objects rather than only the average information produced by a probabilistic source.
Developed independently through the work of Ray Solomonoff, Andrey Kolmogorov, and Gregory Chaitin during the 1960s, the concept is central to algorithmic information theory. It connects computability theory, randomness, data compression, mathematical logic, and inductive inference. Its defining quantity is not computable in general, but this limitation is itself mathematically productive: it establishes precise boundaries on compression, proofs of randomness, and mechanical discovery of patterns.
Two principal versions are commonly distinguished: plain complexity, usually written , and prefix-free complexity, usually written . Their differences matter in exact theorems about coding, probability, and infinite random sequences. Both describe an idealized minimum description length, not the output size of any particular compression utility and not the computational effort required to generate an object.
Historical origins and intellectual setting
The background to Kolmogorov complexity includes two distinct developments: the mathematical theory of computation and the probabilistic theory of information. In 1936, Alan Turing introduced a general model of effective computation, now called the Turing machine, and established fundamental limits on mechanical procedures. A universal Turing machine can simulate other machines from encoded descriptions. This universality made it possible to treat a program itself as a finite description of an object.
Claude Shannon’s 1948 work established information theory as a mathematical study of communication. Shannon’s entropy measures uncertainty associated with a probability distribution, and his coding theorems relate that uncertainty to average message length. This left a different question open: how much information is contained in one particular string, independently of a previously specified source distribution? Two strings can have the same length and the same numbers of zeros and ones while differing greatly in the simplicity of their arrangement.
Solomonoff approached this question through prediction and inductive inference. In work published in 1964, following earlier reports, he assigned greater weight to hypotheses generated by shorter programs. The aim was not merely to describe data but to construct a general mathematical account of learning from observations. His approach connected universal computation with probabilistic prediction and became the foundation of Solomonoff induction.
Kolmogorov’s 1965 paper, commonly known in English as “Three Approaches to the Quantitative Definition of Information,” gave a direct formulation of the complexity of an individual object through its shortest algorithmic description. Chaitin independently developed closely related ideas, with papers appearing in 1966, and subsequently explored their implications for randomness and mathematical incompleteness. Their approaches were not identical in motivation, but all replaced an informal appeal to simplicity with a precise measure based on effective descriptions.
During the following decades, the theory acquired several complementary forms. Per Martin-Löf introduced effective statistical tests for random infinite sequences in 1966. Work by Leonid Levin, Chaitin, and others clarified the importance of self-delimiting descriptions, universal probability, and coding relationships. Later research developed algorithmic statistics, information distance, resource-bounded complexity, and logical depth. The subject consequently became more than a formal account of compression: it provided a common language for individual information, randomness, prediction, and the limits of computation.
Universal descriptions, plain complexity, and prefix complexity
Let denote the set of finite binary strings, and let be the length of a string , measured in bits. Fix an optimal universal description machine . The plain Kolmogorov complexity of a string is
The machine must produce exactly and halt. A program that continues indefinitely while printing a sequence beginning with does not qualify under this definition. “Optimal” means that simulates every other effective description system with an additive overhead depending on that system but not on .
The central invariance theorem states that, for any two optimal universal machines and , there is a constant such that
for every . A fixed simulator or compiler supplies the additional description needed to translate one machine’s programs into the other’s. The theorem does not select a uniquely correct machine or make all finite numerical values identical. Rather, it ensures that changing the description language cannot create an advantage that grows without bound as the objects grow.
Prefix-free complexity imposes an additional requirement. For a prefix-free machine, no halting program is a proper prefix of another halting program. Its valid programs therefore form a prefix code, allowing program boundaries to be recognized without an external end marker. For an optimal universal prefix-free machine,
The prefix condition makes program lengths satisfy the Kraft inequality and supports especially clean connections with probability. Plain programs can use their externally supplied length as information; prefix-free programs must encode enough structure to delimit themselves. Consequently,
while a standard converse bound is
for sufficiently large . All logarithms in such coding formulas are conventionally base two.
Finite objects other than binary strings are handled through effective encodings. Integers, graphs, images, and mathematical expressions can all be represented as strings. If two encodings are related by fixed computable conversions, their complexities differ by at most a constant. The same applies to fixed effective operations: for every partial computable function , whenever is defined,
The constant includes a program implementing . This does not say that every informal representation choice is harmless at practical scales: a large fixed constant can dominate short descriptions, and a representation may incorporate substantial background knowledge.
Uncomputability and limits of formal proof
Kolmogorov complexity is a precisely defined integer-valued function, but no algorithm computes its exact value for every input. The obstacle is not simply that exhaustive search would be slow. Programs may fail to halt, so searching through all shorter candidates cannot in general establish that none will eventually produce the desired object. This links complexity to the halting problem, although a direct contradiction also demonstrates uncomputability.
Suppose that a program could calculate exactly. Given an integer , it could enumerate strings in a fixed effective order and select the first string whose complexity exceeds . Such strings exist because there are fewer short programs than strings. Yet would then have a short description: encode , run the assumed complexity calculator, and perform the search. This requires only bits, contradicting for sufficiently large . The argument is a rigorous version of the tension in describing an object as the first one that lacks a short description.
Complexity is nevertheless upper semicomputable. A procedure can simulate all programs in interleaved steps and keep track of the shortest program found so far for each output. Whenever a shorter successful program appears, the current upper bound decreases. Eventually the bound reaches the true value, but there is no general effective signal that this has happened. In particular, an observed failure to discover further compression is not a certificate of incompressibility.
There are corresponding limits on what a fixed formal theory can prove. In a suitable sound, effectively axiomatized theory, there is a bound beyond which the theory cannot prove statements asserting that particular explicitly specified strings have complexity greater than that bound. Otherwise, a short procedure could search the theory’s proofs for such a statement and output its string, contradicting the claimed lower bound. This phenomenon is associated especially with Chaitin’s incompleteness theorem. The threshold depends on the theory, the chosen universal machine, and the exact formalization.
These limitations do not prevent proofs that high-complexity objects exist, nor do they prevent complexity arguments from proving ordinary mathematical theorems. Counting establishes the existence of incompressible strings without identifying each one effectively. Likewise, restricted description languages or bounded execution times can yield computable variants. The crucial distinction is between proving general structural facts and possessing a uniform procedure that certifies the exact unrestricted complexity of arbitrary individual data.
Incompressibility and the counting method
The most immediate fact about Kolmogorov complexity is that most sufficiently long strings are incompressible. There are binary strings of length , but only
binary programs shorter than . Each program produces at most one output. Therefore fewer than strings of length can have plain complexity below . For a uniformly chosen -bit string ,
For example, fewer than one in length- strings can be compressed by more than 20 bits in this precise description-length sense, apart from the chosen strictness convention at the threshold.
Every string also has a literal description. A plain program can contain the string itself together with a fixed instruction to output it, giving
For prefix complexity, a general bound is
because the literal data need a self-delimiting length or an equivalent boundary convention. Thus the claim that random-looking strings have complexity “about their length” is correct at leading order, but exact statements must distinguish plain from prefix complexity.
Highly regular strings behave differently. If denotes zeros, then : a short program prints zeros times, and conversely the length of the output recovers . For computable infinite sequences such as the binary expansion of , the first bits have complexity at most . Such prefixes may exhibit complicated local patterns and resist ordinary compression tools, yet their unrestricted description complexity is small.
The incompressibility method turns these observations into proofs. A typical argument selects an incompressible object and shows that an alleged exceptional property would allow it to be described too briefly. For instance, a very large imbalance between zeros and ones reduces the number of candidate strings. Given the imbalance and a string’s index among the candidates, the string can be reconstructed with fewer bits than a completely unrestricted length- string would require.
The same strategy applies to repeated substrings, graph properties, and lower bounds on computational tasks. It can replace lengthy average-case counting arguments with a description argument about one representative incompressible object. Careful accounting remains essential: the description must include lengths, parameters, reconstruction instructions, and any auxiliary choices. Omitting these costs can turn a plausible compression argument into an invalid one.
Entropy, coding, and universal probability
Kolmogorov complexity and Shannon entropy answer different questions. Entropy is a property of a probability distribution; complexity is a property of an individual object relative to a universal machine. If a random variable has probabilities , its entropy is
This gives an average coding benchmark, not an intrinsic assignment of descriptive complexity to each outcome. An object can have low probability under one distribution and still possess a very short program.
The two quantities meet through coding theorems. For a computable distribution , descriptions based on the code lengths give an upper bound of the form
Here denotes the length of a program describing the distribution in a suitable effective representation. The bound charges for the model as well as the data. It explains why a highly elaborate distribution that assigns probability one to a particular string does not automatically establish that the string has a short unconditional description: specifying that distribution may be as difficult as specifying the string.
For finite distributions with effectively supplied probabilities, the expected prefix complexity conditional on the distribution is close to entropy:
with a fixed representation and coding convention. Without supplying the distribution as background information, a corresponding upper bound includes its description cost. Ordinary methods such as Huffman coding and arithmetic coding make related model-dependent coding principles constructive, but they do not compute Kolmogorov complexity.
A deeper relationship uses universal algorithmic probability. For an optimal universal prefix-free machine , define the discrete a priori semimeasure
It is a semimeasure because some program probability may never produce a halting output. It is lower semicomputable: simulated programs contribute probability mass whenever they halt. Universality means that multiplicatively dominates every lower semicomputable discrete semimeasure, with a constant depending on the semimeasure being dominated.
The algorithmic coding theorem, associated with Levin, states
Although sums contributions from every program producing , its negative logarithm agrees with the shortest-program length up to a constant. This supplies a precise bridge between description length and universal probability. It must be distinguished from the related semimeasures used for continuing infinite sequences in Solomonoff prediction, where probability is assigned to all outputs beginning with a specified prefix.
Finite incompressibility and infinite randomness
For a finite string, randomness is necessarily relative to a coding convention, a length, and an allowed deficiency. A string can be called incompressible to within bits when, for example,
This does not make finite randomness an observable physical property independent of representation. A specially chosen universal machine may contain a short dedicated instruction for a particular string. The invariance theorem limits the resulting change by a machine-dependent constant, but does not remove that constant from small examples.
For infinite binary sequences, a stronger theory is available. Martin-Löf randomness formalizes the requirement that a sequence avoid every effectively describable statistical exceptional set of measure zero. A Martin-Löf test is a uniformly effectively enumerable sequence of open sets whose fair-coin probabilities satisfy . A sequence fails the test if it belongs to every . Random sequences pass all such effective tests.
The Levin–Schnorr theorem connects this statistical definition to prefix complexity. An infinite binary sequence is Martin-Löf random for the fair-coin measure if and only if there is a constant such that
for every , where is its first bits. The use of prefix complexity is important: replacing with plain complexity does not give the same characterization. Plain complexities of successive prefixes have unavoidable oscillations.
This notion implies familiar statistical properties. Martin-Löf random sequences have limiting frequency one-half for each bit and satisfy effective versions of many probability-one laws. The converse fails: correct frequencies or normality do not suffice. Some computable sequences are normal, meaning that every finite block occurs with the expected limiting frequency, but no computable infinite sequence is Martin-Löf random. A short generator can describe arbitrarily long prefixes once their length is supplied.
An especially important example is Chaitin’s halting probability,
for an optimal universal prefix-free machine. The real number is lower semicomputable but noncomputable, and its binary expansion is Martin-Löf random. Given its first bits, together with the relevant machine conventions, halting can be decided for all programs of length at most . This joins maximal effective randomness with highly structured information about computation: incompressibility does not mean the absence of mathematical significance.
Conditional complexity and shared information
Conditional complexity measures the description length of an object when another object is supplied without charge. For a universal machine with an auxiliary input,
The condition may be a string, an integer, a model, or a tuple encoded by a fixed effective convention. A digital image might have a large unconditional complexity but a small conditional complexity given a nearly identical image, because a short program can describe only the differences. The conditioning information is not counted in the program length.
Several basic identities express this interpretation. For example,
If and are encoded as an ordered pair, their joint complexity describes the information needed to reconstruct both. A particularly precise prefix-complexity chain rule is
Supplying the integer matters. Removing it usually requires a logarithmic correction rather than merely a constant. Equivalent formulations can use a canonically selected shortest program for .
Algorithmic mutual information is commonly expressed, up to conventional additive terms, as
It measures the descriptive saving obtained by treating two objects jointly instead of separately. Two copies of the same incompressible string share nearly all their information: one copy plus a short duplication instruction describes the pair. Two independently chosen long random strings, by contrast, normally have little mutual information beyond incidental shared parameters such as their lengths.
This is an individual-object analogue of mutual information in statistics, but it is not the same quantity as a distributional average. It also does not establish causation. Shared information may arise from copying, common ancestry, a common generating rule, or a chosen encoding. Deterministic effective processing cannot create arbitrarily large amounts of new shared algorithmic information: any change must be accounted for by the processing descriptions and the relevant additive terms.
Conditional complexity also motivates information distance. The maximum of the two directional complexities,
measures how much information is needed to transform either object into the other. Normalization by approximately produces a scale-independent dissimilarity with metric-like properties, subject to small additive corrections. These constructions supply an ideal framework for comparing objects without selecting a single application-specific feature representation, although their unrestricted versions remain uncomputable.
Inductive inference and minimum description length
A short description can serve not only as a representation of existing data but also as a hypothesis about how those data were generated. Solomonoff induction formalizes this idea by considering programs running on a universal machine and weighting them according to their lengths. Programs receive weights proportional to , so simpler effective explanations receive greater prior weight. Predictions are formed by combining the contributions of programs consistent with the observed sequence.
The resulting universal sequence semimeasure dominates every computable probabilistic source up to a multiplicative constant. This domination supports convergence results: when data are generated by a computable probability measure, predictions based on the universal semimeasure approach the true predictive probabilities in appropriate probabilistic senses. The constants depend on the description complexity of the source. These are mathematical results about an ideal predictor, not instructions for a feasible universal forecasting system.
The conceptual connection with Bayesian inference is direct. A prior favoring short effective descriptions implements a formal version of simplicity preference. However, universal priors are not uniquely determined at finite scales: they depend on the reference machine, even though universality controls this dependence multiplicatively in probability and additively in description length. Moreover, the universal mixture cannot generally be computed. Its significance is as a limit theory of induction, not as a practical estimator that can be evaluated exactly.
A related but distinct framework is the minimum description length principle, developed by Jorma Rissanen beginning in 1978. In a two-part formulation, a model is selected by minimizing
The first term charges for specifying the model; the second charges for encoding the data under that model. More elaborate models may fit observations better but require longer descriptions. The principle therefore gives an explicit accounting interpretation of the trade-off between model fit and model complexity. Modern formulations include universal coding and normalized maximum likelihood, not only literal two-part program descriptions.
In machine learning, this perspective helps explain why model fit alone is insufficient. A model that memorizes training data may give those observations a short conditional encoding while requiring a large model description. Yet low training description length does not by itself guarantee generalization under arbitrary changes in data generation. Conclusions depend on the hypothesis class, coding scheme, sampling assumptions, and how side information is treated. Kolmogorov complexity provides an ideal language for these issues; computable learning methods must adopt restricted models or approximations rather than search all possible programs.
Structure, randomness deficiency, and computational depth
A single complexity number does not separate meaningful organization from accidental detail. A random string has high Kolmogorov complexity because it resists compression, yet it may contain little reusable structure. A highly organized object can also require a long description, particularly when its structure is extensive. Algorithmic statistics addresses this distinction by asking how an individual object can be represented as a simple model together with a typical residual.
A basic model is a finite set containing the observed string . The two-part description first specifies , then identifies by its index within the set. Its length is approximately
Here is the length of a program that prints the finite set in a fixed canonical form and halts. A singleton model explains everything but may be as complicated as . The set of all strings of length is simple, but it explains little beyond length.
The trade-off is captured by a structure function such as
It asks how narrowly the data can be located using a model-description budget of at most bits. A related randomness deficiency compares the index length with . If has a substantially shorter description given than a typical member would require, the model has left a detectable regularity unexplained. Definitions using shortest descriptions of the model refine the constant terms in these comparisons.
These ideas lead to algorithmic sufficient statistics and sophistication, which aim to measure the complexity of a model that captures the effective structure without encoding every accidental detail. The significance tolerance is important: changing how much extra total description length is allowed can substantially alter the selected model complexity. There is no unrestricted computable procedure that reliably extracts the uniquely meaningful pattern from every object, and the theory does not identify “meaning” independently of its formal modeling assumptions.
A different distinction is provided by logical depth, introduced by Charles Bennett in the 1980s. At significance level , a typical definition is
A deep object requires a long computation when generated from a description close to shortest. A string can therefore have a short description but great depth if expanding that description requires extensive computation. Conversely, a typical incompressible string can be produced quickly by a near-literal program at a suitable significance level. Complexity measures irreducible description length; depth measures computational history that cannot readily be bypassed without a substantially longer description.
Resource bounds and practical compression-based methods
Unrestricted Kolmogorov complexity ignores how long a program takes to run. A very short description remains short even if its execution requires an impractically large amount of time. This separates the subject from computational complexity, which studies resource requirements as inputs grow. The distinction is visible in a compact program that enumerates an enormous search space before producing its output: descriptive simplicity need not imply computational accessibility.
Time-bounded complexity incorporates a specified execution budget. For a total computable bound , one may define
If no qualifying program exists, the value is taken to be infinite. With an effective finite search bound on program length, bounded execution can be checked exhaustively. In standard machine models, only a bounded amount of input can influence a computation within a fixed number of steps, making such bounded variants effectively searchable. The result is much more sensitive to the chosen machine and simulation costs than unrestricted complexity.
Levin’s time-sensitive complexity uses another compromise, combining length and execution time:
The logarithmic runtime penalty links compact descriptions with efficient search and computation. Other variants restrict space, circuit size, or permissible description languages. Such restrictions are important in cryptography, where a string can be generated by a short program and still be indistinguishable from random to computationally bounded tests. Output from a pseudorandom number generator may have low unrestricted complexity when its seed is short, without thereby being easy to distinguish or predict efficiently.
Practical lossless compression supplies upper bounds rather than exact complexities. If a fixed decompressor reconstructs from a compressed representation , then
with appropriate self-delimiting conventions; the constant accounts for the decoder. Successful compression proves the existence of a short description. Failure by one compressor does not establish that no shorter program exists. A compressor may miss arithmetic regularities, long-range dependencies, or domain-specific structure, and file-format headers can dominate small examples.
One applied construction is the normalized compression distance, commonly written
where is a compressor’s output length and is a suitably encoded concatenation. It approximates ideas from normalized information distance and has been used in clustering documents, biological sequences, music, and other data. Its behavior depends on the compressor’s window size, object boundaries, headers, order effects, and preprocessing; finite implementations need not satisfy ideal metric properties exactly. These methods operationalize a particular compressor’s capacity to detect shared structure, rather than making uncomputable universal information directly measurable.