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 Seminar |
|---|
| 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 |
|---|
