PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Mari Royer, Yakov Pesin, Anatole Katok, Svetlana Katok, Dmitri Burago.

Title:Computable symbolic dynamics
Seminar:Center for Dynamics and Geometry Seminars
Speaker:Steve Simpson, PSU
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 = 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
Date:03 / 16 / 2009
Time:03:30pm - 05:30pm