Indécidabilité, pavages et polyominos

Un polyomino est une figure finie simplement connexe obtenue en collant des carrés unité les uns aux autres arête à arête. Une famille de polyominos pave le plan si on peut recouvrir le plan euclidien avec des copies de ces polyominos sans chevauchement et sans trou. Dans cet exposé, on étudie le problème de décision suivant : étant donnée une famille finie de polyominos, pave-t-elle le plan ? Dans un premier temps, on redémontrera l’indécidabilité du problème à l’aide du Domino Problem, introduit par Wang en 1961. Puis, on s’intéressera à la famille de problèmes de décision indexée par la taille de la famille de polyominos et on montrera qu’il existe une frontière entre décidable et indécidable pour ce paramètre. On conclura par quelques problèmes ouverts intrigants et l’existence d’une famille de 5 polyominos qui pave le plan uniquement de manière non récursive.