\( \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}} \)

Indécidabilité sur les
automates cellulaires

Cours M2 - MIT
Victor Poupet

Surjectivité

Surjectivité

Théorème (Amoroso & Patt, 1972)
La surjectivité des automates cellulaires en dimension 1 est décidable

Théorème (Kari, 1989)
La surjectivité des automates cellulaires en dimension 2 et au-delà est indécidable
Preuve par réduction du problème de pavabilité finie

Pavabilité finie

Réduction du problème de l’arrêt

✎ Pavage fini ssi machine de Turing termine

Pavabilité finie

Entrée : jeu de tuiles \(\tau\) contenant une tuile blanche

Question : existe-t-il un pavage valide non trivial utilisant un nombre fini de tuiles non blanches ?


Théorème
Le problème de pavabilité finie est indécidable.

Chemins

Jeu de tuiles \(\tau_C\) dont les pavages finis

Surjectivité

Soit \(\tau\) un jeu de tuiles contenant une tuile blanche, on construit un AC \(\ACA\)

✎ Proposition
\(\ACA\) est injectif sur les configurations finies ssi \(\tau\) n’admet pas de pavage fini non trivial

Injectivité

Injectivité

Théorème (Amoroso & Patt, 1972)
L’injectivité des automates cellulaires en dimension 1 est décidable

Théorème (Kari, 1989)
L’injectivité des automates cellulaires en dimension 2 et au-delà est indécidable

Preuve par réduction du problème de pavabilité

Space-filling

Définition (space-filling)
Un jeu de tuiles est space-filling si
  • il admet un pavage du plan
  • chaque tuile pointe vers une de ses voisines
  • tout chemin sur un pavage valide parcourt intégralement des carrés arbitrairement grands
Théorème (Kari)
Il existe un pavage space-filling

La courbe de Peano

Courbe auto-similaire obtenue comme limite d’une substitution

→ à la limite, fonction continue surjective de \([0, 1] \rightarrow [0, 1]^2\)

Un pavage space-filling

On enrichit le pavage apériodique précédent


→ Un chemin passant par une tuile parcourt tous les carrés dont cette tuile dépend

Injectivité

Soit \(\tau\) un jeu de tuiles. On définit un AC \(\ACA\)


✎ Proposition
\(\ACA\) est injectif ssi \(\tau\) ne pave pas le plan

Nilpotence

Ensemble limite

Définition (ensemble limite)

Soit \(\ACA = (d, \ACQ, \ACV, \delta)\) un automate cellulaire. On définit

$$Λ^{(0)}(\ACA) = \ACQ^{\ZZ^d}$$

$$Λ^{(k+1)}(\ACA) = \ACA(Λ^{(k)}(A))$$

$$Λ(A) = \bigcap_{i\in\NN} Λ^{(i)}(A)$$

\(Λ(A)\) est appelé ensemble limite de \(\ACA\)

Ensemble limite = configurations qui admettent des antécédents de tout ordre


Définition (nilpotence)
Un AC est nilpotent si son ensemble limite ne contient qu’une seule configuration

Exemples

✎ Caractérisez les ensembles limites des AC suivants


✎ Construisez des AC 1D sur \(\{0, 1\}\) ayant les ensembles limites suivants

Propriétés

✎ Proposition
L’ensemble limite d’un AC n’est jamais vide
✎ Proposition
L’ensemble limite est exactement l’ensemble des configurations ne contenant que des motifs persistants (ayant des antécédents de tout ordre)
✎ Proposition
Si un motif est persistant, il apparaît dans une configuration limite
✎ Proposition
Toute configuration limite a un antécédent limite
✎ Proposition
Si un AC \(\ACA\) est nilpotent il existe \(k\) tel que \(Λ(\ACA) = Λ^{(k)}(\ACA)\)

Indécidabilité 2D

Théorème (Culik, Pachl & Yu, 1989)
La nilpotence des AC en dimension 2 et plus est indécidable

✎ Preuve par réduction du problème de pavage


→ Si un motif sans \(◈\) a des antécédents de tout ordre, on peut paver des carrés arbitrairement grands

Indécidabilité 1D

Théorème (Kari, 1992)
La nilpotence des AC en dimension 1 est indécidable

Preuve par réduction du problème de pavage avec des jeux de tuiles déterministes

Déterminisme

Définition
Un jeu de tuiles de Wang est SE-déterministe s’il n’existe pas deux tuiles dont les couleurs coïncident en haut et à gauche

(définition analogue pour NW, NE et SW)


Pavages par un jeu de tuiles déterministe correspondent à un diagramme espace-temps d’AC 1D


Théorème (Kari)
Le domino problem est indécidable sur les jeux de tuiles déterministes

Indécidabilité 1D

Théorème (Kari, 1992)
La nilpotence des AC en dimension 1 est indécidable

Preuve par réduction du problème de pavage avec des jeux de tuiles déterministes