Automates cellulaires
Les automates cellulaires sont des modèles de calcul discrets — une grille de cellules, chacune dans un état fini, qui évolue à chaque pas de temps selon des règles locales appliquées uniformément.
C’est l’exemple le plus épuré d’émergence : zéro communication, zéro mémoire, zéro intention — et pourtant des comportements globaux spectaculaires.
Structure de base
| Composant | Description |
|---|---|
| Grille | 1D, 2D ou nD |
| États | Finis (souvent 0/1) |
| Voisinage | Cellules adjacentes (Moore, Von Neumann…) |
| Règle de transition | État suivant = f(état actuel, voisins) |
La règle est locale, uniforme et synchrone — elle s’applique à toutes les cellules simultanément.
Les grandes familles
Automates 1D — Wolfram
Une ligne de cellules, voisinage de 3 cellules :
- 2³ = 8 configurations possibles
- 2⁸ = 256 règles au total
Wolfram les a classifiées en 4 classes :
| Classe | Comportement | Exemple |
|---|---|---|
| I | Stable — converge vers un état fixe | Règle 0 |
| II | Périodique — structures répétitives | Règle 4 |
| III | Chaotique — aléatoire apparent | Règle 30 |
| IV | Complexe — structures persistantes et interactions | Règle 110 |
La règle 110 est Turing-complète — elle peut simuler tout calcul possible.
Jeu de la Vie — Conway (1970)
Grille 2D, deux états (vivant / mort), 4 règles :
- Une cellule vivante avec 2 ou 3 voisins survit
- Une cellule vivante avec < 2 voisins meurt (isolement)
- Une cellule vivante avec > 3 voisins meurt (surpopulation)
- Une cellule morte avec exactement 3 voisins naît
Ce qui émerge : planeurs, oscillateurs, canons, structures stables — et computation universelle.
Automates probabilistes
La règle de transition est stochastique. Utilisés pour modéliser :
- Propagation d’épidémies
- Feux de forêt
- Croissance de cristaux
Ce qui les rend fascinants
Complexité irréductible (Wolfram) : on ne peut pas prédire l’état futur sans simuler pas à pas. Il n’existe pas de raccourci analytique.
Équivalence calculatoire : des règles d’une simplicité extrême atteignent la puissance d’un ordinateur universel.
Laboratoire d’émergence : les règles sont locales et explicites — on peut observer exactement comment la complexité globale surgit des interactions locales.
Lien avec les SMA réactifs
Les automates cellulaires sont le cas limite des SMA réactifs :
- Agents = cellules
- Règles locales = règle de transition
- Pas de mobilité, pas de mémoire individuelle
C’est le modèle le plus dépouillé pour étudier l’émergence pure.
Concepts liés
Références
- Wolfram, S. (2002). A New Kind of Science. Wolfram Media.
- Conway, J. H. (1970). The game of life. Scientific American, 223(4), 4–10.
- Cook, M. (2004). Universality in elementary cellular automata. Complex Systems, 15(1), 1–40.