Jardin d'Éden (automate cellulaire)

Dans un automate cellulaire, un jardin d'Éden est un motif fini qui 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 référence au lieu originel biblique et fut donné par John Tukey dans les années 1950[réf. nécessaire], bien avant que John Conway n'invente le jeu de la vie.

Pour les articles homonymes, voir Jardin d'Éden.

Exemples

Pour le jeu de la vie :

  • Le premier jardin d'Éden trouvé pour cet automate cellulaire en 1971, par Roger Banks, Mike Beeler et Rich Schroeppel[réf. nécessaire]. Il est inclus dans un rectangle de 33 cellules sur 9 et comprend 226 cellules vivantes.
  • Jardin d'Eden découvert par Achim Flammenkamp le [réf. nécessaire], qui était le plus petit connu au moment de sa découverte. Inclus dans un rectangle 12 × 11, les 72 cellules noires doivent être vivantes et 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

Liens internes

Liens externes

  • Portail de l’informatique
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.