Du carreau de Truchet au carreau de Wang : atteindre l’atome de l’apériodique et du calculable

Piste rouge Le 10 janvier 2018  - Ecrit par  Alain Busser, Patrice Debrabant Voir les commentaires

Le carreau de Truchet est un carré bicolore divisé selon une diagonale, carreau que l’on peut accoler à d’autres carreaux du même type en respectant (ou pas) la continuité de couleur sur les côtés adjacents. Celui de Wang est quadricolore, divisé selon les deux diagonales.
Ce type de légo semblait bien innocent jusqu’au jour où il s’avéra qu’il pouvait paver le monde (du calculable) [1].
En particulier, certains coffrets de ces légos permettent de paver le plan de manière inévitablement apériodique. Mais combien faut-il de légos différents au minimum ? Et quel est le type le plus simple de légo qui a ce potentiel ?

Nota Bene : cet article est associé à cet autre article plus contemplatif, consacré exclusivement aux pavages de Truchet, dont il partage l’introduction.

I) Les pavages de Truchet

A) Introduction

Les pavages de Truchet, au sens historique du terme, sont des pavages dont la tuile de base est un carré colorié avec un motif bicolore de part et d’autre d’une diagonale. Cette tuile peut être tournée d’un ou plusieurs quarts de tour.

Ces pavages ont été étudiés par Jean Truchet (1657 - 1729) (en religion le Père Sébastien, de l’ordre des Carmes).
Voici un exemple de tuile de base.

On a quatre orientations possibles :

Les mathématiciens spécialisés dans ce type de pavages adoptent souvent un point de vue qui consiste à modéliser la situation sans autoriser les rotations. On peut alors plutôt considérer que le jeu est constitué de 4 tuiles.

Voici alors le type de pavage que l’on peut obtenir :

Si on développe un pavage de Truchet d’un carré par symétries axiales successives, puis si on étend par périodicité, on obtient alors une figure du genre suivant :

Si enfin on respecte la continuité de couleur le long de côtés adjacents (autrement dit, si le pavage est un puzzle ou plutôt un domino bidirectionnel car la même forme de bord peut apparaître plusieurs fois), on peut obtenir ce type de pavage (appelé pavage de Truchet linéaire) :

Remarque : les figures dynamiques de cet article ont été créées avec le logiciel de géométrie dynamique DGPad.
On ne suppose ni sa connaissance ni son utilisation lors de la lecture de cet article. La façon de construire ces figures avec DGPad n’est pas détaillée.

En savoir plus sur DGPad

DGPad est un logiciel pour tablettes et PC écrit en Javascript développé par Eric Hakenholz. Il peut être utilisé sous forme d’une application web (sans aucune installation) à cette adresse : https://www.dgpad.net
Il existe aussi une version installée pour Mac et Linux, téléchargeable à cette adresse : http://carmetal.org/index.php/fr/testa-dgpad/application-pour-mac-et-linux
Les figures de l’introduction sont des copies d’écran de figures dynamiques présentées dans l’article associé.
Les figures dynamique DGPad ont été exportées avec tableau de bord, ce qui permet d’accéder à leur code source. Mais cela ne vaut pas pour les pavages de Kari et Culik, qui ont été programmés « directement » dans le code source (auquel cas le « code source » auquel on peut accéder n’est pas exactement le code source initial).

B) Pavages de Truchet multicolores

Pour l’instant, on a seulement considéré la famille des quatre tuiles de Truchet. Une généralisation consiste à envisager les jeux composés de carreaux isolés extraits de différentes familles, avec plusieurs couleurs.

Si on passe un cran au dessus, on arrive aux carreaux de Wang.

II) Les pavages de Wang

Les tuiles de Truchet sont constituées en coupant un carré en deux selon une diagonale. On peut généraliser ces tuiles en coupant le carré en quatre selon les deux diagonales. On a alors quatre région, que l’on peut colorier par des couleurs indépendantes. Comme pour les tuiles de Truchet, on peut imposer la
contrainte d’égalité de couleur entre tuiles le long des côtés
adjacents.
Si on ne prend que deux couleurs distinctes et adjacentes, on retrouve les tuiles de Truchet (et les pavages de Truchet multicolores).

