Alexander Shen

Alexandre Shen works as a researcher in Montpellier (LIRMM, CNRS & University of Montepellier, France) and Moscow (on leave from Institute of information transmission problems, Moscow, Russia); his research topic is algorithmic information theory (Kolmogorov complexity) and algorithmic randomness (foundations of probability theory). Since 1981 he participates in the organization of Kolmogorov seminar in Moscow Univesity (started by Andrei N. Kolmogorov himself). For many years he worked in advanced math program in Moscow teaching mathematics and computer science and wrote some books for high school students: Algebra (with Israel M. Gelfand), Algorithms and Programs: Problems and Solutions and several others (not translated into English).

"Kolmogorov complexity and algorithmic information theory": It is usual to measure the amount of information in a message in bits. However, just the number of bits is not a good measure: message in 8-bit/char encoding and 16-bit/char have essentially the same information content even if the second one has twice more bits. More natural approach is to measure the "compressed size" of a message, but this depends on the compression technique; there are many compressor algorithms and none of them is "the right one". Andrei Kolmogorov and others (R. Solomonoff, and later G. Chaitin) found that one still have reasonably invariant definition of information content (=algorithmic complexity) and there is a rich theory around this notion. It also allows us to address the philosophical question: what is randomness? why we reject the fair coin hypothesis if we see 0101...0101 (1000 alternating bits) but some other sequence of 1000 bit may look plausible as the outcome of coin tossing? (Note that any two bit strings of length 1000 have the same probability if the coin is symmetric and coin tossings are independent). We will try to discuss both mathematical properties of algorithmic complexity and its use in the foundation of probability theory. Some common sense as a prerequisite will be useful for the second part.