Kolmogorov complexity in perspective part I

information theory and randomness

Marie Ferbus-Zanda

Serge Grigorieff

pp. 57-94

in: Jacques Dubucs, Michel Bourdeau (eds), Constructivity and computability in historical and philosophical perspective, Berlin, Springer, 2014

Abstract

We survey diverse approaches to the notion of information: from Shannon entropy to Kolmogorov complexity. Two of the main applications of Kolmogorov complexity are presented: randomness and classification. The survey is divided in two parts in the same volume. Part I is dedicated to information theory and the mathematical formalization of randomness based on Kolmogorov complexity. This last application goes back to the 1960s and 1970s with the work of Martin-Löf, Schnorr, Chaitin, Levin, and has gained new impetus in the last years.