Règle 110
La règle 110 est un automate cellulaire élémentaire (1D) qui a la particularité d’être Turing-complet — il peut simuler tout calcul possible, avec des règles d’une simplicité absolue.
La règle
Voisinage de 3 cellules (gauche, centre, droite), 2 états (0/1) → 8 configurations :
| Voisinage | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Résultat | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Le nom “110” vient de la lecture binaire des résultats : 01101110 = 110 en décimal.
Ce qui émerge
À partir d’une configuration initiale simple (une seule cellule active), la règle 110 produit :
- Des structures stables (particules immobiles)
- Des structures périodiques (oscillateurs)
- Des gliders (structures mobiles qui se propagent)
- Des collisions entre gliders produisant de nouvelles structures
Ces collisions peuvent encoder des opérations logiques — d’où la Turing-complétude.
La preuve de Turing-complétude
Démontrée par Matthew Cook en 2004 (publiée après un blocage juridique de Wolfram).
Cook a montré qu’on peut encoder une machine de Tag dans la règle 110 — et les machines de Tag sont équivalentes aux machines de Turing.
La preuve est remarquable : elle utilise des gliders comme bits d’information et leurs collisions comme opérations de calcul.
Pourquoi c’est important
La règle 110 est le système le plus simple connu à être Turing-complet. Elle illustre le principe de complexité irréductible de Wolfram :
Il n’existe pas de raccourci pour prédire son comportement futur — il faut simuler pas à pas.
C’est l’argument central de Wolfram dans A New Kind of Science : la nature elle-même pourrait fonctionner selon ce principe.
Concepts liés
Références
- Cook, M. (2004). Universality in elementary cellular automata. Complex Systems, 15(1), 1–40.
- Wolfram, S. (2002). A New Kind of Science. Wolfram Media. — chapitres 3 et 11.