Les tuiles de Wang, introduites dans les années 1960, sont une source inépuisable de problèmes indécidables. Il s'agit de tuiles carrées unitaires aux bords colorés et à l'orientation fixée, qui peuvent être placées côté à côté si elles partagent la même couleur sur leur bord commun. De nombreux problèmes de décision impliquant des tuiles de Wang suivent la même structure globale : étant donné un ensemble fini de tuiles de Wang, existe-t-il un algorithme permettant de déterminer si elles recouvrent une forme particulière ou un sous-ensemble de la grille infinie ? Si on souhaite un pavage de la grille entière, il s'agit du problème du domino, dont on sait qu’il est indécidable pour Z^2 et beaucoup d'autres groupes. Dans cet exposé, nous nous concentrons sur les pavages de chemins infinis (les « snake tilings »). On peut se demander s'il existe un pavage d'un chemin bi-infini auto-évitant sur la grille Z^2 (c’est le «  snake domino problem»). Je présenterai comment ce problème, étudié pour la grille infinie, peut être étendu à un groupe de type fini. Je présenterai quelques résultats qui illustrent comment le choix du groupe influe sur la décidabilité du problème du « snake domino ».

Il s'agit d'un travail en collaboration avec Nicolás Bitar