A Tight Upper Bound on Kolmogorov Complexity by Hausdorff Dimension and
Uniformly Optimal Prediction
Ludwig Staiger
The present paper links the concepts of Kolmogorov complexity
(in Complexity theory) and Hausdorff dimension (in Fractal
geometry) for a class of recursive (computable) sets of
infinite strings.
It is shown that the complexity of an infinite string contained
in a \Sigma_2-definable set of strings is upper bounded
by the Hausdorff dimension of this set and that this upper
bound is tight. Moreover, we show that there are computable
gambling strategies guaranteeing a uniform prediction quality
arbitrarily close to the optimal one estimated by Hausdorff
dimension and Kolmogorov complexity provided the gambler's
adversary plays according to a sequence chosen from a
\Sigma_2-definable set of strings.
We provide also examples which give evidence that our results
do not extend further in the Arithmetical hierarchy.