Ludwig Staiger

The Kolmogorov complexity function of an infinite word $\xi$ maps a natural

number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We

investigate the maximally achievable complexity function if $\xi$ is taken

from a constructively describable set of infinite words. Here we are

interested ...
more >>>

Ludwig Staiger

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 ...
more >>>