Compressibility and Kolmogorov Complexity
Stephen Binns, Marie Nicholson · Notre Dame Journal of Formal Logic · 2012
This paper continues the study of the metric topology on 2 N that was introduced by S. Binns. This topology is induced by a directional metric where the distance from Y ∈ 2 N to X ∈ 2 N is given by lim sup n C ( X ↾ n ∣ Y ↾ n ) n . This definition is closely related to the notions of effective Hausdorff and packing dimensions. Here we establish that this is a path-connected topology on 2 N and that under it the functions X ↦ dim H X and X ↦ dim p X are continuous. We also investigate the scalar multiplication operation that was introduced by Binns. The multiplication of a real X ∈ 2 N by an element α ∈ [ 0 , 1 ] represents a dilution of the information in X by a factor of α . Our main result is to show that every regular real is the dilution of a real of Hausdorff dimension 1. That is, that the information in every regular real can be maximally compressed.