For more information about this meeting, contact 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 |