Computable symbolic dynamics

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

May 26, 2009

This is the abstract of my talk at a workshop on algorithmic randomness at the University of Wisconsin, May 27–31, 2009.

Abstract

Let G be a computable group, and let A be a finite alphabet. By a G-subshift we mean a nonempty subset of A^{G} which is topologically closed and closed under the action of G. It can be shown that any G-subshift X is defined by a countable set E of excluded finite configurations. If E is finite, we say that X is of finite type. If E is computable, we say that X is of computable type. It can be shown that most or all G-subshifts which arise in practice are of computable type. Let X be of computable type, and let P (X) be the problem of finding a point of X. If X is minimal (i.e., every orbit is dense) and of computable type, then P (X) is algorithmically solvable (a result of Michael Hochman). Let us say that X is d-dimensional if G = ℤ^{d}. If X is 1-dimensional and of computable type, then P (X) can be of any desired degree of unsolvability (a result of Joseph Miller). If X is 2-dimensional and of finite type, then P (X) can be of any desired degree of unsolvability (my result). The 1-dimensional subshifts of computable type are precisely those which can be obtained as projections of 2-dimensional subshifts of finite type (a result of Alexander Shen).