Effective Hausdorff dimension

Summary

Abstract. We continue the study of effective Hausdorff dimension as it was initiated by Lutz. Whereas he uses a generalization of martingales on the Cantor space to introduce this notion we give a characterization in terms of effective s-dimensional Hausdorff measures, similar to the effectivization of Lebesgue measure by Martin-Löf. It turns out that effective Hausdorff dimension allows to classify sequences according to their ‘degree’ of algorithmic randomness, i.e., their algorithmic density of information. Earlier the works of Staiger and Ryabko showed a deep connection between Kolmogorov complexity and Hausdorff dimension. We further develop this relationship and use it to give effective versions of some important properties of (classical) Hausdorff dimension. Finally, we determine the effective dimension of some objects arising in the context of computability theory, such as degrees and spans.

§1. Introduction. Generally speaking, the concepts of Hausdorff measure and dimension are a generalization of Lebesgue measure theory. In the early 20th century, Hausdorff [9] used Caratheodory's construction of measures to define a whole family of outer measures. For examining a set of a peculiar topological or geometrical nature Lebesgue measure often is too coarse to investigate the features of the set, so one may ‘pick’ a measure from this family of outer measures that is suited to study this particular set. This is one reason why Hausdorff measure and dimension became a prominent tool in fractal geometry.

Hausdorff dimension is extensively studied in the context of dynamical systems, too. On the Cantor space, the space of all infinite binary sequences, the interplay between dimension and concepts from dynamical systems such as entropy becomes really close. Results of Besicovitch [3] and Eggleston [7] early brought forth a correspondence between the Hausdorff dimension of frequency sets (i.e., sets of sequences in which every symbol occurs with a certain frequency) and the entropy of a process creating such sequences as typical outcomes. Besides, under certain conditions the Hausdorff dimension of a set in the Cantor space equals the topological entropy of this set, viewed as a shift space.