Logo image
Sign in
Topological Arguments for Kolmogorov Complexity
Journal article   Open access   Peer reviewed

Topological Arguments for Kolmogorov Complexity

Andrei Romashchenko and Alexander Shen
Theory of Computing Systems, Vol.56(3), pp.513-526
01/01/2015

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.
url
Find in HALView

Metrics

1 Record Views

Details

Logo image