Pavages du plan : indecidabilite et periodicite.
Résumé
We study some decision problems concerning the tiling of the plane with Wang tiles. We present a proof for the undecidability of the tiling problem for the whole plane, and also for the periodic tiling. In these poofs, an aperiodic tile set is constructed. We are interested in the second part in the link between the cardinality of possible tilings of the plane with a given tile set and the existence of a periodic tiling. We are also interested in the property of quasiperiodicity and prove that all tile sets that tile the plane, may tile the plane quasiperiodically.
Nous nous intéressons à des problèmes de décidabilité des pavages du plan par des tules de Wang. Nous étudions le problème du pavage du plan avec une tuile imposée à l'origine et nous montrons que ce problème est indécidable. Ensuite, nous donnons une preuve de l'indécidabilité du pavage du plan ; la démonstration de ce résultat nous permet d'exhiber un jeu de tuiles apériodique. Enfin, nous montrons l'indécidabilité du pavage périodique du plan. Nous étudions dans la suite des problèmes liés à la périodicité. Dans les constructions précédentes, nous avons vu qu'il existe au moins un jeu de tuiles apériodique. Ceci nous amène à nous intéresser au lien entre la cardinalité de l'ensemble des pavages possibles pour un certain jeu de tuiles et la périodicité d'un des pavages donné par ce jeu. Finalement, nous nous intéressons à la généralisation de la notion de périodicité qu'est la quasipériodicité et nous prouvons que tout ensemble de tuiles pavant le plan permet de le paver quasipériodiquement.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...