Exact Constructive and Computable Dimensions

Abstract

In this paper we derive several results which generalise the constructive dimension of (sets of) infinite strings to the case of exact dimension. We start with proving a martingale characterisation of exact Hausdorff dimension. Then using semi-computable super-martingales we introduce the notion of exact constructive dimension of (sets of) infinite strings. This allows us to derive several bounds on the complexity functions of infinite strings, that is, functions assigning to every finite prefix its Kolmogorov complexity. In particular, it is shown that the exactHausdorff dimension of a set of infinite strings lower bounds the maximumcomplexity function of strings in this set. Furthermore,we showa result bounding the exact Hausdorff dimension of a set of strings having a certain computable complexity function as upper bound.