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

• Course 1 (17.09.2015, 15:45-17:45, N.A.) Elements of symbolic dynamics, part I.
• Introduction: why study tilings ? [pdf]
Cantor space, two definitions of subshifts, SFT.
• Course 2 (24.09.2015, 15:45-17:45, N.A.) Elements of symbolic dynamics, part II.
• Sliding block codes, conjugacy.
Examples of SFTs, sofic subshifts.
One dimensional SFTs and sofic susbhifts.
• Course 3 (01.10.2015, 15:45-17:45, N.A.) Robinson's tiling and Mozes construction.
• Periodicity and complexity function.
Robinson's tiling, Mozes result (in a nutshell) [pdf].
• Course 4 (08.10.2015, 15:45-17:45, N.A.) Decidability issues.
• Turing machines inside SFTs, undecidability of the Domino problem [pdf].
• Course 5 (15.10.2015, 15:30-18:30, T.F.) The Cut and Project method [pdf].
• Course 6 (05.11.2015, 15:30-18:30, T.F.) Quasicrystals: formation (self-assembly and flip dynamics) [pdf].
• Course 7 (19.11.2015, 15:30-18:30, M.S.) Simulation theorem.
• Course 8 (26.11.2015, 15:45-17:45, M.S.) Entropy.
• Course 9 (03.12.2015, 15:30-18:30, M.S.) Coding of dynamical systems.
• Course 10 (17.12.2015, 15:45-17:45, M.S.) Determinism, expansivity and cellular automata.
• ### Bibliography

• Courses 1 and 2: Elements of symbolic dynamics
• [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. Springer-Verlag, Berlin, 1998. One-sided, two-sided and countable state Markov shifts.
• [Rob91] Arthur Robinson. Symbolic Dynamics and Tilings of Rd. Proceedings of Symposia in Applied Mathematics
• Courses 3 and 4: Aperiodicity and undicidability
• [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 Goodman-Strauss : 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(1-3):259–264, 1996.
• ### Research articles

1. [pdf] E. Jeandel and G. Theyssier, Subshifts as models for MSO logic (2013)
2. [pdf] J. Kari, The Nilpotency Problem of One-Dimensional Cellular Automata (1992)
3. [pdf] and [pdf] W. Hanf and D. Myers, Nonrecursive Tilings of the Plane. I and II (1974)
4. [pdf] Robert Ammann, Branko Grünbaum, G. C. Shephard, Aperiodic tiles (1992)
5. (chosen by Antoine)
6. [pdf] Antoine Julien, Complexity and cohomology for cut and projection tilings (2010)
7. [pdf] P. Kasteleyn, The statistics of dimers on a lattice (1961)
8. [pdf] R. Kenyon, Tiling a polygon wih parallelogram (1993)
9. (chosen by Yassine)
10. [pdf] M. Luby, D. Randall and A.J. Sinclair, Markov chain algorithms for planar lattice structures (2001)
11. (chosen by Damien)
12. [pdf] Dave Bayer, Persi Diaconis, Trailing the dovetail shuffle to its lair (1992)
13. (chosen by Nam)
14. [pdf] M. Hochman, Universality in Multidimensional Symbolic Dynamics (2009)
15. [pdf] R. Pavlov and M. Schraudner, Entropies realizable by block gluing shifts of finite type
16. [pdf] W. Jockusch, J. Propp , P. Shor, Random Domino Tilings and the Arctic Circle Theorem (1995)
17. [pdf] Jarkko Kari and Michal Szabados, An Algebraic Geometric Approach to Nivat’s Conjecture (2015)
18. [pdf] Van Cyr and Bryna Kra, Nonexpansive Z^2-Subdynamics and Nivat's Conjecture (2014)
19. [pdf] Tom Meyerovitch, Growth-type invariants for Z^d subshifts of finite type and arithmetical classes of real numbers (2010)
20. [pdf] Tom Meyerovitch and Ronnie Pavlov, Entropy and measures of maximal entropy for axial powers of subshifts (2014)
21. [pdf] Nick Ormes and Ronnie Pavlov, Extender sets and multidimensional subshifts (2013)
22. [pdf] Van Cyr and Bryna Kra, The automorphism group of a minimal shift of stretched exponential growth (2015)