Prerequisites

Students are expected to know about basic notions of topology (open, closed and compact sets, distance) but also to be familiar with finite automata theory and computability theory.
Objective

The objective of this course is to illustrate how computability theory imposes some constraints  computability obstructions  on dynamical systems such as tiling systems, and how these obstructions often occur as the only ones.
Instructors

The three instructors will be Thomas Fernique, Mathieu Sablik and Nathalie Aubrun.
Evaluation

Three homework assignments and an oral presentation of a research article (details concerning the oral presentation will depend on the number of students).

Homework assignment 1 [pdf], duedate 10.25.2015 !!
(Tentative) Schedule
Cantor space, two definitions of subshifts, SFT.
Examples of SFTs, sofic subshifts.
One dimensional SFTs and sofic susbhifts.
Robinson's tiling, Mozes result (in a nutshell) [pdf].
Bibliography
 [LM95] Douglas A. Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York, NY, USA, 1995.
 [Kit98] Bruce P. Kitchens. Symbolic dynamics. Universitext. SpringerVerlag, Berlin, 1998. Onesided, twosided and countable state Markov shifts.
 [Rob91] Arthur Robinson. Symbolic Dynamics and Tilings of R^{d}. Proceedings of Symposia in Applied Mathematics
 [Ber66] Robert Berger. The undecidability of the domino problem. American Mathematical Society, 1966.
 [Rob71] Raphael Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12(3):177–209, 1971.
 [GS98] Chaim GoodmanStrauss : Matching rules and substitution tilings. Annals of Mathematics, 157:181–223, 1998.
 [Moz89] Shahar Mozes. Tilings, substitution systems and dynamical systems generated by them. Journal d’Analyse Mathématique (Jerusalem), 53:139–186, 1989.
 [Kar96] Jarkko Kari. A small aperiodic set of wang tiles. Discrete Mathematics, 160(13):259–264, 1996.
Research articles
 [pdf] E. Jeandel and G. Theyssier, Subshifts as models for MSO logic (2013)
 [pdf] J. Kari, The Nilpotency Problem of OneDimensional Cellular Automata (1992)
 [pdf] and [pdf] W. Hanf and D. Myers, Nonrecursive Tilings of the Plane. I and II (1974)
 [pdf]
Robert Ammann, Branko Grünbaum, G. C. Shephard, Aperiodic tiles (1992)(chosen by Antoine)
 [pdf] Antoine Julien, Complexity and cohomology for cut and projection tilings (2010)
 [pdf] P. Kasteleyn, The statistics of dimers on a lattice (1961)
 [pdf]
R. Kenyon, Tiling a polygon wih parallelogram (1993)(chosen by Yassine)
 [pdf]
M. Luby, D. Randall and A.J. Sinclair, Markov chain algorithms for planar lattice structures (2001)(chosen by Damien)
 [pdf]
Dave Bayer, Persi Diaconis, Trailing the dovetail shuffle to its lair (1992)(chosen by Nam)
 [pdf] M. Hochman, Universality in Multidimensional Symbolic Dynamics (2009)
 [pdf] R. Pavlov and M. Schraudner, Entropies realizable by block gluing shifts of finite type
 [pdf] W. Jockusch, J. Propp , P. Shor, Random Domino Tilings and the Arctic Circle Theorem (1995)
 [pdf] Jarkko Kari and Michal Szabados, An Algebraic Geometric Approach to Nivat’s Conjecture (2015)
 [pdf] Van Cyr and Bryna Kra, Nonexpansive Z^2Subdynamics and Nivat's Conjecture (2014)
 [pdf] Tom Meyerovitch, Growthtype invariants for Z^d subshifts of finite type and arithmetical classes of real numbers (2010)
 [pdf] Tom Meyerovitch and Ronnie Pavlov, Entropy and measures of maximal entropy for axial powers of subshifts (2014)
 [pdf] Nick Ormes and Ronnie Pavlov, Extender sets and multidimensional subshifts (2013)
 [pdf] Van Cyr and Bryna Kra, The automorphism group of a minimal shift of stretched exponential growth (2015)