Kolmogorov complexity as a language

Alexander Shen 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The notion of Kolmogorov complexity (=the minimal length of a program that generates some object) is often useful as a kind of language that allows us to reformulate some notions and therefore provide new intuition. In this survey we provide (with minimal comments) many different examples where notions and statements that involve Kolmogorov complexity are compared with their counterparts not involving complexity.
Type de document :
Communication dans un congrès
CSR: Computer Science Symposium in Russia, Jun 2011, Saint Petersburg, Russia. 6th International Computer Science Symposium in Russia, pp.105-119, 2011, 〈http://logic.pdmi.ras.ru/csr2011/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00845801
Contributeur : Andrei Romashchenko <>
Soumis le : mercredi 17 juillet 2013 - 18:05:24
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

  • HAL Id : lirmm-00845801, version 1
  • ARXIV : 1102.5418

Collections

Citation

Alexander Shen. Kolmogorov complexity as a language. CSR: Computer Science Symposium in Russia, Jun 2011, Saint Petersburg, Russia. 6th International Computer Science Symposium in Russia, pp.105-119, 2011, 〈http://logic.pdmi.ras.ru/csr2011/〉. 〈lirmm-00845801〉

Partager

Métriques

Consultations de la notice

97