Linguistique de l’écrit

Revue internationale en libre accès

Livre | Chapitre

183261

Kolmogorov complexity in perspective part I

information theory and randomness

Marie Ferbus-Zanda Serge Grigorieff

pp. 57-94

Résumé

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.

Détails de la publication

Publié dans:

Dubucs Jacques, Bourdeau Michel (2014) Constructivity and computability in historical and philosophical perspective. Dordrecht, Springer.

Pages: 57-94

DOI: 10.1007/978-94-017-9217-2_3

Citation complète:

Ferbus-Zanda Marie, Grigorieff Serge, 2014, Kolmogorov complexity in perspective part I: information theory and randomness. In J. Dubucs & M. Bourdeau (eds.) Constructivity and computability in historical and philosophical perspective (57-94). Dordrecht, Springer.