Andrey Kolmogorov

Andrey Kolmogorov

Mathematician, 1903–1987. Study focus: probability models, description length, and what compression can and cannot establish.

Kolmogorov's 1933 probability framework and his later work on algorithmic information answer different questions. A probability model assigns measures to events. Description complexity asks how short a program can produce a particular object. Confusing them leads to errors such as claiming that a file which a compressor cannot shrink has been proved random.

Historical setting

Kolmogorov entered Moscow University in 1920 and worked across analysis, probability, logic, dynamical systems, and turbulence. His mathematical environment included Nikolai Luzin and Pavel Alexandrov. His 1933 Grundbegriffe der Wahrscheinlichkeitsrechnung organized probability using measure theory. His 1965 paper distinguished combinatorial, probabilistic, and algorithmic approaches to information. Solomonoff and Chaitin also developed algorithmic approaches, so this field should not be presented as a one-person invention. MacTutor biography, original publication record

Probability was already a substantial mathematical subject before 1933. Kolmogorov did not turn mere intuition into mathematics overnight. Nor did his axioms automatically resolve which probability distribution should describe a real experiment. Axiomatization supplies rules for reasoning inside a model; interpretation and evidence connect that model to observations. Vovk and Shafer's historical analysis

Events, measures, and assumptions

A probability space consists of a sample space Ω, a collection F of measurable events, and a measure P. In the usual formulation, F is a sigma-algebra: it contains Ω and is closed under complements and countable unions. Probabilities are nonnegative, P(Ω)=1, and the measure of a countable union of pairwise disjoint events is the sum of their measures.

For an original finite example, toss a fair coin twice independently. Then Ω={HH,HT,TH,TT}, with probability 1/4 assigned to each outcome. Let A mean the first toss is heads, and B mean at least one toss is heads. We have P(A)=1/2, P(B)=3/4, and P(A∩B)=1/2. Therefore P(A|B)=(1/2)/(3/4)=2/3.

Conditioning changes the relevant set of possibilities. The statement that the first toss is heads is more likely after learning that at least one is heads. Independence of the two tosses does not make every event constructed from them independent of every other event. Here A and B are dependent because P(A∩B) ≠ P(A)P(B).

The fairness and independence assumptions did not follow from the axioms. We supplied them. If a process chooses only HH or TT with equal probability, each individual toss is still marginally fair, but the tosses are dependent. P(A|B) is then 1. Model choices change answers even when every model obeys the same axioms.

A program as a description

Fix a universal description machine U. The plain description complexity C_U(x) of a finite binary string is the length in bits of a shortest program that makes U output exactly x and halt. Using a subscript makes the machine choice explicit. A different universal machine changes this measure by at most an additive constant independent of x, but that constant can matter greatly for short strings. Prefix-free program complexity, often written K, is a related but distinct definition. Kolmogorov's algorithmic approach

For a string consisting of one million repetitions of 01, a description can specify a repetition operation, the pair 01, and the repeat count. This gives an upper bound once the instruction format and interpreter are fixed. It does not establish the exact shortest program. A string that looks irregular to a person may also have a short generating rule unknown to that observer.

Description length is not runtime. A short program can take an enormous time to finish. Adding a time bound creates a different complexity measure. Similarly, a practical compressor chooses a restricted family of coding methods. Failure within that family is not a proof of failure for all programs.

Why many strings resist short descriptions

There are 2^n binary strings of length n. The number of binary programs shorter than n-k is at most

1 + 2 + 4 + ... + 2^(n-k-1) = 2^(n-k) - 1.

Each halting program produces at most one output string. Thus fewer than 2^(n-k) length-n strings can have a description shorter than n-k bits. Dividing by 2^n, fewer than a fraction 2^-k can be compressed by more than k bits under this counting convention. For n=16 and k=4, at most 4095 of the 65536 strings have programs shorter than 12 bits. This is an original worked application of the counting argument.

The proof establishes abundance, not an effective certificate for a particular string. It also says nothing about the distribution of files people actually save. Natural-language text and program source are not uniformly selected from all equal-length bit strings.

Why exact complexity is uncomputable

Suppose a total algorithm could compute C_U(x). For any threshold m, a program could search strings in a fixed order and print the first whose complexity exceeds m. Such strings exist by counting. The search program's code consists of a fixed procedure plus an encoding of m, requiring roughly logarithmic rather than linear growth in m.

For sufficiently large m, this would describe the selected string using fewer than m bits, contradicting the selection criterion. This is a proof sketch: a formal proof fixes the universal machine, self-delimiting encoding of the threshold, and constant overhead. It explains why exact complexity cannot be obtained merely by running every shorter program: some candidates never halt.

Finite incompressibility and randomness of an infinite sequence require carefully stated definitions. A pseudorandom generator with a fixed finite seed can produce output that is difficult for efficient tests to distinguish from random output while still having a short unrestricted description. Computational security and unrestricted description complexity are different notions.

Exercises

1. In the independent fair-coin model, compute the probability that both tosses are heads given at least one head. Then compute it for the process choosing only HH or TT. Explain the different results.
2. Among 20-bit strings, how many can possibly have programs shorter than 15 bits? What fraction is that? Can the counting proof identify a specific incompressible string?
3. A compressor outputs 1005 bytes for a 1000-byte file. Another researcher finds a 60-byte program generating it. Are the results contradictory? State what each result proves and what extra cost must be specified for the 60-byte claim.

Compare your reasoning with the worked solutions

1. In the independent model, the conditional outcomes HH, HT, and TH are equally likely, so the answer is 1/3. In the dependent process, learning that there is a head rules out TT, leaving HH with probability 1. Marginal fairness alone is not enough to justify the four-outcome uniform model. The difference arises from dependence, not a violation of probability axioms.
2. Programs of lengths 0 through 14 number 2^15-1=32767. At most that many distinct 20-bit outputs can have such descriptions. The fraction is 32767/1048576, slightly below 1/32. Some programs do not halt or share outputs, so this is an upper bound. Counting does not locate an individual string with high complexity; doing that reliably at arbitrary thresholds would conflict with the uncomputability argument.
3. There is no contradiction. The compressor established the size of its own encoding, perhaps including a header. The generator establishes a short description relative to its programming language, interpreter, and available inputs. To compare bit complexity fairly, include any decoder/interpreter overhead required by the chosen reference machine and any hidden data used by the program. Neither result alone establishes the exact minimum among all descriptions.