Andrey Nikolaevich Kolmogorov
| Paul M.B. Vitanyi (2007), Scholarpedia, 2(2):2798. | doi:10.4249/scholarpedia.2798 | revision #186579 [link to/cite this article] |
For now let me mention a non-exhaustive list of areas he enriched by his fundamental research: The theory of trigonometric series, measure theory, set theory, the theory of integration, constructive logic (intuitionism), topology, approximation theory, probability theory, the theory of random processes, information theory, mathematical statistics, dynamical systems, automata theory, theory of algorithms, mathematical linguistics, turbulence theory, celestial mechanics, differential equations, Hilbert's 13th problem, ballistics, and applications of mathematics to problems of biology, geology, and the crystallization of metals. In over 300 research papers, textbooks and monographs, Kolmogorov covered almost every area of mathematics except number theory. In all of these areas even his short contributions did not just study an isolated question, but in contrast exposed fundamental insights and deep relations, and started whole new fields of investigations.
Apart from his penetrating work in Mathematics and the Sciences, he devoted much of his time to improving the teaching of mathematics in secondary schools in the Soviet Union, and in providing special schools for the mathematically gifted - which were very successful. Famous are also his efforts to capture in quantitative form some aspects of Russian poetry, especially that of Pushkin. It is told that "it was fascinating to hear him lecture on this, whether one understood Russian or not." In 1942 Kolmogorov married Anna Dmitriyevna Egorov. He did not have children of his own.
While being acknowledged without question in science, Kolmogorov was also blessed with social recognition. The USSR conferred to him seven orders of Lenin, the Order of the October Revolution, and also the high title of Hero of Socialist Labour; he gained Lenin prizes and State prizes. He occupies the first place among all Soviet mathematicians in the number of foreign academies and scientific societies that have elected him as member. These number over twenty, among them
- the Royal Netherlands Academy of Sciences (1963),
- the London Royal Society (1964),
- the USA National Society (1967),
- the Paris Academy of Sciences (1968),
- the Polish Academy of Sciences,
- the Rumanian Academy of Sciences (1956),
- the German Academy of Sciences Leopoldina (1959),
- the American Academy of Sciences and Arts in Boston (1959).
He was presented with honorary doctorates from the universities of Paris, Berlin, Warsaw, Stockholm, etc. He was elected a honorary member of the Moscow, London, Indian, and Calcutta Mathematical Societies, of the London Royal Statistical Society, the International Statistical Institute, and the American Meteorological Society. In 1963 he was awarded the International Bolzano prize.
These remarks are based on second hand information, and primarily on sources in the Russian Mathematical Surveys, other references, and to a much lesser extent on personal communications. My credentials for writing about Kolmogorov's achievements are founded solely on my interests in that excellent notion we call Kolmogorov complexity. Since Kolmogorov was a man of many aspects, it is a pleasure to share some of these with the reader. This writeup was originally published as an obituary, Vitanyi (1988), see also Section 1.13 of Li and Vitanyi (1997).
Contents |
Early Years: 1903-1933
Kolmogorov was born on 25 April 1903 in the town of Tambov, where his mother Mariya Yakovlevna Kolmogorova had been delayed on her way from the Crimea. She died in childbed, and the responsibility to bring up the child was taken over by her sister Vera Yakovlevna Kolmogorova, "an independent woman who held high social ideals. She passed this over to her nephew, raising him in the sense of responsibility, independence of opinion, intolerance towards idleness and poorly performed tasks, and the desire to understand and not just to memorize."
Kolmogorov treated her as his mother until her death in 1950 at Komarovka (his dacha) at the age of 87. From his mother's side Kolmogorov was of aristocratic stock, his grandfather Yakov Stephanovitch Kolmogorov was a district head of the nobles in Uglich.
Kolmogorov spent his early years (before the revolution of 1917) at the family estate. The sources are less clear about his father. Apparently, Kolmogorov's father was the son of a clergyman, and was himself an agronomist with highly specialized training, what they called at the time "a learned agronomist."
Kolmogorov started to work already at an early age (but presumably after the revolution); and before he became a student at Moscow University, he worked for some time as a railway conductor. He arrived at the University in autumn 1920, with already a fair knowledge of mathematics, gleaned from a book called "New Ideas in Mathematics." Students at the time received grants that had little material value, but at the second course received, in addition, a ration of 16 kilos of baked bread and a kilo of fat. Hence, Kolmogorov lost little time to check the minimum requirements for moving to the second course (lecture attendance being noncompulsory).
Conditions were generally harsh, and lecture rooms cold and unheated in the winter of 1920/1921. The following (unattributed) lines describe it:
- "That grim year, nineteen twenty-one,
- the scientific march began
- Of Moscow University.
- Though I was not then very old,
- Though sheepskin coats enveloped me,
- I still recall that beastly cold."
For some time Kolmogorov was interested in Russian history as well as mathematics. He did serious scientific research on XV-XVI century manuscripts concerning agrarian relations in ancient Novgorod. In the twenties he made a hypothesis on the way the upper Pinega was settled, and this conjecture was later confirmed by an expedition to that area.
In this early post-October revolution period the mathematical life in Moscow was dominated by "young Luzitania" (1920-1923) and "post-Luzitania" (1923-1927), a nickname for the school of real function theory headed by N.N. Luzin. This legendary personality apparently created either enthusiastic admiration or, in their struggle for independence, one-sided negation in his pupils. Among the first subjects in mathematics Kolmogorov took were set theory, projective geometry, and theory of analytic functions. In 1921-1922 he obtained his first independent mathematical result (the existence of Fourier-Lebesgue series with arbitrarily slowly decreasing Fourier coefficients), and he became a pupil of N.N. Luzin. During this time he was also approached by P.S. Urysohn, who tried to interest him in topological problems. Since Kolmogorov had obtained some results on the descriptive theory of functions, work that did not fit into Luzin's plans, Urysohn brought him into contact with P.S. Alexandrov, whose research interests were better related to this topic. However, at about this time Kolmogorov constructed a Fourier series divergent everywhere, a result that attracted international attention, and brought him for the time being in Luzin's orbit again. For this reason Kolmogorov's initial contacts with Aleksandrov stayed very limited at the time.
Kolmogorov got interested in mathematical logic, and in 1925 published a paper in Mathematicheskii Sbornik on the law of the excluded middle, which has been a continuous source for later work in mathematical logic. This was the first Soviet publication on mathematical logic containing (very substantial) new results, and the first systematic research in the world on intuitionistic logic. Kolmogorov anticipated to a large extent A. Heyting's formalization of intuitionistic reasoning, and made a more definite correlation between classical and intuitionistic mathematics. Kolmogorov defined an operation for "embedding" one logical theory in another. Using this - historically the first such operation, now called the Kolmogorov operation - to embed classical logic in intuitionistic logic, he proved that application of the law of the excluded middle in itself cannot lead to a contradiction. In 1932 Kolmogorov published a second paper on intuitionistic logic, in which for the first time a semantics was proposed (for this logic), free from the philosophical aims of intuitionism. This paper made it possible to treat intuitionistic logic as constructive logic.
His interest in probability theory originated in 1924. His first steps in this area were performed jointly with A.Y. Khinchin. In 1928 he succeeded in finding necessary and sufficient conditions for the strong law of large numbers to hold, and proved the law of the iterated logarithm for sums of independent random variables, under very general conditions on the summands. In "A general theory of measure and the calculus of probabilities", 1929, he put forward a first draft of an axiom system for probability theory based on the theory of measure and the theory of functions of a real variable. Such a theory had been first suggested by E. Borel in 1909, was further developed by Lomnicki in 1923, and received its so successful final form with Kolmogorov's classic treatment of 1933. Much important work on probability theory had already been done without benefit of foundations, but this little book "Foundations of the Calculus of Probabilities," published in German in 1933, immediately became the definitive formulation of the subject. This determined not only a new stage in the development of probability theory as a branch of mathematics, but also gave the necessary basis for the creation of the theory of random processes - the subject of his 1931 paper below. It was here that the basic theorems on infinite-dimensional distributions, now the logical foundations for the rigorous construction of the theory of random functions and sequences of random variables, were first formulated. The involved ideas lie at the heart of the modern theory of random processes; they form essential concepts in the very idea of control theory, and play a vital role in Kolmogorov's later synthesis of information theory and ergodic theory. Kolmogorov's many contributions in the theory of probability and statistics made him generally acknowledged as the foremost representative of this discipline.
In 1931 Kolmogorov's paper "Analytical methods in probability theory" appeared, in which he laid the foundations for the modern theory of Markov processes. According to Gnedenko: "In the history of probability theory it is difficult to find other works that changed the established points of view and basic trends in research work in such a decisive way. In fact, this work could be considered as the beginning of a new stage in the development of the whole theory".
The theory had a few forerunners: A.A. Markov, H. Poincare and Bachelier, Fokker, Planck, Smolukhovski and Chapman. Their particular equations for individual problems in physics, informally obtained, followed as special cases in Kolmogorov's theory. A long series of subsequent publications followed, by Kolmogorov and his followers, among which a paper by Kolmogorov dealing with one of the basic problems of mathematical statistics, where he introduces his famous criterion (Kolmogorov's test) for using the empirical distribution function of observed random variables to test the validity of an hypothesis about their true distribution. In general Kolmogorov's ideas on probability and statistics have led to numerous theoretic developments, and to numerous applications in present-day physical sciences.
After graduation in 1925, Kolmogorov stretched his stay at the University for four more years as a research student, but finally in 1928-1929 stricter control on the number of years a student had for research was enforced. An unprecedented number of 70 students finished in 1929, including Kolmogorov This raised the problem of where to continue his research. Aleksandrov was instrumental in securing for Kolmogorov the single available vacancy in 1929 at the Institute of Mathematics and Mechanics of Moscow University, against heavy competition.
Youth: 1929-1940
From 1930-1940 Kolmogorov published more than sixty papers on probability theory, projective geometry, mathematical statistics, the theory of functions of a real variable, topology, mathematical logic, mathematical biology, philosophy and the history of mathematics. In 1931 Kolmogorov was made professor at Moscow University, and from 1937 held the chair of theory of probability. From this time dates the life long friendship between Kolmogorov and P. Aleksandrov. Says Aleksandrov: "in 1979 this friendship [with Kolmogorov] celebrated its fiftieth anniversary and over the whole of this half century there was not only never any breach in it, there was also never any quarrel, in all this time there was never any misunderstanding between us on any question, no matter how important for our lives and our philosophy; even when our opinions on one of these questions differed, we showed complete understanding and sympathy for the views of each other."
Says Kolmogorov: "for me these 53 years of close and indissoluble friendship were the reason why all my life was on the whole full of happiness, and the basis of that happiness was the unceasing thoughtfulness on the part of Aleksandrov."
Kolmogorov describes how this friendship started in 1929 during a sailing trip on the Volga. At that time, the "Society for Proletarian Tourism and Excursions" offered active vacations: one obtained a boat and camping equipment at one city on the Volga which could be handed in at other cities downstream. Kolmogorov, already experienced in boating, decided to organize such a trip, and asked (besides two others) Aleksandrov to join. The young men bought the then popular 'Jungsturm' suits for all of the crew. By way of books they took along only a steamboat timetable and a copy of the Odyssey (and also manuscripts to work on and a folding writing desk). They started out at June 16, and covered 1300 kilometers before handing in the boat at Samar downstream. Kolmogorov and Aleksandrov then proceeded together to the Caucasus by steamer. After some more wandering, they set up residence in an unused cell of a monastery on a small peninsula in Lake Savan. Whiling their time away at secluded bays, in between swimming and sun bathing they also managed to get some work done: Kolmogorov in the shadows on integration theory and analytic description of Markov processes in continuous time, and Aleksandrov dressed only in dark glasses and white panama hat in the burning sun on his Topology book with Hopf. They stayed in these idyllic surroundings for about three weeks, then set off partly on foot, partly by other means of transport, and eventually climbed the Alagez mountain (4100m). They wound up at Tiflis, from where Aleksandrov proceeded alone to a prearranged appointment with a group of mathematicians. Kolmogorov continued hiking and mountain climbing. (By this time it was August.) Later, they joined up again at Gagra, on the Black Sea, and spent some more time there, sunbathing and swimming and doing mathematics. At about this time they decided to share a house together.
After returning to Moscow they forthwith rented the first in a series of houses in the nearby vacation village of Klyaz'm, and moved in together with Kolmogorov's aunt Vera Yakovlevna. A short time later, Masha Barbanova, who had been Kolmogorov's nanny at the family estate near Jaroslavl' before the revolution, joined as housekeeper. In 1935 they acquired (initially part of) an old manor house at Komarovka, with room for a large library and several guests. This `house at Komarovka' became a meeting place for mathematicians. One of them said "It is just like Oberwolfach (a mathematical institute in the Black Forest), except that here Kolmogorov buys all the drinks."
It is perhaps instructive to see a glimpse of the mathematicians' country life:
"As a rule," says Kolmogorov, "of the seven days a week, four were spent in Komarovka, one of which was devoted entirely to physical recreation - skiing, rowing, long excursions on foot (these long walks covered on average about 30 kilometers, rising to 50; on sunny March days we went out on skis wearing nothing but shorts, for as much as four hours on a stretch. On the other days, morning exercise was compulsory, supplemented in the winter by a 10 kilometer ski run ... Especially did we love swimming in the river just as it began to melt ... I swam only short distances in icy water but Aleksandrov swam much further. It was I however who skied naked for considerably longer distances." As P. Halmos, visiting Kolmogorov in Moscow in 1965 tells it:
"Kolmogorov [had] five rooms [apartment in the University]. ... stacks of reprints in one corner, a collection of theatrical masks somewhere, and a couple of skis somewhere else. "Is this where you work? I asked. "No, no", he said: "I work out at the dacha; I am here only three days a week."" (At the celebration meeting of K's seventieth birthday, a skiing trip was organized where Kolmogorov clad only in shorts outskied every other participant.)
In 1930-1931 Kolmogorov and Aleksandrov were mainly abroad. The year 1930 they spent both at Gottingen. Here Kolmogorov had contacts with R. Courant on limit theorems, with H. Weyl on intuitionistic logic, and with E. Landau on function theory. Kolmogorov relates the story that he solved a problem Landau much liked to be solved, and wrote it up in detail. Landau being very pleased told everybody about the success and invited a paper on the subject, but, to his embarrassment, Kolmogorov discovered a few weeks later exactly the same result with the same proof by Besicovitch in Fundamenta Mathematicae. The summer both Kolmogorov and Aleksandrov visited Caratheodory at Munich (measure theory), and were invited to stay with Frechet on the Mediterranean (to work on probability theory in Kolmogorov's case). The journey there involved hiking through Bavaria, staying with Frechet for about a month, visiting P.S. Urysohn's grave in Normandy, and continuing on to Paris. Aleksandrov left Paris by the end of September for Goettingen, and Kolmogorov stayed on until December, and had some meetings with Borel and P. Levy, especially the last. While Kolmogorov returned to Goettingen, Aleksandrov spent the spring 1931 semester in the U.S.A.
As another highlight of this period the article "Mathematics" for the second edition of the Great Soviet Encyclopaedia is often mentioned. Another area he turned to at the time was topology. Simultaneously with the U.S. topologist J.W. Alexander and independently of him, Kolmogorov discovered the notion of cohomology and founded the theory of cohomological operations. The work of Kolmogorov and his school on the deep connections between topology, the theory of ordinary differential equations, celestial mechanics and the theory of dynamical systems, determined to a considerable extent its present state.
At the end of the thirties, Kolmogorov's attention was drawn to the mechanics of turbulence. In the hands of Kolmogorov and his school the theory of turbulence obtained an accurate mathematical form as an applied chapter in the theory of measure of function spaces. With great physical intuition, in two short papers in 1941, Kolmogorov posited in concise mathematical form ideas about the structure of the small-scale components of turbulent motion of fluids and gasses, latent in earlier experimental work, particularly by G.I. Taylor. These hypotheses imply many qualitative results that are widely applicable - what goes on, for instance, within the turbulence that occurs in the wake of a jet aircraft. Some of the quantitative relations arising have the character of new laws of nature - like Kolmogorov's law of "2/3": in each developed turbulent flow the mean square difference of the velocities at two points is proportional to the 2/3rd power of their distance (if the distance is not too small or not too large). Kolmogorov made also quantitative predictions on the basis of his theories, that were later confirmed by experiments, e.g., the stratified structure of the ocean, an effect known as "pancakes". Kolmogorov's 1941 contributions to the theory of turbulence are perhaps the most important ones in the long and unfinished history of the theory of turbulence.
Middle Years: 1940-1960
He was interested in every branch of science, he and his pupils wrote about crystal growth, about geometry of the interaction of plants, and also made significant contributions to `birth and death' processes and to genetics. One of these papers brought him to a head-on confrontation with Lysenko. In a courageous stand in emphasizing scientific truth, in a paper published in 1940 in the "Genetics" section of Dokl. Akad. Nauk SSSR , Kolmogorov showed that the material gathered by followers of Stalin's protege Academician Lysenko, contrary to opinion, supported Mendel's laws. Another joint work (with Piscounov and Petrovsky) treated the rate of advance of an advantageous gene in a linear environment, (a topic studied independently by R.A. Fisher, whom Kolmogorov held in high regard). This was later adapted to describe spreading of epidemics of innovations, and rumours.
The theory of smoothing and prediction of stationary time-series is usually associated with the name of Norbert Wiener but in fact it was developed simultaneously by Wiener and Kolmogorov during the second world war.
In the post-war period Kolmogorov turned again to turbulence, and made small improvements on laws he discovered before, that were experimentally verified as well. Topics in the vast range of classical mechanics, ergodic theory, function theory, information theory and the theory of algorithms belong to this period. He managed to find links between totally unconnected fields, and published a small number of papers, but quite fundamental ones, on each topic. In his work on dynamical systems one can distinguish two periods. In 1953-1954 he made a seminal contribution to the fundamental problem of classical mechanics, identified fifty years earlier by H. Poincare in his study of the motion of planets around the sun. Neglecting all but one planet one deals with an `integrable' problem that is well understood. However, the small effects associated with gravitational interaction between the planets introduces a profound qualitative change related to the fact that the equations are now `nonintegrable.' In attacking this problem, Kolmogorov's great achievement was to develop a general theory of Hamiltonian systems under small perturbations, which has several practical applications, among others in the study of magnetic fields and plasma physics. This work also spawned, together with improvements of Kolmogorov's pupil Arnol'd and by Moser, what is now known as the study of `KAM-tori.' Subsequent computational studies aptly confirm Kolmogorov's insights and have opened up the enormously fruitful field of `chaos in dynamical systems,' which is currently attracting much attention. These studies lead, for example, to better weather forecasting.
At this time he also started to work on the theory of automata and the theory of algorithms. Together with his pupil V.I. Uspensky he formulated the important notion of Kolmogorov-Uspensky machine. He supported the up and coming field of cybernetics (theory of computation) against heavy initial antagonism (in the USSR). Many USSR computer scientists are Kolmogorov's pupils or pupils of Kolmogorov's pupils.
The second period from 1955-1959 consisted in applications from information theory to the ergodic theory of dynamical systems. He introduced the fruitful idea of informational (entropic) characteristics in the study of metric spaces and of dynamical systems. Together with Arnol'd, Kolmogorov settled in 1956-1957 Hilbert's 13th problem, disproving the conjectured outcome, by showing that a continuous function in any number of variables can be represented as a composition of continuous functions of a single variable and addition. The ideas of introducing entropic characteristics in the theory of dynamical systems opened up a large new area. Another important concept, that of a quasi-regular system (now called K-system), plays a very important role in the analysis of classical dynamic systems with strong stochastic properties, such as in physics, biology and chemistry. In the years 1958-1959 Kolmogorov applied ergodic theory to phenomena of the type of turbulence, which had a great influence on subsequent work.
Later Years: 1960-1987
While in previous years Kolmogorov used concepts of information theory in mathematical sciences, now it was the turn of information theory to be reconstructed using the theory of algorithms, incidentally closing the circle of his research by giving logico-algorithmic foundations to the theory of probability. Algorithmic Information Theory, or [[Kolmogorov complexity]] theory, originated with the discovery of universal descriptions of finite objects, and a recursively invariant approach to the concepts of complexity of description, randomness and a priori probability. Historically, it is firmly rooted in R. von Mises' notion of random infinite sequences Kollektivs, proposed from 1919 onwards as foundation for the theory of probability in the spirit of a physical theory (according to the program outlined in D. Hilbert's 6th problem), using the frequency interpretation of probability. In 1940 A. Church proposed an algorithmic version of von Mises random sequences, but the results were not yet satisfactory.
In his 1933 booklet Kolmogorov had in some sense executed Hilbert's suggestion in his 6th problem: "To treat (in the same manner as geometry) by means of axioms, those physical sciences in which mathematics plays an important part; in the first rank are the theory of probability ..", in 1963 Kolmogorov observes: "This theory [K's 1933 set theoretic axiomatic approach] was so successful, that the problem of finding the basis of real applications of the results of the mathematical theory of probability became rather secondary to many investigators. ..[However] the basis for the applicability of the results of the mathematical theory of probability to real 'random' phenomena must depend in some form on the frequency concept of probability , the unavoidable nature of which has been established by von Mises in a spirited manner."
However, von Mises based his approach on axiomatically postulated infinite random sequences, representing repetitious independent trials with a limiting frequency. To this Kolmogorov objects: "The frequency concept based on the notion of limiting frequency as the number of trials increases to infinity, does not contribute anything to substantiate the application of the results of probability theory to real practical problems where we always have to deal with a finite number of trials."
Following a four decades long controversy on von Mises' intended notion of an infinite random sequence, in a 1965 paper Kolmogorov used the theory of algorithms to describe the complexity of a finite object as the length of the smallest description (algorithm to reconstruct it). This would seem to make the definition depend on the algorithmic method used. However, it turns out that there are optimal and universal methods for which the complexities of the objects described are asymptotically optimal. Although there are many optimal methods, the corresponding complexities differ by no more than an additive constant. It is natural to call a finite object random if it has no description of complexity less than it has itself. It is seductive to define an random infinite sequence as one of which the growth of complexity if the initial segments with the length is sufficiently fast, thus relating to von Mises' earlier approach. Due to unavoidable oscillations of the complexity of prefixes as function of their length this did not work out. However, P. Martin-Loef, a Swedish mathematician visiting Kolmogorov in Moscow in 1964-1965, was able to show that under appropriate axiomatic definitions of randomness, one can prove once and for all that the thus defined sequences satisfy all effective tests for randomness, and have measure one in the set of all such infinite sequences. This rigorously defined an appropriate class, intuitively satisfactory as well, to qualify as von Mises' Kollektivs. Later it was shown by L.A. Levin, P. Gacs and G.J. Chaitin that one can refine the notion of complexity by defining it relative to a set of admissible descriptions. If admissible descriptions are restricted such that no description is a proper prefix of any other description, then an infinite sequence is Martin-L of random if and only if each of its finite initial sequences has a complexity that equals (up to a fixed constant) its length.
With the advent of electronic computers in the 1950's, a new emphasis on computer algorithms, and a maturing general recursive function theory, ideas tantamount to Kolmogorov complexity came to many people's minds, because `when the time is ripe for certain things, these things appear in different places in the manner of violets coming to light in early spring,' in the phrase of Wolfgang Bolyai in another famous context. Thus, R. Solomonoff in Cambridge, Massachusetts, had formulated the same ideas already in 1960. and had published his truly innovative work on the subject already in 1964 in `Information and Control'.
According to Solomonoff his work got far more attention after Kolmogorov started to refer to it from 1968 onward, even though the attribution of `Kolmogorov' complexity seems to have stuck. Says Kolmogorov: `I came to similar conclusions before becoming aware of Solomonoff's work, in 1963-1964.'
Yet a third independent inventor entered slightly later, Gregory Chaitin, who was an 18 year old undergraduate in New York when he submitted a very similar set of inventions for publication end 1965 for publication in `J. Assoc. Comp. Mach.' (published in 1966 and 1969, the last paper containing the definition of Kolmogorov complexity and results thereof, while the 1966 paper extends C.E. Shannon's non-invariant notion of state-symbol measure for the complexity of Turing machines). Says Chaitin: `this definition [of Kolmogorov complexity] was independently proposed about 1965 by A.N. Kolmogorov and me ... Both Kolmogorov and I were then unaware of related proposals made in 1960 by Ray Solomonoff.'
As perhaps the last mathematical innovation of an extraordinary scientific career, Kolmogorov in 1973 proposed to found statistical theory on finite combinatorial principles independent of probabilistic assumptions. Technically, the new statistics is expressed in terms of Kolmogorov complexity. The relation between the individual data and its explanation (model) is expressed by Kolmogorov's Structure function. This entails a non-probabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider model classes consisting of models of given maximal (Kolmogorov) complexity. The Structure function of the given data expresses the relation between the complexity level constraint on a model class and the least log-cardinality of a model in the class containing the data. Later, it was shown that the structure function determines all stochastic properties of the data: for every constrained model class it determines the individual best-fitting model in the class irrespective of whether the `true' model is in the model class considered or not. The only written record by Kolmogorov himself is the following abstract, Kolmogorov (1974 UMN}:
"To each constructive object corresponds a function \(\Phi_x(k)\) of a natural number \(k\)---the log of minimal cardinality of \(x\)-containing sets that allow definitions of complexity at most \(k\ .\) If the element \(x\) itself allows a simple definition, then the function \(\Phi\) drops to 1 even for small \(k\ .\) Lacking such definition, the element is "random" in a negative sense. But it is positively "probabilistically random" only when function \(\Phi\) having taken the value \(\Phi_0\) at a relatively small \(k=k_0\ ,\) then changes approximately as \(\Phi(k)=\Phi_0-(k-k_0)\ .\)"
One of the last papers of Kolmogorov was a survey on the topic of algorithmic information theory - a paper together with Uspensky published in 1987. For a comprehensive introduction and a survey of the astonishing range of applications of Kolmogorov complexity, see Applications of Algorithmic Information Theory and Li and Vitanyi (1997).
As a Teacher
Kolmogorov's pedagogical activities began in 1922, when he became teacher at the experimental model school of the People's Commissariat for Education. He taught there until 1925. From 1925 till 1929 he was instructor at the University. Passing on knowledge and scientific ideas was very important for Kolmogorov His interests in this subject ranged over the full scale from earliest education to higher education, and occupied much of his time. He actively took part in organizing mathematical Olympiads in schools and gave talks to school children. Thus he wrote a booklet on the topic `Mathematics as a Profession', which circulated in tens of thousands of copies. He put special emphasis on selection of mathematically gifted adolescents, since even the nonmathematicians will need such training in their later career.
According to Kolmogorov, by 14-15 years about half of the pupils have come to the conclusion that mathematics and physics will be of little use to them. In recognition of that fact a special simplified program should be followed by such pupils. `The mechanically understood principles of uniformity of schools providing general education, which excludes schools with a more detailed study of individual subjects, has outlived itself. As applied to mathematics it has already been destroyed by the creation of schools giving special training to computer operators and computer programmers.' And: `At 14-16 everything changes. At this age interest in mathematics usually becomes apparent, which quickly and painlessly leads the student to concentrated work and then to the real research work of the young scientist (at 18-20 years). ... For the beginners, the young people entering science for the first time, it is important to be convinced as soon as possible that they are capable of doing something original, their very own. When offering a subject for research to a graduate or a research student, the supervisor must not think only about the objective importance, or urgency of the subject, but also whether the work on the subject will stimulate the development of the young scientist, and whether it is within his powers to carry out, and at the same time demand the maximal effort of which he is capable.' The ability to offer the students exactly what is most important and ripe in the development of science, and avoid pursuing dead-ends, and what is at the same time in their powers to accomplish is very characteristic for Kolmogorov.
The number of Kolmogorov's research students who have obtained their Ph.D. exceeds sixty. He was instrumental in substantial transformation (in the Soviet Union) of the very character of university education in mathematics, in particular the organization of practical work in mathematics, and updating the contents of mathematics. He also engaged in the search for new contents of mathematics in secondary schools, the founding of mathematical boarding schools, gave cycles of lectures for teachers on the structure of modern mathematics, and so on. Finally, he created an author's collective, and took part himself in writing textbooks on geometry, algebra and analysis for 6th through 10th grades. At the mathematical boarding school No. 18 at the University of Moscow, otherwise known as the `Kolmogorov school', he gave for years lessons up to 26 hours a week, and wrote accompanying syllabi. He also gave lectures to the students on music, art and literature. He felt that intellectual development must be evenly balanced. The former pupils of this school are very successful and systematically take the first places in All-Union and International Mathematical Olympiads.
In 1964 Kolmogorov became head of the mathematical section of a joint syllabus committee of the USSR Academy of Sciences and that of Pedagogical Sciences. Kolmogorov also organized a Statistical Laboratory at the University of Moscow, and succeeded in upgrading the budding library by obtaining large funds, and also international literature through partial use of money he received as part of the international Bolzano prize. In 1972 on Kolmogorov's initiative a compulsory course in mathematical logic was introduced for the first time in the Department of Mechanics and Mathematics at Moscow State University. He wrote the syllabus (which was still followed in 1983) and was the first to teach it.
According to V.I. Arnol'd, "Kolmogorov never explained anything, just posed problems, and didn't chew them over. He gave the student complete independence and never forced one to do anything, always waiting to hear from the student something remarkable. He stood out from the other professors I met by his complete respect for the personality of the student. I remember only one case where he interfered with my work: in 1959 he asked me to omit from the paper on self-maps of the circle the section on applications to heartbeats, adding "That is not one of the classical problems one ought to work on". The application to the theory of heartbeats was published by L. Glass 25 years later, while I had to concentrate my efforts on the celestial-mechanical applications of the same theory."
L.S. Pontryagin relates: "Kolmogorov gave me an interesting task..:
to study [some problems in] locally compact algebraic fields
in which multiplication is not necessarily commutative...
A week later I reported to Aleksandrov
that I had solved it in the case of commutative fields.
Directly afterwards the three of us, Aleksandrov, Kolmogorov
and I, met in Aleksandrov's flat. With a shade of
ironical doubt, Kolmogorov said: "Well now, Lev Semenovich,
I hear you have already solved my problem, let's hear you."
Kolmogorov declared my very first statement to be false,
but I immediately refuted him. Then he said: "Yes,
it seems that the problem turned out to be much easier than
I supposed." None of the rest of my answer aroused doubt.
For the case of the noncommutative field the problem was
immeasurably more difficult. It took me a whole year to
work it out." It is also said that
Kolmogorov was one of the very few
non-political mathematicians in the Soviet Union with
yet real power. He quietly helped
talented people with otherwise unfashionable views.
Kolmogorov's pupils included in the early years: Millionshchikov (later Vice-President of the USSR Academy of Sciences), Mal'tsev, Nikol'skii, Gnedenko, Gel'fand, Bavli and Verchenko. The subjects ranged from theoretical geophysics, mathematical logic, functional analysis, probability theory, function theory. During and after the war: Shilov, Fage, Sevast'yanov, Sirazhdinov, Pinsker, Prikhorov, Barenblatt, Bol'shev, Dobrushin, Medvedev, Mikhalevich, Uspenskii, Borovkov, Zolotarev, Alekseev, Belyaev, Mehhalkin, Epokhin, Rozanov, Sinai, Tikhomirov, Shiryaev, Arnol'd, Bassalygo, and Ofman. Later also Prokhorov, L.A. Levin, Kozlov, Zhurbenko, Abramov, and Bulinskii. His pupils include a number of well-known foreign mathematicians, among who the Swede P. Martin-Loef. Pupils who became member of the USSR Academy of Sciences: A.I. Mal'tsev (algebra, mathematical logic), S.M. Nikol'skii (function theory), A.M. Obukhov (physics of the atmosphere), I.M. Gel'fand (functional analysis), Yu.V. Prokhorov (probability theory); and corresponding member: L.N. Bol'shev (mathematical statistics), A.A. Borovokov (probability theory, mathematical statistics), A.S. Monin (oceanology), and V.I. Arnol'd. The Ukrainian Academy of Sciences: B.V. Gnedenko (probability theory, history of mathematics), V.M. Mikhalevich (cybernetics), etc.
Scientific Career
Kolmogorov entered Moscow University in 1920, graduated in 1925, and got his (equivalent of) Ph.D. in 1929, when he also got a position on the faculty. In 1931 Kolmogorov became professor at Moscow University, and from 1933-1939 he also became Director of the Scientific Research Institute of Mathematics at the Moscow State University. Apparently, he was involved with the scientific research of all graduate students at the institute, not only his own. Most of them mention the unforgettable hikes on Sundays when Kolmogorov invited all his own students (graduates and undergraduates) as well as students from other supervisors. These 40 km walks in the environment of Bolshevo, Klyaz'm, later Komarovka, are remembered as intellectually stimulating and culturally wide ranging experiences, ending when he and Aleksandrov treated the whole company to dinner in their dacha. In 1939 Kolmogorov was elected as an Academician of the All-Union Academy of Sciences and as Academician-Secretary of the Physics-Mathematical Section. He also did enormous work as head of the mathematics editorial board of the Publishing House of Foreign Literature and as editor of the mathematics section of the Great Soviet Encyclopaedia. During the second world war Kolmogorov engaged in the war effort by solving problems in ballistics and began research on problems of quality control of mass industrial production. From 1964 to 1966, and from 1976 till at least 1983 Kolmogorov has been President of the Moscow Mathematical Society; from 1946 to 1954 and from 1983 on Editor-in-chief of Uspekhi Math. Nauk (Russian Mathematical Surveys). At the University of Moscow, Kolmogorov held from 1938 to 1966 the chair of probability theory. From 1966 till 1976 he was the head of the Interdepartmental Laboratory of Statistical Methods, and from 1976 to 1980 he held the chair of mathematical statistics, which he organized. From 1980 on Kolmogorov held the chair of mathematical logic. From 1951 to 1953 he was Director of the Institute of Mathematics and Mechanics of the Moscow State University; from 1954 to 1956 and from 1978 to at least 1983 the head of the mathematics section of the Faculty of Mechanics and Mathematics. From 1954 to 1958 he was Dean of the Faculty of Mechanics and Mathematics of the University.
References
A.M. Abramov, Kolmogorov's pedagogic legacy, Russian Mathematical Surveys, 43:6(1988), 45-88.
P.S. Aleksandrov, A few words on A.N. Kolmogorov, Russian Math. Surveys, 38:4(1983), 5-7.
V.I. Arnol'd, A few words on Andrei Nikolaevich Kolmogorov, Russian Mathematical Surveys, 43:6(1988), 43-44.
N.N. Bogolyubov, B.V. Gnedenko, S.L. Sobolev, Andrei Nikolaevich Kolmogorov (on his eightieth birthday). Russian Math. Surveys, 38:4(1983), 9-27.
T.M. Cover, P. Gacs, R.M. Gray, Kolmogorov's contributions to Information Theory and Algorithmic Complexity, The Annals of Probability, 17(1989), 840-865.
B.V. Gnedenko, Andrei Nikolaevich Kolmogorov (on the occasion of his seventieth birthday), Russian Math. Surveys 28:5(1973), 5-16.
A.N. Kolmogorov, Grundbegriffe der Wahrscheinlichkeitsrechnung, Springer Verlag, Berlin, 1933. (2nd Russian Edition (1974), `Osnovnye Poniatija Teorii Verojatnostej,' Nauka, Moscow)
A.N. Kolmogorov, Complexity of Algorithms and Objective Definition of Randomness, A talk at Moscow Math. Soc. meeting 4/16/1974. Abstract in: Uspekhi Mat. Nauk, 29:4(1974),155. Translated from the original Russian by L.A. Levin.
A.N. Kolmogorov, Memories of P.S. Aleksandrov, Russian Mathematical Surveys, 41:6(1986), 225-246.
A.N. Kolmogorov, Letters of A.N. Kolmogorov to A. Heyting, Russian Mathematical Surveys, 43:6(1988), 89-93.
M. Li, P.M.B. Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, 1997, Second Edition.
S.M. Nikol'skii, Aleksandrov and Kolmogorov in Dnepropetrovsk, Russian Math. Surveys, 38:4(1983), 41-55.
S.P. Novikov, Memories of A.N. Kolmogorov, Russian Mathematical Surveys, 43:6(1988), 40-42.
Obituary: Andrei Nikolaevich Kolmogorov, J Bull. London Math. Soc., 22:1(1990), 31-100.
Obituary, Mr. Andrei Kolmogorov - Giant of mathematics, Times, October 26, 1987.
A.N. Shiryaev, A.N. Kolmogorov: Life and creative activities, The Annals of Probability, 1989, 866-944, Publications of Kolmogorov: pp. 945-964.
V.M. Tikhomirov, The life and work of Andrei Nikolaevich Kolmogorov, Russian Mathematical Surveys, 43:6(1988), 1-39.
B.A. Trakhtenbrot, A survey of Russian approaches to `perebor' (brute-force-search) algorithms, Annals of the History of Computing, 6(1984), 384-400.
P.M.B. Vitanyi, Andrei Nikolaevich Kolmogorov, CWI Quarterly, 1(1988), pp. 3-18.
Internal references
- Marcus Hutter (2007) Algorithmic information theory. Scholarpedia, 2(3):2519.
- Rodney G. Downey and Jan Reimann (2007) Algorithmic randomness. Scholarpedia, 2(10):2574.
- Ming Li and Paul M.B. Vitanyi (2007) Applications of algorithmic information theory. Scholarpedia, 2(5):2658.
- Olaf Sporns (2007) Complexity. Scholarpedia, 2(10):1623.
- James Meiss (2007) Dynamical systems. Scholarpedia, 2(2):1629.
- James Meiss (2007) Hamiltonian systems. Scholarpedia, 2(8):1943.
- Mark Aronoff (2007) Language. Scholarpedia, 2(5):3175.
- Frank Hoppensteadt (2007) Mathematical biology. Scholarpedia, 2(6):2877.
- Jeff Moehlis, Kresimir Josic, Eric T. Shea-Brown (2006) Periodic orbit. Scholarpedia, 1(7):1358.
- David Myers (2007) Psychology of happiness. Scholarpedia, 2(8):3149.
External Links
- Andrei Nikolaevich Kolmogorov (biography, publications, pictures, interviews)
- A.N. Kolmogorov History of Mathematicians Archive.
- Algorithmic Information Theory resource page (introductions, bibliography, mailing list, researchers, events)
See Also
Algorithmic Information Theory, Algorithmic Randomness, Applications of AIT, Kolmogorov-Arnold-Moser Theory, Kolmogorov Dimension, Kolmogorov-Sinai Entropy, Kolmogorov-Smirnov Test
