Topological arguments for Kolmogorov complexity

Andrei Romashchenko 1, * Alexander Shen 1
* Auteur correspondant
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Communication dans un congrès
AUTOMATA, Sep 2012, La Marana, Furiani, France. 18th International Workshop on Cellular Automata and Discrete Complex Systems, pp.127-132, 2012, 〈http://www.i3s.unice.fr/automata2012/〉
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736127
Contributeur : Andrei Romashchenko <>
Soumis le : jeudi 27 septembre 2012 - 16:10:10
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 18:18:05

Fichier

topology-automata.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : lirmm-00736127, version 1

Collections

Citation

Andrei Romashchenko, Alexander Shen. Topological arguments for Kolmogorov complexity. AUTOMATA, Sep 2012, La Marana, Furiani, France. 18th International Workshop on Cellular Automata and Discrete Complex Systems, pp.127-132, 2012, 〈http://www.i3s.unice.fr/automata2012/〉. 〈lirmm-00736127〉

Partager

Métriques

Consultations de la notice

151

Téléchargements de fichiers

218