Complexity and Robustness of Tilings with Random Perturbations

par Léo Gayral (Université Toulouse III - Paul Sabatier)

vendredi 23 juin 2023, 14:00 → 17:15 Europe/Paris

Salle Katherine Johnson, bâtiment 1R3 (Institut de Mathématiques de Toulouse)

The central question of my work is that of the robustness to perturbations of tilings defined by local rules. Here, a tiling refers to a labelling of the grid ${\mathbb{Z}}^d$ by a finite alphabet, with neighbourhood rules determining which symbols can be juxtaposed, like puzzle pieces. When the number of rules is finite, we obtain a Subshift of Finite Type (or SFT). Starting from dimension $d=2$, complex structures (aperiodic, hierarchical, self-similar) can appear for certain choices of local rules. The challenge is then to know to what extent these structures are preserved when a small proportion of perturbations is allowed.

The challenge here is twofold. Firstly, for computer scientists, such structures can be used to encode computational models (i.e. computers) such as Turing machines. In information theory, it is natural to ask whether a signal can be transmitted in a noisy environment, and by extension whether it is physically possible to create a computational model that will produce correct results despite rare but inevitable localised faults. Secondly, for physicists, such structures are comparable to those of quasicrystals, materials that are highly ordered but have no crystalline (i.e. periodic) structure, and for which it is still difficult to propose a theoretical model explaining their formation. In my presentation, I will expose some key ideas and results related to both of these viewpoints.