For more information about this meeting, contact Stephen Simpson.
| Title: | Tiling problems and 2-dimensional symbolic dynamics |
|---|
| Seminar: | Logic Seminar |
|---|
| Speaker: | Stephen G. Simpson, Pennsylvania State University |
|---|
| Abstract: |
|---|
| In 1959, in order to study certain problems in mathematical logic, Hao Wang introduced tiling problems. A Wang tile is a unit square with colored edges. Given a finite set of Wang tiles, consider the associated tiling problem, i.e., the problem of covering the plane with translates of the given tiles so that adjacent edges have matching colors. In 1965 Robert Berger obtained some difficult yet fundamental results concerning tiling problems. For instance, the problem of whether a given tiling problem has any solution whatsoever is algorithmically undecidable. In the 1990s it was realized that the study of tiling problems is equivalent to the study of 2-dimensional symbolic dynamical systems of finite type. Recent results based on the techniques of Berger have greatly illuminated the dynamical properties of such systems. For instance, Hochman and Meyerovitch proved that a positive real number is the entropy of such a system if and only if it is right recursively enumerable. The present seminar talk is intended as an introduction to 2-dimensional symbolic dynamics and tiling problems. Later in the semester our Shapiro visitor Alexander Shen will develop these topics in greater depth and detail. |
Room Reservation Information
| Room Number: | MB315 |
|---|
| Date: | 02 / 23 / 2010 |
|---|
| Time: | 02:30pm - 03:45pm |
|---|
