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.