| The two most important notions of fractal dimension are
Hausdorff dimension, developed by Hausdorff (1919), and packing dimension, developed by Tricot (1982).
Both dimensions have the mathematical advantage of being defined from measures, and both have yielded
extensive applications in fractal geometry and dynamical systems. In 2000, the speaker proved a simple
characterization of Hausdorff dimension in terms of gales, which are betting strategies that generalize
martingales. Imposing various computability and complexity constraints on these gales produces a
spectrum of effective versions of Hausdorff dimension, including constructive, computable,
polynomial-space, polynomial- time, and finite-state dimensions. Work by several investigators has
already used these effective dimensions to shed light on a variety of topics in theoretical computer
science, including algorithmic information theory, computational complexity, prediction, and data
compression. Constructive dimension has also been discretized, assigning a dimension to each finite
binary string in a way that arises naturally from Hausdorff and constructive dimensions and gives the
unexpected characterization that the Kolmogorov (program-size) complexity of a string is just its
length times its dimension. We survey these developments, along with a more recent result by Athreya,
Hitchcock, Mayordomo and the speaker showing that packing dimension -- previously thought to be much
more complex than Hausdorff dimension -- admits a gale characterization that is an exact dual of that
of Hausdorff dimension. This talk is intended for nonspecialists. No prior knowledge of fractal
dimension or martingales will be assumed. |