Back to the root file of my research overview.

Algorithmic Information Theory

Kolmogorov Complexity remained my interest for many years. Complexity K(x/y) of a string x given y is the minimal length of a binary program transforming y into x . Solomonoff and Kolmogorov have shown K(x/y)+O(1) is invariant across programming languages. There were problems with basic concepts. E.g., mutual information I(x:y)=K(y)-K(y/x) was not known to be symmetric or even monotone when y is replaced with f(y) (as with f(a,b)=a ). I started my work in the area by proving in 1967 these properties with O(log K(x,y) ) accuracy. Kolmogorov proved this result independently and presented our work to Moscow Math. Society ( [Kolmogorov 68], the proof in [Zvonkin, Levin 70]). (It took a few months to get an appointment with Kolmogorov to show my result. When we met, it turned out he just found his own proof. He did not know in advance the statement of my result, only that it was on complexity. While I came to the question by myself, Kolmogorov was emphasizing the problem publicly before me.) [Levin 74] gives a modification of K(x) where such relationships are exact.

While fundamental in many areas of Science, randomness is really ``native'' to Computer Science. The computational nature of randomness was clarified by Kolmogorov (after important preliminary ideas, most notably of Laplace, v.Mises and Church). He and his followers (Martin-Lof, Schnorr, Gacs, myself, and others) have built in the 60s and early 70s the first successful theory of random objects. Kolmogorov tried to resolve paradoxes of Probability Theory by defining as random those binary sequences that have only prefixes of bounded deficiency of randomness d(x)=\|x\|-K(x)=O(1) .

This did not quite work: the set was empty. I proposed in [Zvonkin, Levin 70] a variation KM(x) of Complexity which was proven in [Levin 73a], [Schnorr 73] to yield precisely those random sequences satisfying all computable probabilistic laws (Martin-Lof tests). This area is explained in a greater detail in [Kolmogorov Uspensky 86]. [Levin 74] shows that a set of sequences has measure zero if and only if it consists of low complexity sequences and sequences with infinite information about a single common sequence. Together with some information conservation inequalities of [Levin 74], this resolves some tricky foundational issues of Probability. [Levin 76a] extended randomness tests from computable to enumerable distributions. This is technically involved, but allows to include as a special case other important concepts like mutual information. [Levin 76b] gave a uniform description to a considerable variety of complexity measures found to date and to all other possible variations. I found a number of other theorems and concepts in this area which I cannot describe all here. [Levin 84] gives a detailed (but very technical) account.