La Règle 110 de Wolfram

La Règle 110 de Wolfram est un remarquable automate cellulaire unidimensionnel de la classification des règles « élémentaires » de Stephen Wolfram. Chaque cellule de cette grille linéaire peut être dans l'un des deux états : 0 (éteint) ou 1 (allumé). À chaque étape, la rangée suivante de cellules est déterminée en examinant les triplets de la rangée actuelle — chaque cellule plus ses deux voisins. Le motif indiquant quels triplets produisent un 1 dans la génération suivante est encodé par le nombre binaire 110.

Malgré sa définition minimale — juste quelques bits décrivant quels arrangements locaux deviennent « allumés » — la Règle 110 démontre un comportement incroyablement riche et complexe. Il a été prouvé qu'elle est Turing-complète sous certaines conditions initiales, la plaçant au même niveau que les systèmes capables, en théorie, d'effectuer des calculs universels.

Comment ça marche →

La Règle

Dans la terminologie des automates cellulaires élémentaires, le numéro de règle décimal 110 correspond au motif binaire 01101110 lu du triplet « 111 » au « 000 ». Cela signifie que certains triplets (comme 110, 101, 011, 001) produisent une cellule vivante dans la génération suivante, tandis que d'autres produisent une cellule morte.

Malgré la convention de nommage simple, les comportements qui émergent peuvent être étonnamment complexes. Vous verrez des régions chaotiques, des motifs répétitifs et toutes sortes d'interactions pilotées par ces simples règles de triplets.

Émergence & Complexité

L'un des aspects les plus intrigants de la Règle 110 est la façon dont une seule rangée de bits peut évoluer vers des structures ressemblant à des particules en mouvement, des collisions ou des fronts d'onde. De minuscules changements dans la rangée initiale peuvent modifier radicalement la tapisserie qui se déploie, soulignant la sensibilité du système aux conditions initiales. Cette complexité émergente provient purement d'interactions locales — aucune coordination centrale n'est requise.

Dans certaines configurations, vous observerez des régions stables, des « Gliders » et des expansions répétitives ou chaotiques qui soulignent la profondeur du système. Les chercheurs ont étudié cet automate de manière approfondie pour comprendre comment des systèmes déterministes simples peuvent exhiber des motifs qui semblent aléatoires ou sont au moins calculatoirement irréductibles.

Complétude de Turing

La Règle 110 peut être configurée pour calculer tout ce qu'une machine de Turing universelle peut, la rendant Turing-complète. Cela signifie que si vous configurez la rangée initiale de la bonne manière, vous pouvez théoriquement émuler des opérations logiques, de la mémoire et tout élément de calcul fondamental au sein de ce petit automate. C'est une démonstration frappante que la complexité peut émerger même de l'ensemble de règles le plus simple — ce sont les interactions locales répétées au fil du temps qui produisent un comportement puissant.

Aperçu Algorithmique

Voici une approche simple pour calculer chaque nouvelle rangée. Nous pouvons optionnellement enrouler les bords pour que les cellules d'un côté puissent voir les voisins du côté opposé. Si cela est désactivé, les bords au-delà de la grille sont considérés comme « morts » :

// Rule 110 transition table - maps each 3-bit pattern to its next state
const transitions = {
  // pattern => next state
  '111': 0,
  '110': 1,
  '101': 1,
  '100': 0,
  '011': 1,
  '010': 1,
  '001': 1,
  '000': 0
};

Et voici comment nous l'appliquons lors de chaque mise à jour (bien que notre implémentation finale utilise l'approche par décalage de bits, ce tableau est une expression alternative des triplets qui produisent une cellule vivante) :

function computeNextRow(currentRow, wrapEdges) {
  const length = currentRow.length;
  const newRow = new Array(length).fill(0);

  for (let i = 0; i < length; i++) {
    const leftIndex  = wrapEdges ? (i - 1 + length) % length : i - 1;
    const rightIndex = wrapEdges ? (i + 1) % length : i + 1;

    const left   = (leftIndex < 0 || leftIndex >= length) ? 0 : currentRow[leftIndex];
    const center = currentRow[i];
    const right  = (rightIndex < 0 || rightIndex >= length) ? 0 : currentRow[rightIndex];

    const pattern = (left << 2) | (center << 1) | right;
    newRow[i] = (110 >> pattern) & 1;
  }
  return newRow;
}