Le jeu de tuiles

D´efinition 1:

Pav´e : Un poly`edre qui servira `a paver Rn. Dans le cas de Z2, on parle de tuile.

Tuile de Wang : Un carr´e avec des cˆot´es color´es.

Jeu de tuiles : Un sous ensemble de Z4, chacun des quadruplets correspondant `a un ensemble

de quatre couleurs qui d´efinissent une tuile. On notera  un tel ensemble de tuiles dans la suite

du document.

Configuration : Application de Z2 !  . A chaque point du plan on associe une et une seule

tuile de 

Motif : Restriction d’une configuration `a un domaine fini de Z2. Pour plus de facilit´e, nous

noterons : mot(Pa) l’ensemble des motifs d’un pavage Pa. On notera de la mˆeme fa¸con : mot(Pa)n

les motifs carr´es de taille n de Pa.

Motif valide : Motif dans lequel, lorsque deux tuiles sont voisines, le contact est de la mˆeme

couleur.

Pavage du plan : Configuration dans laquelle tout motif extrait est valide.

On peut tout de suite ´etablir une notation ´evidente apr`es ces d´efinitions. Comme une configuration est

une application de Z2 dans  , l’ensemble des configurations est donc Z2 . Nous noterons donc de la sorte

cet ensemble.

Concernant les motifs, nous pourrons sans restriction, nous restreindre `a un motif carr´e, ´etant donn´e que

tout motif est un sous ensemble d’un motif carr´e.

1.2 P´eriodicit´e et d´ecidabilit´e

Le probl`eme du pavage du plan, qui s’attache `a savoir si un jeu de tuiles donn´e permet un pavage du

plan, a ´et´e introduit par Wang dans le but de prouver la satisfiabilit´e de formules logiques (donn´ees `a l’aide

de quantificateurs de Kahr). Berger a montr´e l’ind´ecidabilit´e d’un tel probl`eme, grˆace `a la d´ecouverte d’un

pavage non p´eriodique. Nous allons reprendre cette preuve par la suite. Commen¸cons d’abord par pr´esenter

la notion de p´eriodicit´e, puis par comprendre l’approche qu’a voulu suivre Wang.

D´efinition 2:

Pavage p´eriodique : Une configuration valide qui admet un vecteur (x, y) de p´eriodicit´e.

Cela revient `a dire que, quelle que soit la tuile consid´er´ee, une translation de (x, y) permet de

retrouver la mˆeme tuile.

On peut aussi penser qu’un pavage ne peut ˆetre p´eriodique que selon un seul axe (nous prendrons l’axe

x pour la suite). On parlerait alors de p´eriodicit´e simple selon l’axe x. Wang a prouv´e que si un jeu de

tuiles

...