Recursion theory and symbolic dynamics

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.personal.psu.edu/t20 t20@psu.edu

October 18, 2013

This is my abstract for Computational interpretations of mathematical theorems, a Royal Society International Scientific Seminar, November 25-26, 2013.

There are many connections between d-dimensional symbolic dynamics and Turing’s theory of computability and unsolvability. Given a d-dimensional system of finite type, consider the associated orbit problem, i.e., the problem of finding at least one orbit of the system. For d = 1 it is well known that the orbit problem is algorithmically solvable, because one can find a periodic orbit. Meyers in 1974 constructed a 2-dimensional system of finite type for which the orbit problem is algorithmically unsolvable, i.e., no orbit of the system is computable in the sense of Turing. In a paper to appear in Ergodic Theory and Dynamical Systems, I improved Meyers’s result by constructing 2-dimensional systems of finite type for which the orbit problem has any desired degree of unsolvability. In another direction, recall that the Kolmogorov complexity of a finite mathematical object τ may be roughly described as the size, measured in bits, of the smallest Turing machine program which describes τ. In a recent paper to appear in Theory of Computing Systems, I obtained a sharp characterization of the topological entropy of a d-dimensional symbolic system X in terms of the Kolmogorov complexity of the finite configurations of symbols which occur in X. I also showed that the topological entropy of X coincides with the Hausdorff dimension of X with respect to the standard metric.