Around Kolmogorov Complexity: Basic Notions and Results

Alexander Shen 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Algorithmic information theory studies description complexity and randomness and is now a well known field of theoretical computer science and mathematical logic. There are several textbooks and monographs devoted to this theory where one can find the detailed exposition of many difficult results as well as historical references. However, it seems that a short survey of its basic notions and main results relating these notions to each other, is missing. This report attempts to fill this gap and covers the basic notions of algorithmic information theory: Kolmogorov complexity (plain, conditional, prefix), Solomonoff universal a priori probability, notions of randomness (Martin-L\"of randomness, Mises--Church randomness), effective Hausdorff dimension. We prove their basic properties (symmetry of information, connection between a priori probability and prefix complexity, criterion of randomness in terms of complexity, complexity characterization for effective dimension) and show some applications (incompressibility method in computational complexity theory, incompleteness theorems). It is based on the lecture notes of a course at Uppsala University given by the author.
Type de document :
Chapitre d'ouvrage
Measures of Complexity. Festschrift for Alexey Chervonenkis, Part II, Springer, pp.75-115, 2015, 978-3-319-21851-9. 〈10.1007/978-3-319-21852-6_7〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233758
Contributeur : Alexander Shen <>
Soumis le : mercredi 25 novembre 2015 - 17:11:06
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

Collections

Citation

Alexander Shen. Around Kolmogorov Complexity: Basic Notions and Results. Measures of Complexity. Festschrift for Alexey Chervonenkis, Part II, Springer, pp.75-115, 2015, 978-3-319-21851-9. 〈10.1007/978-3-319-21852-6_7〉. 〈lirmm-01233758〉

Partager

Métriques

Consultations de la notice

83