# Meeting Details

Title: Computable symbolic dynamics Center for Dynamics and Geometry Seminars Steve Simpson, PSU 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 = Z^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).

### Room Reservation Information

Room Number: MB106 03 / 16 / 2009 03:30pm - 05:30pm