Ces tuiles ont été introduites (puis explorées) par Wang en 1961. Elles sont communément appelées tuiles de Wang.

Les tuiles de Wang sont des carrés à bords distincts (traditionnellement colorés ou découpés) qui s’assemblent comme des pièces de puzzle dans le plan à deux dimensions.
Mais (contrairement à un puzzle) les pièces peuvent seulement être translatées (les rotations et les symétries ne sont pas permises), comme pour les tuiles de Truchet en place. Voici par exemple un jeu de tuiles :

Avec ces tuiles, on cherche à paver une zone rectangulaire du plan, voire le plan tout entier.
Avec le jeu de tuiles précédent, on peut réaliser le pavage suivant (qui est périodique [2]) :

Vision mosaïque vs vision puzzle

Remarque : les mêmes tuiles peuvent être vues comme des pièces de puzzle avec des bords découpés, ou coloriés différemment.

Voici par exemple un jeu de tuiles à bords découpés (et un équivalent coloré) :

Avec ces tuiles, on peut réaliser ce pavage :

Wang avait inventé ces tuiles pour incarner des notions abstraites de calculabilité et il pressentait certainement leur potentiel. Mais il restait à mesurer précisément ce dernier.
Dès leur introduction, Wang s’était intéressé au pavage du plan par ces tuiles. Et il s’était aventuré à conjecturer que le problème du pavage du plan par un jeu fini de dominos était décidable (autrement dit qu’il existait un algorithme capable de décider en temps fini si un jeu de tuiles peut paver ou non le plan).
Cette conjecture était la conséquence logique d’une autre conjecture : « Tout ensemble de tuiles qui pave peut paver périodiquement. ».

En fait, pour un ensemble de tuiles, il y a, a priori, 4 possibilités :

  • il ne pave pas ;
  • il ne pave que périodiquement ;
  • il pave périodiquement et apériodiquement ;
  • il ne pave que apériodiquement.

La question cruciale est de savoir s’il existe des ensembles de tuiles du quatrième type.
Car s’il n’en existe pas, alors le pavage du plan par un jeu fini de dominos est forcément décidable.

Idée de la preuve

On peut écrire un algorithme qui examine successivement les carrés de côtés 1, 2, ..., n, pour déterminer si ces carrés (en tant que parties du plan) sont pavables. Pour cela, l’algorithme évalue toutes les dispositions possibles, qui sont en nombre fini égal à $nombreDeTuiles^{n^2}$ et évalue également si l’on obtient un carré périodique parmi les pavages obtenus (c’est une contrainte sur les côtés qui peut être évaluée).

Cet algorithme s’arrête nécessairement au bout d’un temps fini, soit parce qu’il a trouvé un carré qui n’est pas pavable, soit parce qu’il a trouvé une période.

Tout cela semblait naturel et rassurant jusqu’à ce que cette conjecture soit réfutée en 1966 par Berger, un élève de Wang. La tuile…
Le sujet s’avérait ainsi plus complexe que prévu, et plus intéressant aussi.
Berger avait démontré que toute fonction calculable peut se calculer avec les dominos de Wang en montrant que toute machine de Turing peut s’exprimer avec des pavages de ce type.

Exemple : pavage de Wang pour calculer une addition unaire

Toute fonction calculable peut être rendue par un pavage de Wang.
Par exemple, on peut calculer une addition (codée en unaire) avec des dominos de Wang comme le montre le storyboard ci-dessous. Compléter le pavage avec les dominos aboutit à calculer l’addition.






Voici la figure interactive correspondante (les termes à additionner sont générés au hasard) :

Pavage de Wang pour l’addition unaire (HTML)
HTML - 12 ko

En d’autres termes, on peut dire que les dominos de Wang ont le potentiel du calculable.

