A Correspondence Principle for Exact Constructive Dimension

摘要

Exact constructive dimension as a generalisation of Lutz's [10,11] approach to constructive dimension was recently introduced in [19]. It was shown that it is in the same way closely related to a priori complexity, a variant of Kolmogorov complexity, of infinite sequences as their constructive dimension is related to asymptotic Kolmogorov complexity. The aim of the present paper is to extend this to the results of [8,9,18] (see also [2, Section 13.6]) where it is shown that the asymptotic Kolmogorov complexity of infinite sequences in ∑_2~0-definable sets is bounded by their Hausdorff dimension. Using Hausdorff's original definition one obtains upper bounds on the a priori complexity functions of infinite sequences in ∑_2~0-definable sets via the exact dimension of the sets.