Skip to content

Andrey Kolmogorov

Abstract

Andrey Kolmogorov (1903–1987) was the most productive mathematician of the Soviet century, with dozens of theorems and concepts bearing his name, and three of them are foundations of computing. His 1933 axioms made probability a branch of mathematics, which is what every randomised algorithm, every error rate and every machine-learning loss function rests on. His entropy of a dynamical system (1958) connected Shannon’s information theory to physics. And in 1965, at 62, he defined the information content of a single object as the length of the shortest program that produces it, which gave randomness a definition that does not mention probability at all, and which turned out to be uncomputable. He came to the theory of algorithms late and from the top, and it was the subject he chose to lecture on in his last years.

Andrey Kolmogorov
Andrey Kolmogorov. Image: Konrad Jacobs, Mathematisches Forschungsinstitut Oberwolfach, CC BY-SA 2.0 de, via Wikimedia Commons.

Tunoshna

Andrey Nikolaevich Kolmogorov was born in Tambov on April 25, 1903; his mother died giving birth to him and his father, an agronomist, was absent, so he was raised by his mother’s sisters on the family estate at Tunoshna, near Yaroslavl, where one aunt ran a school and printed a children’s newspaper in which his first mathematical observation appeared at six: that the sum of the first n odd numbers is n squared. He entered Moscow State University in 1920, studying history as well as mathematics, and joined the school of Nikolai Luzin, the Moscow analyst whose students remade Russian mathematics. In 1922, at nineteen, he constructed a Fourier series that diverges almost everywhere, a result the field had believed impossible, and was known internationally before he graduated.

Probability

Through the 1920s he and Aleksandr Khinchin built the modern theory of probability, and in 1933 Kolmogorov published, in German, Grundbegriffe der Wahrscheinlichkeitsrechnung, sixty pages that put the subject on the axioms every textbook now states: a probability is a measure on a space of events, summing to one, and everything else follows. Before it, probability was a collection of techniques with disputed foundations; after it, a random variable was a measurable function and a theorem was a theorem. The equations for the evolution of Markov processes (1931), the strong law of large numbers, the theory of stationary processes and the prediction theory that Norbert Wiener developed in parallel for gunnery (see Norbert Wiener and Cybernetics) are his. In 1941 he set out the scaling laws of turbulence, still the reference theory; during the war he computed the optimal scatter of artillery fire and the placement of barrage balloons over Moscow.

His friendship with the topologist Pavel Alexandrov, begun on a river trip in 1929, lasted until Alexandrov’s death in 1982; they shared a house at Komarovka outside Moscow and neither ever described the relationship in public. In 1936, in the Luzin affair, both took part in the campaign against their old teacher, Kolmogorov testifying against him; historians still argue over how far they were coerced, and neither discussed it afterwards. He married Anna Egorova in 1942.

Information

In the 1950s Kolmogorov turned to the problems of the new sciences. The stability of the solar system produced the Kolmogorov–Arnold–Moser theorem (1954), with his student Vladimir Arnold and Jürgen Moser; Hilbert’s thirteenth problem produced, with Arnold, the representation theorem of 1957 that every continuous function of several variables is a superposition of continuous functions of one, a result that resurfaced in 2024 as the basis of Kolmogorov–Arnold neural networks. Reading Claude Shannon, he defined in 1958 the entropy of a dynamical system, which measures how fast a deterministic system generates information and which Yakov Sinai, another student, made a tool for classifying chaos (see Claude Shannon and Information Theory).

He had been running a seminar on the theory of algorithms since 1953, with Vladimir Uspensky, in which the Turing machine was reformulated as the Kolmogorov–Uspensky machine, a model that computes on graphs rather than tapes. Out of it came the idea for which computer science claims him. In “Three Approaches to the Quantitative Definition of Information” (1965), he asked what the information content of a single finite object is, without any probability distribution behind it, and answered: the length of the shortest program, for a fixed universal machine, that outputs the object. The choice of machine changes the answer only by a constant. A string is random if no program much shorter than the string itself produces it, which made “random” a property of the object rather than of the process that produced it. Ray Solomonoff in the United States had published the same idea in 1964 as a theory of prediction and Gregory Chaitin, at nineteen, found it independently in 1966; the measure carries Kolmogorov’s name because his was the statement mathematicians read, and its consequences, including that it cannot be computed, are in Kolmogorov Complexity and Gregory Chaitin. Kolmogorov lectured on the subject into the 1980s and regarded it as the proper foundation for probability itself, the axioms of 1933 being, on this view, a way of doing mathematics about randomness without saying what it was.

The School

In 1963 he founded a boarding school for mathematically gifted children attached to Moscow State University, taught there himself, and spent his last twenty years writing textbooks and rewriting the Soviet school curriculum in mathematics, a reform that was attacked and partly reversed. His students include Arnold, Israel Gelfand, Sinai, Uspensky, Eugene Dynkin and Roland Dobrushin, a lineage that is most of Russian mathematics in the second half of the century. He received the Wolf Prize in 1980. Parkinson’s disease disabled him in his last years; he died in Moscow on October 20, 1987. He had said that he wanted to be remembered as a teacher, and the school still carries his name.

📚 Sources