Ceci étant posé, on pouvait alors reprendre les choses à l’envers et réfuter la conjecture initiale : il devait nécessairement exister des jeux de tuiles apériodiques

Un jeu de tuiles pavant le plan est dit apériodique s’il ne fournit que des pavages apériodiques.

L’existence de jeux apériodiques de tuiles étant acquise, on a naturellement cherché à en exhiber.
Berger avait initialement trouvé un jeu apériodique de 20 426 (!) tuiles. Il a réussi à réduire ce nombre à 104 tuiles. Puis Knuth a encore réduit ce nombre à 96.


Pour réduire encore le nombre de tuiles, différents chercheurs ont adapté des pavages apériodiques existants pour en faire des jeux apériodiques de tuiles de Wang.
Cliquer sur l’article suivant pour plus d’explications sur la manière de transformer un pavage géométrique « classique » apériodique en un pavage de Wang, et déplier le bloc pour voir le résultat.

http://grahamshawcross.com/2012/10/12/wang-tiles-and-aperiodic-tiling/

Galerie de pavages de Wang apériodiques dérivés de pavages apériodiques existants

  • Robinson, 1971 (4x6 = 24 tuiles)

Robinson a démontré que cet ensemble de 6 tuiles, qui sont exactement des tuiles de Wang mais présentées sous forme de pièces de puzzle, est apériodique.
Dans le formalisme adopté dans cet article, où l’on n’autorise pas les rotations, cela correspond à 26 dominos (tuiles de Wang) à glisser.

Dans ce pavage de Penrose, on part d’un pavage par flèche et chevron. L’ensemble de ces deux pavés est apériodique.

Malgré les angles, on peut en extraire ce jeu de tuiles de Wang :

  • Amman, 1986 (16 tuiles)

Amman a proposé un ensemble surprenant de deux motifs apériodiques, qui se situe un peu entre les pavages classiques et les pavages de Wang :

Ces motifs donnent ce jeu de tuiles de Wang :


Tous les pavages dérivés du bloc précédent sont obtenus et démontrés apériodiques par des considérations géométriques.
En 1995, Kari propose une méthode révolutionnaire pour obtenir un pavage apériodique. Celui-ci est de nature algébrique, et s’appuie sur une variante des machines de Turing, la machine de Mealy
Par cette méthode, il obtient un pavage apériodique à 14 tuiles (en fait 13, une des tuiles n’étant pas utilisée au final, comme il le démontrera plus tard).
Kulik adapte légèrement la méthode pour obtenir un autre pavage apériodique à 13 tuiles.

A chaque fois, le jeu de tuiles donne une infinité de pavages sans période.

Voici par exemple deux colorisations du jeu de tuiles de Culik (ces tuiles sont données ici sans égard à la façon dont elles ont été engendrées) :




Démontrer que le pavage de Robinson ou celui d’Amman sont périodiques est un exercice intéressant mais disons-le assez assommant : il faut étudier finement les motifs qui apparaissent nécessairement dans un pavage, les classer..., pour finalement exclure toute possibilité de périodicité.

On va ici se concentrer sur le pavage de Culik (il est plus juste de le qualifier de pavage de Kari et Culik car il doit beaucoup à Kari). Commençons par le présenter, implémenté en HTML/Javascript, puis avec DGPad.
Dans le premier fichier DGPad, le script est « prédigéré », ce qui permet un chargement rapide. Dans le second, on a le vrai script du pavage et le chargement est nettement plus long.

Pavage de Culik (HTML) Pavage de Culik (DGPad) Pavage de Culik 2 (DGPad)
HTML - 7.2 ko
HTML - 97 ko
HTML - 7.4 ko

Comment est construit le pavage de Kari et Culik ? Idée de la preuve

La première idée, somme toute assez naturelle, consiste à interpréter un jeu de tuiles comme une machine de Mealy.
Qu’est-ce qu’une machine de Mealy ?
Il s’agit en quelque sorte d’une machine de Turing sans ruban : la machine possède différents états. Dans un état donné, la machine peut lire un symbole en entrée ; elle donne alors en sortie un symbole, et change d’état.

