Résumé de séminaire

Résumé :

The amount of information in a binary string is defined as the length of the minimum length of a computer program printing the string. For example, if we toss a fair coin 10000 times we obtain with high probability a string the amount of information in which is about 10000 bits. Intuitively, all this information is meaningless. Is it possible to define what is the amount of meaningful information in a string?

Références :

Nikolai Vereshchagin est professeur à l'université de Moscou, au Département de logique et théorie générale des algorithmes.

Home page : http://lpcs.math.msu.su/~ver/