View source for Andrey Nikolaevich Kolmogorov

==Later Years: 1960-1987==

[[Image:kolmogorov1.jpg|thumb|150px|left|F1|The older Kolmogorov]]
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.'

[[Image:kolmogorovstructurefunction.jpg|thumb|300px|right|F1|Kolmogorov's lecture introducing the Structure function at the meeting of the Bernoulli society in Tallinn, Estonia, 1973]]
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 <math>\Phi_x(k)</math> of a
natural number <math>k</math>---the log of minimal cardinality of <math>x</math>-containing
sets that allow definitions of complexity at most <math>k\ .</math>
If the element <math>x</math> itself allows a simple definition,
then the function <math>\Phi</math> drops to 1
even for small <math>k\ .</math>
Lacking such definition, the element is "random" in a negative sense.
But it is positively "probabilistically random" only when function
<math>\Phi</math> having taken the value <math>\Phi_0</math> at a relatively small
<math>k=k_0\ ,</math> then changes approximately as <math>\Phi(k)=\Phi_0-(k-k_0)\ .</math>"

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).