Dans l’exemple ci-dessus (tiré de Wikipédia), on a schématisé une machine de Mealy déterministe.

  • Cette machine a trois états : S0, S1, S2.
  • Si la machine est dans un état S0 et lit un 1, elle produit un 0 et passe dans l’état S1.
  • etc

Les états seront les côtés verticaux (gauche -> droite) des tuiles et les symboles lus et produits seront les côtés horizontaux (haut -> bas).
Dans le cas du pavage de Kari, la machine sera déterministe. Dans le cas du pavage de Culik, la machine sera non déterministe (mais appliquée de façon déterministe pour éviter les culs de sac).

Les symboles lus et produits seront des nombres. Pour garantir l’apériodicité de tout pavage, on va en quelque sorte créer une machine de Mealy qui peut soit multiplier par 3, soit multiplier par 1/2. Un produit de facteurs 3 et 1/2 ne donnant jamais 1, on ne pourra pas retrouver le nombre de départ, ce qui interdira toute périodicité.
Sur chaque ligne, on « codera » un nombre et sur la ligne du dessous on codera son produit par q (3 ou 1/2).

C’est ici que ça se complique. L’objectif est d’obtenir une version faible (mais suffisamment forte pour conclure à l’apériodicité) de la vue de l’esprit suivante : « la ligne du dessous est obtenue en multipliant la ligne du dessus par 3 (respectivement par 1/2). Chaque tuile de la ligne va donc multiplier par 3 (respectivement par 1/2). »

Seulement, il ne faut pas rêver : si une tuile multipliait effectivement par 3 ou 1/2, il y aurait clairement une infinité de côtés verticaux de la forme $\lambda. \dfrac{3^n}{2^p}$ et donc de tuiles…
L’idée suivante est donc d’amortir par les états.

Considérons une tuile :

On va imposer non pas c=qa (avec q=3 ou 1/2) mais qa+b = c+d (amortissement par les états).
Autrement dit : c = qa - (d-b)

d-b est le changement d’état.

Vérifions que ce dispositif s’intègre dans la vue de l’esprit :
Imaginons alors un pavage qui serait périodique avec un motif rectangulaire qui se répète.
Intéressons-nous à la somme $S_1$ des côtés supérieurs de la ligne du haut. Soit $S_2$ une ligne en dessous.
c = qa - (d-b) donc en sommant sur le motif on obtient $\Sigma (d-b)=0$ par périodicité, donc $S_2=q.S_1$.
Autrement dit, quand on parlait de ligne dans la vue de l’esprit, il s’agit en fait de la somme (hypothétique) des côtés supérieurs sur un motif rectangulaire périodique.
On obtiendra de même $S_3=q.S_2$, etc…
Et arrivé à la dernière ligne du motif on doit retrouver $S_1$ par périodicité.

Si $S_1 \neq 1$, on aboutira alors à une contradiction (car un produit de 3 et de 1/2 ne donne jamais 1).

Reste à construire les tuiles.
Il y a deux contraintes :

  • on veut qu’il n’y ait pas trop de tuiles ;
  • on veut pouvoir appliquer la machine de Mealy dans les quatre directions.

L’dée géniale de Kari consiste à convoquer les suites de Beatty, et même leur première différence (oui, il fallait y penser !…).

Pour un réel $r$, on note $\lfloor r \rfloor$ la partie entière de r.
Etant donné un nombre $\alpha$, sa suite bi-infinie de Beatty $B(\alpha)$ est la suite $B(\alpha)_i = \lfloor i \alpha \rfloor$.
Les suites de Beatty ont été introduites par Beatty en 1926.
Kari a utilisé les suites obtenues en calculant les premières différences des suites de Beatty.

Pour $i \in \mathbb{Z}$, on définit $E(\alpha)_i = B(\alpha)_i – B(\alpha)_{i-1}$

