Kolmogorov complexity and Hausdorff dimension. (English) Zbl 0789.68076

Staiger, Ludwig

Inf. Comput. 103, No. 2, 159-194 (1993).

This interesting note develops several formal relationships between program-size complexity of infinite strings and various measures of information content. The idea is to bound the complexity of a maximally complex string in a prescribed set of strings by the Hausdorff dimension as well as the entropy of that set. Then the Hausdorff dimension gives lower bounds to the Kolmogorov complexity, and under various recursivity conditions the entropy gives upper bounds. This approach can be used to generalize important theorems of P. Martin-Löf on Kolmogorov complexity. The author proves several theorems, gives numerous examples showing limitations of his results, and includes an extensive bibliography of 63 items.

Reviewer: A.A.Mullin (Huntsville)

MSC:

68Q30	Algorithmic information theory (Kolmogorov complexity, etc.)
28A78	Hausdorff and packing measures

Keywords:

set entropy; random sequence; Hausdorff dimension; Kolmogorov complexity; bibliography