Logo image
Se connecter
Topological arguments for Kolmogorov complexity
Article de revue

Topological arguments for Kolmogorov complexity

Alexander Shen et Andrei Romashchenko
Electronic proceedings in theoretical computer science, Vol.90(90), pp.127-132
13/08/2012

Résumé

Computer Science Computer Science, Theory & Methods Science & Technology Technology
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.

Indicateurs

1 Consultations de la notice

Détails

Logo image