Abstract:
Exact constructive dimension as a generalisation of Lutz’s
[Lut00, Lut03] approach to constructive dimension was recently
introduced in [Sta11]. 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 [Hit02, Hit05, Sta98] (see also [DH10, Section 13.6]) where it is
shown that the asymptotic Kolmogorov complexity of infinite
sequences in
∑02-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
∑02-definable sets via the exact dimension of the sets.