Topological arguments for Kolmogorov complexity

Alexander Shen
(CNRS and LIRMM, France)
Andrei Romashchenko
(CNRS and LIRMM, France)

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.

In Enrico Formenti: Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires (AUTOMATA&JAC 2012), La Marana, Corsica, September 19-21, 2012, Electronic Proceedings in Theoretical Computer Science 90, pp. 127–132.
Published: 13th August 2012.

ArXived at: http://dx.doi.org/10.4204/EPTCS.90.10 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org