Cette suite bi-infinie sera appelée la representation équilibrée de $\alpha$. Cette représentation équilibrée est en fait une suite de deux entiers. En effet, si $k\leqslant \alpha \leqslant k+1$, alors $E(\alpha)$ est une suite de k et de k+1.

Par exemple :
$E(1,5)= ….121212 …$, $E(\frac{1}{3})= ... 001001 ….$, $E(\frac{8}{3})= … 233233 ….$.

Le nombre lu sera de la forme $E(\alpha)_i$
Le résultat sera $E(q.\alpha)_i$

Pour rétablir l’amortissement par les états (qa+b = c+d) la différence des états doit être égale à $qE(\alpha)_i-E(q.\alpha)_i$

Pour obtenir cette différence, on prend naturelllement comme état $qB(\alpha)_i – B(q.\alpha)_i$. Cet état fait l’amortissement voulu.

Pour q=3, $q\lfloor r \rfloor - \lfloor qr \rfloor $ est égal à -2, -1 ou 0 (3 états).

Pour q=$\frac{1}{2}$, $q\lfloor r \rfloor - \lfloor qr \rfloor $ est égal à 0 ou à $\frac{1}{2}$ (2 états).

On va faire en sorte que $\alpha$ (qui sera multiplié par 3 ou $\frac{1}{2}$) reste toujours compris entre 0 et 2. Ainsi le nombre lu sera forcément 0,1 ou 2.

Plus précisément, si $\alpha \in [\frac{1}{3},\frac{2}{3}]$, on lira un 0 ou un 1 et on multipliera $\alpha$ par 3.

Cela correspond à la machine de Mealy $M_3$ suivante :

Et de la même façon, si $\alpha \in [0,2]$, on lira un 0, un 1 ou un 2 et on pourra multiplier $\alpha$ par $\frac{1}{2}$.

Cela correspondrait à la machine de Mealy $M_{\frac{1}{2}}$ suivante :

Mais il y a clairement un problème : la tuile (0,0,0,0) (et son équivalent pour l’état 1/2), qui n’a rien d’apériodique...

Dans l’esprit, il faut continuer à multiplier par 3 et $\frac{1}{2}$ à l’infini. Et $\alpha$ ne doit jamais descendre en dessous de $\frac{1}{3}$.
Pour arriver à ce résultat, on va modifier la machine $M_{\frac{1}{2}}$ en $M'_{\frac{1}{2}}$ pour faire en sorte qu’elle ne puisse pas s’appliquer plus de deux fois de suite sur une ligne. On introduit donc un nouveau symbole d’entrée/sortie 0’. Et on introduit aussi un nouvel état 0’ pour faire en sorte que les états de $M_3$ et $M'_{\frac{1}{2}}$ soient disjoints. Ainsi, on peut considérer que la réunion de $M_3$ et $M'_{\frac{1}{2}}$ constitue une seule machine de Mealy.


Cette machine de Mealy permet de construire une infinité de pavages valides du plan.
Il suffit de partir d’une suite $E(\alpha)$ avec $\alpha \in [\frac{1}{3},2]$.
Si $\alpha \in [\frac{1}{3},\frac{2}{3}]$, on multiplie $\alpha$ par 3.
Sinon on multiplie $\alpha$ par $\frac{1}{2}$. Et dans ce dernier cas, si on est encore supérieur à $\frac{2}{3}$, alors on multiplie encore $\alpha$ par $\frac{1}{2}$. Et cette fois, on est dans $[\frac{1}{3},\frac{2}{3}]$.

Le jeu de tuiles est le suivant :

Ce jeu de tuiles est apériodique car on peut considérer que $S_1$ correspond à une ligne où l’on multiplie par 3, et on voit bien que dans ce cas (sauf cas trivial à écarter) $S_1>0$ .

Peut-on faire mieux (autrement dit moins) que 13 tuiles ?
Cette question longtemps ouverte a été refermée en juin 2015 par Emmanuel Jeandel et Michael Rao : on peut le faire en 11 tuiles sur 4 couleurs et ce record est absolu (on ne peut pas faire mieux). Voir l’article qui présente la démonstration (assistée par ordinateur).

