arXiv:0801.0354 Abstract | arXiv Analytics

arXiv:0801.0354 [math.LO]Abstract References Reviews Resources

Kolmogorov complexity in perspective

Published 2008-01-02Version 1

We survey the diverse approaches to the notion of information content: from Shannon entropy to Kolmogorov complexity. The main applications of Kolmogorov complexity are presented namely, the mathematical notion of randomness (which goes back to the 60's with the work of Martin-Lof, Schnorr, Chaitin, Levin), and classification, which is a recent idea with provocative implementation by Vitanyi and Cilibrasi.

Comments: 37 pages

Categories: math.LO, cs.CC, cs.IT, math.IT

Keywords: kolmogorov complexity, perspective, main applications, shannon entropy, diverse approaches

Related articles: Most relevant | Search more

arXiv:1301.3392 [math.LO] (Published 2013-01-15)

The axiomatic power of Kolmogorov complexity

Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren

arXiv:0801.0349 [math.LO] (Published 2008-01-02)

Church, Cardinal and Ordinal Representations of Integers and Kolmogorov complexity

Marie Ferbus-Zanda, Serge Grigorieff

arXiv:0901.3933 [math.LO] (Published 2009-01-26, updated 2014-08-10)

Kolmogorov complexity and the Recursion Theorem