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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00845801
Contributor : Andrei Romashchenko <>
Submitted on : Wednesday, April 3, 2019 - 2:33:36 PM
Last modification on : Friday, April 5, 2019 - 11:24:40 AM

File

1102.5418.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

149

Files downloads

60