L’usage pour les pavages de Wang est d’accepter de prendre une même couleur horizontalement et verticalement, alors que ces deux « couleurs » sont indépendantes. C’est ce que nous avons fait pour le pavage de Kari et Culik.
Mais on peut considérer que c’est un mauvais usage et qu’il est préférable d’utiliser des couleurs différentes (l’identité de couleur a du sens pour les carreaux de Truchet, alors qu’elle n’en a pas pour les carreaux de Wang). C’est ce que nous avons fait pour ce dernier exemple de pavage apériodique (11 tuiles sur 4x2 couleurs).

Pavage apériodique à 11 tuiles sur 8 (=4x2) couleurs de E. Jeandel et M. Rao.

III) Retour sur les pavages de Truchet multicolores

Maintenant que l’on sait qu’il existe des pavages de Wang apériodiques, on peut se demander si la tuile de Truchet multicolore, qui est plus grossière, a aussi ce potentiel.
Nous avons soumis cette question à Michael Rao, et celui-ci l’a très vite résolue.
On va restituer ici sa démonstration :

On peut considérer que le pavage comporte au moins une tuile coupée dans le sens « / » (sinon on peut raisonner de la même façon avec la tuile symétrique « \ »).

On considère alors le graphe orienté avec l’ensemble de sommets les couleurs, et l’ensemble d’arcs (x,y) s’ il y a une tuile coupée dans le sens « / » avec la couleur x à gauche, et y à droite.

  • S’il existe un cycle dans ce graphe orienté, on est dans une situation de ce type :

Et le pavage est clairement périodique.



  • S’il n’existe pas de cycle, alors comme il n’y a qu’un nombre fini de couleurs, il existe une tuile x/y qui n’a pas de successeur en « / ».

Au sud et à l’est de cette tuile, on a forcément des tuiles en « \ ».
Au sud, on a une tuile z\y
A l’est, on a une tuile y\w

Mais alors on a forcément une tuile en « / » au sud-est, ce qui est une contradiction.
Donc tous les pavages sont périodiques.

En résumé, les tuiles de Wang sont des généralisations des carreaux de Truchet qui permettent de façon avérée d’obtenir des pavages apériodiques.
Et ces tuiles ont le potentiel du calculable.
Kari et Culik ont montré qu’il suffisait de 13 tuiles pour construire un pavage apériodique. On sait depuis peu, grâce à Emmanuel Jeandel et Michael Rao, que 11 suffisent et que l’on ne pourra pas faire mieux.
Une autre question est de savoir ce qu’il en est des carreaux de Truchet eux-même (vus comme des carreaux de Wang). Peuvent-ils être la brique de pavages apériodiques ?...
La réponse est inédite [3], elle a été apportée *en exclusivité pour les lecteurs d’Images des Maths* par Michael Rao lui même : c’est non, ces pavages sont toujours périodiques.

Post-scriptum :

Les auteurs tiennent à remercier toutes les personnes qui ont contribué à la gestation de cet article.
Merci pour leur aide à Xavier Goaoc, Nils Berglund, Clément Caubel et Arthur Milchior.
Merci à Emmanuel Jeandel et Michael Rao pour leurs encouragements et leur participation.

Article édité par Romain Dujardin

Notes

[1En d’autres termes, on peut construire une machine de Turing (une machine élémentaire qui peut faire le même type de calcul qu’un ordinateur) avec des tuiles de ce type.

[2Un pavage est dit périodique s’il est invariant par une translation non nulle du plan, et si c’est le cas on peut alors démontrer que le jeu de tuiles permet aussi de construire un pavage avec une période verticale et une période horizontale non nulle : le pavage ainsi créé est formé d’un motif rectangulaire qui se répète.

[3tout au moins à notre connaissance

Partager cet article

Pour citer cet article :

Patrice Debrabant, Alain Busser — «Du carreau de Truchet au carreau de Wang : atteindre l’atome de l’apériodique et du calculable» — Images des Mathématiques, CNRS, 2018

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM