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 exact Hausdorff dimension
of a set of infinite strings lower bounds the maximum complexity function
of strings in this set. Furthermore, we show a result bounding the exact
Hausdorff dimension of a set of strings having a certain computable
complexity function as upper bound.

Obviously, the Hausdorff dimension of a set of strings alone without any
computability constraints cannot yield upper bounds on the complexity of
strings in the set. If we require, however, the set of strings to be
$\Sigma_{2}$-definable several results upper bounding the complexity by the
exact Hausdorff dimension hold true. First we prove that for a
$\Sigma_{2}$-definable set with computable dimension function one can
construct a computable -- not only semi-computable -- martingale succeeding
on this set. Then, using this result, a tight upper bound on the prefix
complexity function for all strings in the set is obtained.

The references [Hit05], [HLM04], and [HLM08] were added:

Hitchcock's Theorem 4.4 [Hit05] was compared with Theorem 3 in Section 1.4.3.

In the introduction and Section 6 the connections of this work with the references on scaled dimension [HLM04], [HLM08] were briefly discussed.

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 exact Hausdorff dimension
of a set of infinite strings lower bounds the maximum complexity function
of strings in this set. Furthermore, we show a result bounding the exact
Hausdorff dimension of a set of strings having a certain computable
complexity function as upper bound.

Obviously, the Hausdorff dimension of a set of strings alone without any
computability constraints cannot yield upper bounds on the complexity of
strings in the set. If we require, however, the set of strings to be
$\Sigma_{2}$-definable several results upper bounding the complexity by the
exact Hausdorff dimension hold true. First we prove that for a
$\Sigma_{2}$-definable set with computable dimension function one can
construct a computable -- not only semi-computable -- martingale succeeding
on this set. Then, using this result, a tight upper bound on the prefix
complexity function for all strings in the set is obtained.