Kolmogorov complexity and Hausdorff dimension (Q2365758)

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.