Kolmogorov complexity in perspective

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
37 pages

Keywords

Logic, Computational Complexity, Information Theory

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/145176

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0801.0354
 http://arxiv.org/abs/0801.0354

Collections

arXiv