Abstract:
We present a brief survey of results on relations between the Kolmogorov
complexity of infinite strings and several measures of information
content (dimensions) known from dimension theory, information
theory or fractal geometry.
Special emphasis is laid on bounds on the complexity of strings in
constructively given subsets of the Cantor space. Finally, we compare
the Kolmogorov complexity to the subword complexity of infinite
strings.