computability
The shortest description
It is the 1960s, and one of the oldest words in probability — 'random' — still has no rigorous meaning for a single fixed object. Here are two sequences of a thousand coin flips: one truly random, one secretly generated by a short hidden rule that happens to look random. No statistical test on the sequence alone cleanly separates them. Formalize randomness so the distinction becomes principled — tie it to the length of the shortest program that reproduces the sequence, so that 'random' means 'incompressible.' The definition is the achievement. Get it wrong and 'random' stays a matter of taste, and the foundations of probability, inference, and information all rest on sand — this notion of complexity-as-randomness became bedrock for everything from data compression to the theory of proof.
Who this problem belongs to
The two figures whose methods fit it best, out of 41 in contention.
This is his problem, solved his way. Having axiomatized probability in 1933, Kolmogorov spent the early 1960s dissatisfied that the theory said nothing about individual objects, and in 1965 he defined the complexity of a string as the length of the shortest program producing it on a universal machine, proving the invariance theorem that makes the definition robust. He explicitly framed randomness as incompressibility, connected it to von Mises's failed collectives and to information theory (offering algorithmic, combinatorial, and probabilistic definitions of information side by side), and his student Martin-Löf completed the statistical-test characterization in 1966. He had every prerequisite: measure theory, logic, computability via the Moscow school, and the philosophical itch that motivated the question. The two-point deduction is only that Solomonoff arrived independently slightly earlier.
The entire definition rests on machinery Turing built in 1936: 'shortest program that reproduces the sequence' is meaningless without a fixed universal machine, and the invariance theorem — complexity is machine-independent up to an additive constant — is a direct corollary of universality. Turing also proved the halting problem undecidable, which is why Kolmogorov complexity is uncomputable, a fact any honest solution must confront rather than discover by surprise. His earlier work on normal numbers (an unpublished 1930s manuscript constructing computable normal numbers) shows he was already circling the tension between effective procedures and randomness, and his Bletchley practice with Bayesian weight-of-evidence gave him working intuitions about distinguishing structure from noise. He lacks only the 1960s framing of tying this to probability's foundations; the conceptual toolkit is essentially his.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
41 figures are scored on this problem. Draw it in a battle to see where you land.