Topological arguments for Kolmogorov complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2012

Topological arguments for Kolmogorov complexity

Abstract

We present several application of simple topological arguments in problems of Kolmogorov complexity. Basically we use the standard fact from topology that the disk is simply connected. It proves to be enough to construct strings with some nontrivial algorithmic properties.
Fichier principal
Vignette du fichier
topology-automata.pdf (113.15 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

lirmm-00736127 , version 1 (27-09-2012)

Identifiers

  • HAL Id : lirmm-00736127 , version 1

Cite

Andrei Romashchenko, Alexander Shen. Topological arguments for Kolmogorov complexity. AUTOMATA, Sep 2012, La Marana, Furiani, France. pp.127-132. ⟨lirmm-00736127⟩
118 View
241 Download

Share

Gmail Facebook X LinkedIn More