(``Andrei Nikolaevich
Kolmogorov,'' CWI Quarterly, 1(1988), pp. 3-18.)
by Paul M.B. Vitanyi,
CWI and University of Amsterdam
Andrei Nikolaevich Kolmogorov, born 25 April 1903 in Tambov, Russia,
died 20 October 1987 in Moscow. He was perhaps the
foremost contemporary Soviet mathematician and counts as one
of the great mathematicians of this century.
His many creative and fundamental
contributions to a vast variety of mathematical
fields are so wide-ranging that I cannot even attempt
to treat them either completely or in any detail.
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.
Apart from 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.
Let me state here that I do not claim
any personal relations with Kolmogorov.
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:
P.M.B. Vitanyi, Andrei Nikolaevich Kolmogorov,
CWI Quarterly,
1(1988), pp. 3-18.
See also references in Section 1.6 of
M. Li and P.M.B. Vitányi,
An Introduction to Kolmogorov Complexity
and its Applications,
Springer-Verlag, New York, 1993 (xx + 546 pp). (This is Section 1.13
in the Second
Edition of 1997.)
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.''
K. treated her as his mother until her death
in 1950 at Komarovka (his dacha) at the age of 87.
From his mother's side K. was of aristocratic
stock, his grandfather Yakov Stephanovitch Kolmogorov
was a district head of the nobles in Uglich.
He spent his early years (before the
revolution of 1917) at the family estate.
The sources are less clear about his father.
Apparently, K.'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.''
K. 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, K. 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 K. 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 K. 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 K.
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 K.
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 K.'s initial contacts with Aleksandrov
stayed very limited at the time.
K. 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.
K. anticipated to a large
extent
A. Heyting
's formalization of intuitionistic reasoning,
and made a more definite correlation between
classical and intuitionistic mathematics.
K. 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 K. 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 K.'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 K.'s later synthesis
of information theory and ergodic theory.
K.'s many
contributions in the theory of probability and statistics
made him generally acknowledged as
the foremost representative of this discipline.
In 1931 K.'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,
Poincaré
and Bashelier, Fokker,
Planck,
Smolukhovski
and
Chapman. Their particular equations for
individual problems in physics, informally obtained,
followed as special cases in K.'s theory. A long series
of subsequent publications followed, by K.
and his followers, among which
a paper by K. 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 K.'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, K. 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 K. This raised the problem of where
to continue his research.
Aleksandrov was instrumental in securing for K. 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 K. 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
K. 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 K. and
Aleksandrov. Says Aleksandrov: ``in 1979 this
friendship [with K.] 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 K.: ``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.''
K. 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. K.,
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.
K. 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:
K. 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. K. 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 K.'s aunt Vera Yakovlevna. A short time later,
Masha Barbanova, who had been K.'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 K.,
``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 K. 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 K. clad only in shorts
outskied every other participant.)
In 1930-1931 K. and Aleksandrov were mainly abroad. The year 1930
they spent both at Gottingen. Here K. had contacts with
R. Courant
on limit theorems, with
H. Weyl
on intuitionistic logic,
and with
E. Landau on function theory.
K. 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,
K. discovered a few weeks later
exactly the same result with the same proof by
Besicovitch in Fundamenta
Mathematicae. The summer both K. and Aleksandrov visited
Caratheodory
at Munich (measure theory), and were invited
to stay with
Frechet
on the Mediterranean (to work on
probability theory in K.'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 K. stayed on until December,
and had some meetings with Borel and P. Lévy,
especially the last. While K. 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, K. discovered the notion
of cohomology and founded the theory of cohomological
operations. The work of K. 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, K.'s attention was drawn to the mechanics of turbulence.
In the hands of K. 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, K. 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 K.'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). K. 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".
K.'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 ,
K. showed that the material gathered by followers
of Stalin's proteg e 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, for whom K.
had 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 K. during the second world war.
In the post-war period K. 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, K.'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 K.'s pupil Arnol'd and by Moser,
what is now known as the study of ``KAM-tori.''
Subsequent computational studies aptly confirm K.'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 Uspenskii he formulated the
important notion of Kolmogorov-Uspenskii 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 K.'s
pupils or pupils of K.'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, K. 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 K. 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 K. 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 K. 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 K. 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 K. 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
K. 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 K. 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 K. started to refer
to it from 1968 onward, even though
the attribution ``Kolmogorov''
complexity seems to have stuck.
Says K.: ``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.''
One of the last papers of K. was on the topic of algorithmic
information theory - a paper together with Uspenskii published
in 1987.
For a comprehensive introduction and a survey of the astonishing
range of applications
of Kolmogorov complexity, see
M. Li and P.M.B. Vitányi,
An Introduction to Kolmogorov Complexity
and its Applications,
Springer-Verlag, New York, 1993 (xx + 546 pp).
As a Teacher
K.'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 K. 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 K., 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 K.
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 K. became head of the mathematical section
of a joint syllabus committee of the USSR Academy
of Sciences and that of Pedagogical Sciences.
K. 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 K.'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,
``K. 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
K. 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.
K.'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-L of. 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
K. 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 K. 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 K. 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 K. 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 K. 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 K.
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, K. 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 K. 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.
This page is maintained by
Paul Vitanyi,
at CWI
and was last modified on January 24, 1996.