Jardín del Edén (autómata celular)

En un autómata celular, un Jardín del Edén es una configuración que no tiene predecesor.

Para los autómatas celulares unidimensionales, los huérfanos y los Jardines del Edén pueden encontrarse mediante un algoritmo eficiente, pero para dimensiones mayores se trata de un problema indecidible.

El teorema del Jardín del Edén de Moore y Myhill afirma que un autómata celular en la cuadrícula cuadrada, o en un mosaico de cualquier espacio euclidiano de dimensión superior, tiene un Jardín del Edén si y sólo si tiene gemelos, dos patrones finitos que tienen los mismos sucesores siempre que uno se sustituye por el otro.

Una configuración puede tener cero, uno o más predecesores, pero siempre tiene exactamente un sucesor.

[4]​ Un Jardín del Edén se define como una configuración con cero predecesores.

[7]​ No obstante, en muchos casos es posible utilizar el teorema del Jardín del Edén (más adelante) para deducir que existe una solución y, a continuación, utilizar un algoritmo de búsqueda para encontrarla.

[8]​ Jean Hardouin-Duparc (1972-73, 1974) fue pionero en un método computacional más eficiente para encontrar patrones huérfanos.

El primer Jardín del Edén explícito en la Vida, con sus células vivas encajando en un rectángulo de 9 × 33, fue identificado como candidato a ser un Jardín del Edén por Roger Banks en 1971, y luego verificado por una exhaustiva búsqueda de predecesores.

[11]​ Por definición, todo huérfano pertenece a un Jardín del Edén: extender un huérfano a una configuración de todo el autómata, eligiendo arbitrariamente un estado para cada celda restante, siempre producirá un Jardín del Edén.

[14]​ Este caso, la continuidad se define asignando una topología discreta al conjunto finito de estados del autómata y, a continuación, utilizando una topología de producto con un término en el producto por cada celda del autómata para construir un espacio topológico cuyos puntos son las configuraciones del autómata.

Si el conjunto de Jardines del Edén no es vacío, debe haber al menos un cilindro en esta unión, por lo que debe haber al menos un huérfano.

[12]​ En un autómata celular, dos patrones finitos son gemelos si uno puede sustituirse por el otro dondequiera que aparezca, sin cambiar las configuraciones futuras.

[3]​ El teorema del Jardín del Edén, debido a Edward F. Moore (1962) y John Myhill (1963), afirma que un autómata celular en un espacio euclidiano es localmente inyectivo si y sólo si es suryectivo.

Más fuertemente, todo autómata celular no localmente inyectivo tiene un patrón huérfano.

Un corolario inmediato es que un autómata celular inyectivo debe ser suryectivo.

En este autómata, cada estado tiene cuatro predecesores, por lo que no es inyectivo pero tampoco tiene Jardín del Edén.

Cualquier autómata celular no localmente inyectivo con un estado quiescente tiene Jardines del Edén que son a su vez configuraciones finitas, por ejemplo cualquier configuración finita que contenga un huérfano.

Se puede demostrar para grupos sóficos utilizando el teorema de Ax-Grothendieck, una relación análoga entre la inyectividad y la biyectividad en la geometría algebraica.