Kolmogorov's Theory of Randomness (on the occasion of Kolmogorov's 95th anniversary)
Professor Leonid Levin, Computer Science Department, College of Arts and Sciences, Boston University, U.S.A.

Abstract: While fundamental to many sciences, the concept of randomness is quite paradoxical. Kolmogorov's analysis clarified it a great deal by revealing its computational nature. I will start with the paradoxes and continue with analysis by Kolmogorov and his followers. Despite major progress in the last decades, some open problems still remain, including to find a "perfect" definition for information. The plan of the talk:

1. Paradoxes of Probability
2. Complexity; Kolmogorov's solution
3. Universal Probability; Law of Randomness
4. Information and the Law of Independence
5. The above Probability Laws imply all others
6. Randomness and Independence; Conservation Inequalities
7. Information: the strongest invariant of probabilistic computations; Church's Thesis

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 23 June 1998.

back