Vendredi 16 mai 1997 - 14h00
Salle de conférences Michel Métivier

Vladimir A. Uspensky
(Moscow University and École Normale Supérieure de Lyon)  

Kolmogorov complexity and its applications to randomness

Kolmogorov complexity of a of a binary word, as Kolmogorov himself has defined it, is the length of the shortest program producing that word. Kolmogorov tried and succeeded to use that definition to create a new informatiom theory in parallel to Shannon's one. But he also intended to define on that base the notion of randomness. Unfortunately, it turned out that the original definition is not good for that goal (in particular, to define what a random infinite sequence is). To get a correct definition of an infinite binary sequence one needs to consider Kolmogorov complexity in a more broad sense: namely, as the length of the shortest description under some appropriate description mode.


  1. A. N. Kolmogorov and V. A. Uspensky. Algorithms and randomness. - SIAM J. Theory of Probability and Its Applications, vol. 32 (1987), pp. 389-412.
  2. V. A. Uspensky. Complexity and entropy: An introduction to the theory of Kolmogorov complexity. - O. Watanabe (Ed.). Kolmogorov Complexity and Computational Complexity. Springer, 1992. - pp. 85-102.
  3. V. Uspensky and A. Semenov. Algorithms: Main Ideas and Applications. - Kluwer, 1993.