Algorithmic Information and Randomness

Martin-Löf's 1966 discovery that the theory of computing — and only the theory of computing — provides a satisfactory definition of the randomness of individual binary sequences was an early and dramatic indicator of things to come. In addition to providing hardware and software tools, computer science has developed deep theoretical tools that are conceptually transforming the foundations of several areas of science. Many of these tools, like randomness, arise from the growing unification of theoretical computer science with information theory.

I have recently been involved in the development of three types of effective fractal dimension outside of complexity theory: The first of these refines randomness and gives a new characterization of Kolmogorov complexity. The second sheds new light on normal sequences and data compression. The third shows that packing dimension (an ostensibly deeper fractal dimension developed in 1982) is an exact dual of Hausdorff dimension with similarly useful effectivizations.

I am currently working with colleagues and students to extend these developments, with applications to fractal geometry, dynamical systems, prediction, game theory, and, yes, computational complexity.

Bibliographies

John Hitchcock maintains online bibliographies on resource-bounded measure and effective fractal dimensions, with links to available papers in the latter.