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.


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.


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


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)