Automates cellulaires
Un automate cellulaire est un modèle mathématique discret : une grille de cellules, où chaque cellule a un état précis, par exemple vivante ou morte. Toutes les cellules changent d’état au même moment, selon un ensemble fixe de règles et les états de leurs voisines directes. Les règles de base sont souvent extrêmement simples, et pourtant des motifs complexes, organiques et imprévisibles en naissent.
Les quatre éléments de base
Tout automate cellulaire est construit à partir des quatre mêmes éléments. La grille est l’espace où vivent les cellules. Ce peut être une ligne à une dimension, un plan à deux dimensions comme un échiquier, ou même un espace à trois dimensions. Les états sont ce qu’une cellule peut être. Dans le cas le plus simple, une cellule est binaire : noire ou blanche, 1 ou 0. Le voisinage est l’ensemble des cellules qui influencent directement une cellule. Sur une grille carrée, c’est généralement le voisinage de Moore, les huit cellules qui l’entourent, ou le voisinage de von Neumann, seulement le nord, l’est, le sud et l’ouest. Les règles sont le cerveau de l’automate : la logique qui donne à chaque cellule son nouvel état. Par exemple : si je suis vivante mais que j’ai moins de deux voisines vivantes, je meurs de solitude. Chaque cellule applique les mêmes règles au même moment.
1. Le jeu de la vie de Conway
Règles : B3/S23. Une cellule vivante survit avec 2 ou 3 voisines vivantes. Une cellule morte naît avec exactement 3. Toutes les autres cellules sont mortes à la génération suivante. John Conway l’a conçu en 1970, et la rubrique de Martin Gardner dans Scientific American l’a rendu célèbre. Il produit des planeurs, des oscillateurs et des vaisseaux. Bill Gosper a trouvé le premier canon à planeurs la même année : une configuration qui tire un nouveau planeur toutes les 30 générations, à l’infini. Le jeu de la vie peut calculer, car les planeurs peuvent transporter des signaux et entrer en collision comme des portes logiques. Surtout, il montre un comportement complexe qui naît de règles simples.
2. Règle 30
Type : automate cellulaire élémentaire à une dimension. L’état suivant de chaque cellule dépend d’elle-même et de ses deux voisines, et chaque génération est dessinée comme une nouvelle ligne sous la précédente. Stephen Wolfram a présenté la règle 30 en 1983. Partez d’une seule cellule noire et elle fait pousser un triangle chaotique. Elle semble aléatoire malgré sa règle déterministe, si aléatoire que sa colonne centrale a servi de générateur de nombres pseudo-aléatoires. Le même genre de triangles apparaît dans le pigment du coquillage Conus textile.
3. Règle 110
Type : automate cellulaire élémentaire à une dimension, comme la règle 30, avec une autre table de huit réponses. Il est prouvé que la règle 110 est universelle au sens du calcul : Matthew Cook a montré qu’avec une première ligne adaptée, elle peut émuler n’importe quel calcul qu’un ordinateur universel peut effectuer. Elle porte des structures mobiles qui se déplacent sur un fond répétitif et interagissent quand elles se rencontrent. Ces collisions sont ce que la preuve utilise comme logique. Elle montre comment des règles très simples peuvent émuler un calcul arbitraire.
4. Brian's Brain
États : éteint, allumé (actif) et réfractaire. Règles : une cellule éteinte s’allume si exactement 2 voisines sont allumées. Une cellule allumée devient réfractaire. Une cellule réfractaire s’éteint. Brian Silverman l’a conçu. Comme une cellule doit se reposer une génération après s’être allumée, chaque impulsion continue de s’éloigner de l’endroit où elle est passée. Le résultat est une foule de motifs autopropulsés qui ressemble aux ondes dans les milieux excitables, comme le tissu nerveux ou le muscle cardiaque, et qui paraît souvent vivante et organique.
5. Wireworld
États : vide, tête d’électron, queue d’électron et conducteur. Règles : une tête devient une queue, une queue devient conducteur, et un conducteur devient une tête quand exactement 1 ou 2 de ses voisines sont des têtes. Les cellules vides restent vides. Brian Silverman a aussi conçu Wireworld, en 1987. Les cellules conductrices sont des fils, et une tête suivie d’une queue est un électron qui les parcourt. Wireworld peut simuler des circuits électroniques : une boucle de fil avec un électron est une horloge, une petite encoche est une diode, et quelques cellules forment une porte logique. Des ordinateurs complets y ont été construits, comme l’ordinateur Wireworld de David Moore et Mark Owen, qui calcule des nombres premiers.
Les 256 règles et les quatre classes de Wolfram
Une cellule à une dimension avec deux voisines voit l’un de huit motifs, de 111 à 000. Une règle donne le nouvel état pour chacun d’eux, elle tient donc en huit bits, et il existe 2⁸ = 256 règles élémentaires. Lisez les huit réponses comme un nombre binaire et vous obtenez le nom de la règle : la règle 30 s’écrit 00011110, et la règle 110 s’écrit 01101110. Stephen Wolfram a classé les règles selon ce qu’elles font, de l’ordre au chaos. 1. La classe 1 aboutit à un état uniforme. 2. La classe 2 aboutit à des structures stables ou répétitives. 3. La classe 3 reste chaotique et d’apparence aléatoire, comme la règle 30. 4. La classe 4 construit des structures qui se déplacent et interagissent à la frontière entre l’ordre et le chaos, comme la règle 110.
Classement par difficulté
Jeu de la vie ★☆☆☆☆ · Règle 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Règle 110 ★★★★★. Les deux premiers s’expliquent d’eux-mêmes quand on les regarde. La règle 110 cache ses structures mobiles dans un fond répétitif.
Les plus beaux visuellement
1. Brian's Brain · 2. Jeu de la vie de Conway · 3. Règle 30 · 4. Règle 110 · 5. Wireworld.
Les plus importants mathématiquement
1. Règle 110, pour l’universalité · 2. Jeu de la vie, pour l’universalité et l’émergence · 3. Règle 30, pour le chaos et le hasard · 4. Wireworld, pour la logique numérique · 5. Brian's Brain, pour les systèmes excitables.
Dans la nature, la physique et la cryptographie
Les automates cellulaires servent à simuler des systèmes complexes dans la nature, la physique et la cryptographie. L’idée remonte à Stanisław Ulam et John von Neumann dans les années 1940, qui ont utilisé une grille de cellules pour concevoir une machine capable de se copier elle-même. Dans le monde réel, on voit des automates cellulaires dans le pigment de certains coquillages, comme le Conus textile, dont les triangles ressemblent à la règle 30, et dans les écailles du lézard ocellé, qui passent du vert au noir selon une règle proche d’un automate cellulaire. Les physiciens s’en servent pour modéliser l’écoulement des gaz, les tas de sable et les feux de forêt. Le hasard apparent de la règle 30 en a fait une candidate pour les générateurs de nombres aléatoires et les chiffrements par flot.
Explorez-les dans PictorX
Ouvrez Automates cellulaires pour lancer les cinq. Regardez le canon à planeurs, une flotte de vaisseaux ou le R-pentomino, qui met 1 103 générations à se stabiliser. Saisissez n’importe quelle règle de type jeu de la vie comme B36/S23, ou n’importe quel numéro de règle élémentaire de 0 à 255. Dessinez et effacez des cellules, envoyez des électrons dans les circuits Wireworld, reliez les bords et passez en mode coloré. Enregistrez un PNG ou ouvrez le canevas dans l’éditeur PictorX.
Questions fréquemment posées
Qu’est-ce qu’un automate cellulaire ?
Une grille de cellules dans laquelle chaque cellule a un état. À chaque pas de temps, toutes les cellules se mettent à jour ensemble selon une règle fixe qui ne regarde qu’une cellule et ses voisines. Malgré la simplicité des règles, les motifs peuvent être complexes et imprévisibles.
Qui a inventé les automates cellulaires ?
Stanisław Ulam et John von Neumann, dans les années 1940 à Los Alamos. Le jeu de la vie de John Conway (1970) a popularisé l’idée, et Stephen Wolfram a étudié les 256 règles élémentaires dans les années 1980.
Quels automates cellulaires sont Turing-complets ?
Parmi les cinq présentés ici, la règle 110 et le jeu de la vie sont prouvés universels, et Wireworld peut contenir un ordinateur complet. Universel signifie qu’avec le bon motif de départ, ils peuvent effectuer n’importe quel calcul qu’un ordinateur universel peut faire.
Quelles sont les quatre classes de Wolfram ?
La classe 1 s’éteint dans un état uniforme, la classe 2 aboutit à des structures stables ou répétitives, la classe 3 reste chaotique comme la règle 30, et la classe 4 construit des structures mobiles qui interagissent, comme la règle 110.
Pourquoi la règle 30 semble-t-elle aléatoire ?
Chaque pas est fixé, mais chaque cellule mélange sa voisine de gauche avec les deux autres d’une manière qui propage vite les petites différences. Aucun motif simple n’a été trouvé dans sa colonne centrale, c’est pourquoi on s’en est servi pour produire des nombres aléatoires.
Outils associés
Automates cellulaires
Lancez le jeu de la vie de Conway, la règle 30, la règle 110, Brian's Brain et Wireworld dans votre navigateur. Dessinez des cellules, changez la règle et regardez des règles simples faire pousser des motifs complexes.
Fourmi de Langton
Lancez la fourmi de Langton dans votre navigateur. Observez la symétrie, le chaos et l’autoroute de 104 pas, puis essayez des règles multicolores, plusieurs fourmis, une grille hexagonale et des turmites.
La spirale d’Ulam
Comment la spirale de Stanisław Ulam, en 1963, dispose les entiers sur une grille carrée, pourquoi les nombres premiers se regroupent sur des diagonales quadratiques et où se trouvent les quarante nombres premiers d’Euler quand la spirale commence à 41.
Labo de réaction-diffusion
Peignez des graines chimiques et regardez la réaction-diffusion de Gray–Scott faire pousser taches, rayures, labyrinthes et coraux. Réglez feed, kill, diffusion et vitesse — puis enregistrez un PNG.
Les fractales
Découvrez comment l’ensemble de Mandelbrot, les ensembles de Julia, les fractales de Newton et les fractales Nova sont générés—et pourquoi le zoom ne manque jamais de détails.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer les automates cellulaires