Jardin d'Éden (automate cellulaire)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Jardin d'Éden.

Dans un automate cellulaire, un motif fini est nommé jardin d'Éden s'il ne possède aucun prédécesseur. C’est-à-dire qu'il n'existe aucune configuration qui permette d'atteindre un jardin d'Éden après une ou plusieurs générations; en conséquence, un tel motif doit être créé à la main.

Le terme fait bien sûr référence au lieu originel biblique et fut donné par John Tukey dans les années 1950, bien avant que John Conway n'invente le jeu de la vie.

Exemples[modifier | modifier le code]

Pour le jeu de la vie :

  • Garden of Eden 1.png
    Le premier jardin d'Éden trouvé pour cet automate cellulaire en 1971, par Roger Banks, Mike Beeler et Rich Schroeppel. Il est inclus dans un rectangle de 33 cellules sur 9 et comprend 226 cellules vivantes.
  • Garden of Eden 4.png
    Jardin d'Eden découvert par Achim Flammenkamp le 23 juin 2004, qui était le plus petit connu au moment de sa découverte. Inclus dans un rectangle 12 x 11; les 72 cellules noires doivent être vivantes, les 41 «X» bleus sont des cellules qui doivent être mortes. (113 cellules sont ainsi contraintes.)

Il a été prouvé que toutes les structures du jeu de la vie contenues dans un rectangle de 6 cellules sur 5 ont au moins un prédécesseur et qu'aucune d'entre elles n'est donc un jardin d'Éden.

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]