Kolmogorov complexity as a language - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2011

Kolmogorov complexity as a language

Alexander Shen


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.
Fichier principal
Vignette du fichier
1102.5418.pdf (135.96 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00845801 , version 1 (03-04-2019)



Alexander Shen. Kolmogorov complexity as a language. CSR: Computer Science in Russia, Jun 2011, Saint Petersburg, Russia. pp.105-119, ⟨10.1007/978-3-642-20712-9_9⟩. ⟨lirmm-00845801⟩
105 View
133 Download



Gmail Mastodon Facebook X LinkedIn More