Estoy empezando a estudiar los autómatas celulares y tengo problemas para entender los llamados estados del Jardín del Edén. ¿Cómo puede un algoritmo determinista terminar en un estado que no tiene imagen previa, esto me parece imposible?
No se garantiza que todos los estados sean posibles en los autómatas celulares, por lo que nunca puede terminar en un estado del Jardín del Edén.
El Teorema del Jardín del Edén establece que si un autómata tiene gemelos, es decir, si es posible reemplazar un estado por otro sin cambiar los estados futuros, entonces puede haber un estado del Jardín del Edén. Para tamaños de cuadrícula suficientemente grandes, el número de predecesores potenciales (que no contienen un patrón gemelo) es menor que el número de estados futuros.
Considere un autómata celular que convierte cualquier estado en estado en un solo paso Todos los estados excepto son inalcanzables y por lo tanto los llamados estados del Jardín del Edén. Sin embargo, este autómata celular es claramente determinista. No hay contradicción.
Pero los estados son locales ( es decir, el contenido de una sola celda). El Teorema del Jardín del Edén habla de patrones de estados ( es decir, el contenido de una colección de celdas adyacentes). Precisamente:
Todos los patrones son accesibles si y solo si no hay patrones gemelos (donde los patrones gemelos son pares de patrones que se pueden intercambiar en una configuración circundante dada sin cambiar la imagen).
Por ejemplo, en Game of Life, hay patrones gemelos (un rodeado de ocho s VS. un patrón de 3x3 de s) por lo que debe haber un Patrón del Jardín del Edén. Te dejo encontrar uno... :)