$ \newcommand{\llbracket}{[\![} \newcommand{\rrbracket}{]\!]} \renewcommand{\epsilon}{\varepsilon} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ACA}{\mathcal{A}} \newcommand{\ACC}{\mathcal{C}} \newcommand{\ACV}{\mathcal{V}} \newcommand{\ACQ}{\mathcal{Q}} $

Origine lointaine

Le problème de décision de Hilbert
Logique du premier ordre
Classes de formules définies syntaxiquement

Théorèmes (1935-1970)

Si la classe considérée est assez riche pour exprimer les mathématiques usuelles, alors il n'existe pas de programme qui décide si une formule de cette classe est ou non un théorème

Origine moderne

Travaux inités par Hao Wang dans les années 1960
Classe $\forall \exists \forall$
Equivalence (poussée) entre problèmes de logiques et problèmes géométrique

Problème (Domino Problem)

Entrée : un ensemble fini de tuiles.

Question : peut-on paver le plan avec elles ?

Différents modèles...

Tuiles de Wang

Une tuile est un carré unité dont les bords ont une couleur
Un ensemble fini de tuiles

Définition

Un pavage du plan est le placement de copies des tuiles bord-à-bord de façon à ce que les couleurs en contact coincident.

On peut aussi paver des carrés, des tores, etc.

Réflexion préliminaire

Un ensemble de tuiles ne pave pas le plan
✎ semi-décidable
Un ensemble de tuiles pave le plan périodiquement
✎ semi-décidable
Si tous les ensembles de tuiles qui pavent le plan le pavent aussi périodiquement, alors on peut décider le problème du pavage du plan.

Wang pensait que c'était le cas

Berger (1964) : Le pavage du plan est indécidable
Corollaire : il exite des ensembles de tuiles aperiodiques

Définition

Un ensemble de tuiles est apériodique s'il peut paver le plan, mais jamais périodiquement

Sous-shifts

Tuiles de Wang faciles à définir mais pas pratiques à utiliser.

→ sous-shifts de type fini

Plan discret

Ensemble fini de décorations

Configuration : associe à chaque cellule une décoration

Ensemble fini de motifs interdits

Définition

Un pavage est une configuration ne contenant aucun motif interdit.

Informellement :

Un jeu de tuiles est un ensemble de règles qui peuvent être vérifiées localement
Il existe une taille $N$ telle que si toute fenêtre de taille $N \times N$ est correcte alors la configuration est un pavage

Équivalence

Proposition

Le Domino Problem avec des tuiles de Wang est équivalent à la formulation par motifs interdits

Preuve. On convertit une instance de l’un en instance équivalente de l’autre

Un sens facile (✎ lequel ?)
Soit un ensemble de motifs interdits
- motifs interdits de taille $\leq m × n$
- couleurs horizontales : motifs $(m − 1) × n$
- couleurs verticales : motifs $m × (n − 1)$ tuiles à partir de chaque motif $n × m$ autorisé

Avec contrainte

Théorème (Wang)

Étant donné un jeu de tuiles $\tau$ et une tuile $t ∈ \tau$, il est indécidable de savoir s’il existe un pavage contenant $t$

✎ Preuve

Par réduction au problème de l’arrêt
Soit une machine de Turing $M$
On construit un jeu de tuile qui simule l’évolution de $M$ mais ne contient pas l’état final

→ Il existe un pavage si et seulement si la machine ne termine pas sur l’entrée vide

Définition

Une configuration est périodique si elle est invariante par translation d’un vecteur non nul

Défintion

Une configuration est bi-périodique si elle est périodique selon deux vecteurs indépendants

Définition

Un jeu de tuiles est apériodique s’il admet un pavage mais qu’il n’admet pas de pavage périodique

Quelle périodicité ?

$$\overrightarrow{p_1} = \vector{x_1}{y_1} \qquad\overrightarrow{p_2} = \vector{x_2}{y_2}$$

$$x_2\overrightarrow{p_1} - x_1\overrightarrow{p_2} = \vector{0}{x_2y_1 − x_1y_2}$$

$$y_2\overrightarrow{p_1} - y_1\overrightarrow{p_2} = \vector{y_2x_1 - y_1x_2}{0}$$

Proposition

Si un ensemble de tuiles admet un pavage périodique, alors il en admet un bi-périodique

Remarque

Un pavage bi-périodique a une période verticale et une horizontale

→ Un ensemble de tuiles est aperiodique s’il pave le plan mais n’admet aucun pavage horizontalement et verticalement périodique

Quasi-périodicité

Définition

Un motif $m$ est récurrent dans une configuration $\ACC$ s’il existe un entier $n$ tel que $m$ apparaît dans toute fenêtre de taille $n \times n$ dans $\ACC$

Définition

Une configuration $\ACC$ est quasi-périodique si tous les motifs qu’elle contient sont récurrents

Théorème

Si un jeu de tuiles pave le plan, il admet un pavage quasi-périodique

✎ Preuve (double compacité !)

On enlève un par un les motifs non récurrents
Point d’accumulation ne contient que des motifs récurrents

Exemple pour s'insipirer

Robinson 1970

Idées :

Une configuration qui contient des carrés de taille arbitraire disjoints ne peut pas être périodique
Assurons-nous qu’au centre de tout carré, il y a un coin

Idée générale

Idées :

On dessine des carrés
On les connecte
On les organise en groupes $3 \times 3$ pour former un plus grand carré
On continue récursivement pour les tailles plus grandes

Rectangles et infini

On veut des rectangles (ou carrés) de taille non bornée
La compacité oblige de tolérer certains passage à l’infini

Pas grave

Carrons les rectangles

On ajoute des diagonales
Elles contournent les carrés internes

→ les rectangles deviennent carrés

Les bras

Les carrés émettent des bras
Les bras connectent des carrés
Les bras connectent les mêmes côtés
Les bras peuvent croiser au plus un carré
Les bras peuvent se croiser

Alignement

Proposition

Des carrés connectés par des bras ont la même taille

Preuve par l’absurde en considérant le plus petit mal aligné

Rmq : Comme des bras infinis ne peuvent pas apparaître dans une configuration bi-périodique, on peut supposer que tout carré a un voisin dans chaque direction