Possibility before probability

The combinatorial approach starts with a finite set X containing N possible values. Before a value is specified, the freedom is H(x)=log₂N. Learning that x=a removes that freedom. A binary code needs at least the ceiling of that logarithm in the worst case, because b bits distinguish at most 2^b alternatives.

This definition needs no claim that the alternatives are equally probable. They are simply allowed. Kolmogorov stresses this logical independence because probability language can hide a modelling choice. A grammar may admit a family of sentences without assigning a credible chance to every member. A specification may permit many designs even when no random process samples them. Counting the admissible region is already a substantial mathematical problem.

Constraints shrink the set. If a message alphabet has s symbols and only sequences satisfying a frequency constraint are admissible, one should count those sequences rather than all sⁿ strings. For long messages the logarithm of that constrained count approaches a rate familiar from entropy. Yet the route is different: the starting object is a set cut out by rules, not a distribution assumed over its members.

Kolmogorov's language examples make this distinction concrete. Grammatical correctness permits far more texts than literary acceptability. Meter and rhyme consume some freedom while residual lexical freedom makes a poem possible. The numbers quoted in the article are historically specific estimates, not modern measurements to repeat uncritically. Their conceptual role is durable: information depends on which constraints define the admissible field.

The article also builds a conditional combinatorial quantity. Let X and Y be finite sets, and let U contain the possible pairs rather than all of X×Y. Once x=a is known, only a subset Y_a remains possible. Its conditional entropy is H(y|x=a)=log₂|Y_a|. The information supplied by a about y is the reduction log₂|Y|−log₂|Y_a|. This quantity varies with the observed value a. It describes how a constraint slices a relation, not how surprising a was.

Consider 64 possible destinations and a badge that reveals which of four equal zones contains the destination. Before seeing the badge, six bits select a destination. Afterwards, four bits select one of the sixteen locations in that zone. The badge supplies two combinatorial bits about the destination. If zones have unequal sizes, different badge values supply different amounts. No probability is needed to state that a small fibre removes more possibilities than a large one.

This relational framing anticipates the paper's algorithmic move. In both cases, information is a reduction produced by a condition. The combinatorial version subtracts logarithms of set sizes. The algorithmic version subtracts shortest programme lengths. Their resemblance is instructive, but they are not formally identical: one needs a declared possibility relation, while the other searches effective transformations in a programming method.

A distribution adds expectation

The probabilistic approach gives each value x a probability p(x). Its entropy is H(P)=−Σ p(x)log₂p(x). This is an average number of bits before the outcome is known. It weights common and rare outcomes differently and supports conditional entropy, mutual information and channel capacity. Those relationships make it richer than bare counting when the probability law is defensible.

If the distribution is uniform over N values, probabilistic entropy equals log₂N. Otherwise it is lower. Concentrated mass reduces expected surprise because a short code can be reserved for common outcomes. The combinatorial ceiling remains a worst-case count of admissible alternatives; Shannon entropy becomes an average cost under a stated law.

Kolmogorov draws a sharp boundary around the natural use case. Probabilistic information works for bulk traffic containing many unrelated or weakly related messages that obey stable laws. Empirical frequencies can stand in for probabilities when mixing is sufficiently rapid. A flow of telegrams through a channel fits that picture better than a unique novel treated as one draw from an imaginary distribution over all possible novels.

Pointwise probabilistic information between particular values can even be negative: seeing x may make a particular y less likely. The expected mutual information remains non-negative and symmetric. This difference matters. A local observation can mislead about a specific outcome while the relation between variables remains informative on average. “Information” changes grammatical role when one moves from an event to an expectation.

The pointwise quantity can be written i(x:y)=log₂[p(y|x)/p(y)]. Suppose rain has prior probability 0.4, but after a particular forecast symbol it has conditional probability 0.1. For the event “rain”, that symbol contributes log₂(0.1/0.4)=−2 bits. It steers belief away from the event that later occurs. Another symbol may contribute positive information, and averaging across joint outcomes yields mutual information. Kolmogorov calls attention to this local negativity because the combinatorial reduction cannot be negative when conditioning only removes admissible possibilities.

Expected mutual information is symmetric because it measures average dependence in the joint law. The conditional quantities used to calculate it need not look symmetric at each observation. This distinction prevents a common mistake: applying an average theorem to a singular realised pair. A distribution can justify a symmetric expectation while one event changes odds in one direction and another changes them differently.

The singular-object problem now becomes unavoidable. To ask for the entropy of one completed novel, we must first choose a distribution over novels or posit a stochastic process over its parts. Either choice may illuminate a textual question, but neither is supplied by the object alone. The algorithmic approach does not deny those models. It gives a different answer whose reference is an effective description language rather than a probability law.

The individual object enters

Kolmogorov's central complaint is not that probability is defective. It is that many questions concern one individual object and lack a credible ensemble. How much information does a particular map carry about a particular region? How much hereditary information is embodied in a particular form? How much structure belongs to one fixed text? A probability distribution over counterfactual maps, organisms or novels may be unavailable or arbitrary.

The algorithmic answer begins with an index domain: a countable collection of objects that can be encoded by finite binary strings. A programming method A is a partial recursive function. Given programme p and condition x, it may return y, run forever or remain undefined. Relative complexity is

K_A(y|x)=min{|p| : A(p,x)=y}.

Read the formula operationally. Place x on an auxiliary tape. Search for the shortest programme that makes method A emit y. Its bit length is the remaining description burden. Absolute complexity is the special case with no useful condition, written here as K_A(y). The paper uses its own indexing conventions; modern textbooks often streamline the notation without changing the core question.

The word “shortest” is doing two jobs. It refuses to equate information with the size of a supplied file, because a bloated file may have a short generator. It also refuses to choose one clever explanation in advance. Every effective programme competes. A literal print programme always supplies an upper bound, while a loop, formula, lookup table or transformation from x may do better.

Kolmogorov spends real effort specifying the domain on which those programmes operate. Each object receives a finite binary index. The indexing is one-to-one, effective transformations of indices are required, and ordered pairs must also belong to the domain with effectively constructible indices. These conditions prevent the notation from hiding non-effective naming tricks. If one were allowed to assign a one-bit private name to whichever object happened to matter, description length would record the naming scheme's favouritism rather than discover structure.

The domain may be embedded in a larger domain, and the indices may be replaced by another effectively intertranslatable system. Complexity then changes only within a bounded additive term. This precursor to invariance matters because the “object” could be a binary string, integer, finite table, text or paired observation. Their surface types differ, but effective indexing allows one universal method to act across them without granting exact equality between encodings.

Partial recursiveness introduces a further discipline. A programme is permitted to be undefined for some inputs. This is necessary for universality: general computation includes procedures that loop. Relative complexity is infinite under a method if no programme produces the target from the condition, although an optimal universal method can always use a literal description and is therefore finite on the intended indexed objects. The distinction between “not yet produced” and “will never be produced” is exactly what later blocks computation of the minimum.

Conditional complexity makes shared structure visible. If x is an earlier edition and y differs in twelve locations, a patch may describe y cheaply from x. If x is unrelated noise, it provides no comparable saving. The relevant relation is computational: can an effective transformation exploit x to produce y?

The universal method pays a fixed translator bill

A definition tied to one programming language seems arbitrary. One language might have a primitive command for chessboards; another might require a loop. Kolmogorov's fundamental theorem limits this dependence. There exists an asymptotically optimal partial recursive method A such that for every other method q,

K_A(y|x) ≤ K_q(y|x) + C_q.

The proof architecture is a universal interpreter. Give A a fixed index identifying q, followed by q's programme. The interpreter simulates q on x. The index and decoding convention form the constant C_q. They depend on the rival method but not on x or y.

If both A₁ and A₂ are optimal, each can simulate the other with fixed overhead. Their complexity assignments differ by at most a constant. This is the invariance theorem's practical promise: once objects are large, a fixed compiler header should not dominate a description that spans thousands or millions of bits.

The proof can be traced in four moves. First, enumerate partial recursive methods by finite indices. Second, construct a universal partial recursive function that accepts an index and an ordinary input. Third, package a rival method's index with its programme using an effective pairing convention. Fourth, let the universal method decode that package and perform the rival computation. For a fixed rival, only its programme varies across targets; the method index and wrapper stay fixed. Their combined length is the simulation constant.

Notice what the proof does not inspect. It does not ask whether the rival is elegant, fast or commonly used. It does not compare the outputs statistically. It needs only effective simulation. The result is therefore strong across programming conventions and silent about practical overhead. An interpreter can be fixed yet enormous, slow or perversely designed. Asymptotic optimality controls programme length, not engineering quality.

The promise is asymptotic. For a four-bit string, a 600-bit interpreter header is absurdly larger than the object. Kolmogorov explicitly calls such small comparisons meaningless and designs the measure for quantities large enough that the constant is negligible. Claims that one short slogan, password or tiny data record has an exact Kolmogorov complexity confuse a theorem about bounded disagreement with a canonical numerical scale.

Kolmogorov then defines the information supplied by x about y as

I_A(x:y)=K_A(y)−K_A(y|x).

The equation prices the saving. Describe y from nothing useful; then describe it with x available. The reduction is the algorithmic information that x conveys about y. It is bounded below by a negative machine constant because a programme can always ignore x. Giving the target itself as condition leaves only a fixed “copy input” instruction, so K(x|x) is bounded and self-information approximates K(x).

The form in the 1965 paper is directional. It asks how much x shortens the description of y. Later algorithmic information theory develops symmetry results with additional logarithmic qualifications and refined complexity conventions. Those later results should not be silently substituted here. In the primary construction, direction remains visible because K(y|x) and K(x|y) can differ substantially for finite objects.

For example, let x be a long database and y one row selected by a short index. Given x, the row is easy to produce. Given that row, reconstructing the entire database is usually hard. Thus x may convey most of the algorithmic information needed for y, while y conveys little of what is needed for x. The asymmetry reflects containment of effective structure, not causal direction or semantic importance.

A finite description-language explorer

The bench below searches a deliberately small language: literal printing, repetition of short blocks, all-zero or all-one runs, and patches from a supplied helper string. It reports the shortest description it finds under two artificial machines with different syntax overheads. This is an executable illustration of upper bounds and conditional savings. It is not a universal programming system, cannot compute K, and cannot certify that a string is random.

Interpretation boundary. A positive saving means this finite language found a shorter route using the helper. Zero saving means only that its tiny candidate set found none. Neither outcome establishes true algorithmic information, exact complexity or statistical randomness.

The number no compressor can certify

Kolmogorov makes noncomputability part of the definition's explanation. Partial recursive programmes need not halt. Suppose an algorithm claimed to return exact K(y). To certify that a candidate of length m is shortest, it would have to exclude every shorter programme. Some will halt after enormous delays; others never halt. A general certificate separating those cases would decide the halting problem.

A compressor therefore gives an upper bound. If it encodes y in 700 bits, then the complexity under a suitable decoding convention is at most the compressor, metadata and 700-bit payload cost. If the compressor fails and stores the file literally, nothing follows about a better programme in another language. “Incompressible by gzip” is a property of a tool and file format, not a theorem of algorithmic randomness.

A useful semi-decision procedure still exists. Dovetail all programmes: run the first for one step, the first two for another step each, then the first three, and so forth. Whenever a programme halts with output y, record its length and improve the current upper bound if it is shorter. This process will eventually discover every halting description. It may keep improving forever, and it has no general stopping signal saying the present winner is globally shortest.

The one-sided character is essential. Complexity is approachable from above by successively better descriptions, not computable by a total procedure that knows when the optimum has arrived. Practical compression inherits the constructive half and abandons exhaustive universality. It searches a designed family quickly, which makes its output useful while weakening any claim about the unreachable minimum.

The second boundary is reference dependence. Invariance says that optimal machines disagree by a bounded amount. It does not identify the amount, prove that it is small for a chosen object, or nominate a unique reasonable machine. Kolmogorov hoped reasonable variants would differ by hundreds rather than tens of thousands of bits for large objects. That is an interpretive expectation in the paper, not a derived universal calibration.

The third boundary is time. A tiny programme might enumerate proofs or simulate a physical system for longer than the age of the universe before printing y. Plain description length still calls it simple. Kolmogorov closes by proposing a complexity K_t(x) constrained by permissible computational difficulty t. Removing the time bound recovers the earlier minimum. The article does not develop the resource-bounded theory, so modern results must remain later work.

This creates a useful triangle. Literal size measures storage now. Kolmogorov complexity measures shortest effective origin without a time price. Resource-bounded complexity asks for the shortest description that finishes within a budget. A practical compressor lives in the third corner, yet typically explores only a small family of algorithms. Confusing the corners produces both exaggerated claims and unfair dismissals.

The fourth boundary is representation. Objects enter the theory through indices. A computable recoding changes complexity by no more than the cost of translating that representation, but a representation can expose or conceal regularity at the scales that matter for finite data. A bitmap, a vector drawing and a verbal description may encode the same scene with different accessible structure.

The theory also avoids semantic judgement. A random-looking string may be the digits of a deep mathematical constant; a meaningful paragraph may be algorithmically complex if no shorter effective rule exists. Complexity measures shortest effective description, not importance, beauty, truth, usefulness or conscious meaning. Kolmogorov's literary examples explore description and conditional prediction; they do not reduce interpretation to bit count.

These boundaries make the central distinction professionally useful without turning it into a universal score. When someone asks whether a dataset, model or explanation “contains more information”, first identify the object being quantified. Are we counting permitted states, averaging under a distribution, measuring a discovered code, or reasoning about an unreachable shortest programme? Different answers are not competitors until their question and reference conditions match.

Why almost every member of a simple large set is incompressible

The paper's concluding bridge to randomness begins with a simply described finite set M of N objects. There are fewer than 2^k binary programmes shorter than k bits. Therefore fewer than that many members can have descriptions below k, even before accounting for programmes that fail or collide. Set k=log₂N−c. At most a fraction 2^−c of the set can be compressed by c or more bits.

So almost all members of a large, simply specified set have complexity close to log₂N. This counting argument does not require sampling every member or computing any member's exact complexity. It proves abundance while leaving identification difficult. We know incompressible strings exist in overwhelming numbers, yet cannot generally certify a chosen long string as one of them.

Put numbers on the census. Among all 2^1,000 strings of length 1,000, fewer than 2⁹⁸⁰ can have programmes shorter than 980 bits. Therefore fewer than one in 2²⁰, about one in a million, can save more than twenty bits under a fixed method. This conclusion counts descriptions, not empirical frequencies from a generator. Collisions and non-halting programmes only reduce the number of objects reached by short programmes.

The phrase “a simply described set” carries an assumption. If specifying the set itself requires a vast programme, membership can import hidden information. Kolmogorov requires the set's description to be negligible compared with log₂N. Randomness is therefore relative to a structured population whose boundary is cheap to state. A hand-picked singleton is maximally selective but provides no useful incompressibility theorem because describing the set already describes its only member.

Kolmogorov's 1963 work on random-number tables is the paper's cited predecessor. Chaitin's 1966 programme-size analysis and Martin-Löf's 1966 effective tests then sharpened different sides of algorithmic randomness. The familiar later equivalence between incompressible prefixes and passing effective null tests is not proved in this 1965 article. Reading history backwards would make its compact final paragraph appear to contain a mature theory it only helped set in motion.

The relation to Solomonoff is equally precise. Solomonoff weighted all programmes to predict a continuation; Kolmogorov minimised programme length to quantify an individual object and a conditional relation. Both rely on universal computation and confront machine dependence and noncomputability. Summing descriptions and selecting the shortest description are connected but distinct operations.

From prediction to description, then complexity

Paper 0006 remains in Stage S0, module S0M1: Computability, algorithms and information theory. Church and Turing supplied the boundary of mechanical procedure. Shannon showed how probability laws determine compressible rates for message ensembles. Solomonoff made universal descriptions into predictive weights. Kolmogorov now asks what can be said about one individual object and one effective relation.

The paper introduces three durable separations. Set size is not expected uncertainty. Expected uncertainty is not individual description length. Short description is not feasible reconstruction. Those distinctions later support complexity theory, learning theory, randomness, model selection and scientific explanation, but the 1965 result itself is narrower: definitions, an optimality theorem, and candid limits.

The strongest immediate successor is Gregory Chaitin's 1966 “On the Length of Programs for Computing Finite Binary Sequences”, which develops programme-size measures with explicit machines. Stephen Cook's 1971 paper should follow because it changes the question from whether a short description exists to how computational resources classify problems. Chaitin's 1975 information-theoretic formulation then clarifies the formal analogy with classical information theory.

Six ways to retrieve the argument

Information begins by naming its reference class

Kolmogorov's article lasts only a few pages, but it changes the grammar of information. The older approaches quantify a freedom or uncertainty supplied from outside the realised object. The algorithmic approach lets the object participate through its shortest effective description and lets another object participate through conditional savings. The resulting number is relational twice over: relative to a programming method and, in conditional form, relative to available data.

The fundamental theorem prevents that relativity from becoming complete arbitrariness. Universal methods can translate one another at fixed cost. The same theorem refuses false precision, because fixed does not mean zero and finite examples may be smaller than the translator. Noncomputability prevents a shortest-programme oracle. Runtime blindness keeps descriptive simplicity separate from practical ease.

The durable lesson is diagnostic. Before measuring information, identify the alternatives, probability law, individual object, condition, description language and resource budget. Once those are visible, apparent contradictions dissolve into different questions. When they are hidden, a bit count can look exact while answering nothing in particular.

Continue through the sequence