# Séminaire

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

**References.**

- A. N. Kolmogorov and V. A. Uspensky.
*Algorithms and randomness.* -
SIAM J. Theory of Probability and Its Applications, vol. 32 (1987), pp.
389-412.
- 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.
- V. Uspensky and A. Semenov.
*Algorithms: Main Ideas and Applications.*
- Kluwer, 1993.