Symbolic dynamics: entropy = dimension = complexity

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/

July 21, 2011

This is my abstract for an invited talk at the Asian Initiative for Infinity, Workshop on Infinity and Truth, at the Institute for Mathematical Sciences, National University of Singapore, July 25–29, 2011.

We prove some fundamental results in symbolic dynamics. Let G be a countable semigroup, specifically G = (ℕ^{d}, +) or G = (ℤ^{d}, +) where d is a positive integer. Let A be a finite set of symbols. A G-subshift is a nonempty set X ⊆ A^{G} which is G-invariant and topologically closed. Note that we impose no finiteness or computability hypothesis on X. We show that, with respect to the standard metric on X, the Hausdorff dimension of X coincides with the effective Hausdorff dimension of X and with the topological entropy of X. We obtain a sharp characterization of the Hausdorff dimension of X in terms of the Kolmogorov complexity of the finite configurations of symbols which occur in X.