# 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. Puede ser la configuración inicial del autómata, pero no puede surgir de ninguna otra forma. John Tukey bautizó estas configuraciones con el nombre del Jardín del Edén de las religiones abrahámicas, creado de la nada.
Un Jardín del Edén está determinado por el estado de cada celda del autómata (normalmente una rejilla cuadrada infinita de celdas de una o dos dimensiones). Sin embargo, para cualquier Jardín del Edén existe un patrón finito (un subconjunto de celdas y sus estados, denominado huérfano) con la misma propiedad de no tener predecesor, independientemente de cómo se rellenen las celdas restantes. Una configuración del autómata completo es un Jardín del Edén si y sólo si contiene un huérfano. 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. No obstante, las búsquedas informáticas han logrado encontrar estos patrones en el Juego de la Vida de Conway.
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.

## Definiciones

Un autómata celular se define por una malla de celda, un conjunto finito de estados que pueden asignarse a cada celda y una regla de actualización. A menudo, la rejilla de celdas es la red cuadrada infinita de una o dos dimensiones. La regla de actualización determina el siguiente estado de cada celda en función de su estado actual y de los estados actuales de otras celdas cercanas (la vecindad de la celda). La vecindad puede ser un conjunto finito arbitrario de celdas, pero cada dos celdas deben tener vecinas en las mismas posiciones relativas y todas las celdas deben utilizar la misma regla de actualización. Una configuración del autómata es una asignación de un estado a cada célula.
El sucesor de una configuración es otra configuración, formada aplicando la regla de actualización simultáneamente a cada celda. La función de transición del autómata es la función que mapea cada configuración a su sucesor. Si el sucesor de la configuración X es la configuración Y, entonces X es un predecesor de Y. Una configuración puede tener cero, uno o más predecesores, pero siempre tiene exactamente un sucesor. Un Jardín del Edén se define como una configuración con cero predecesores.
Un patrón, para un autómata celular dado, consiste en un conjunto finito de celdas junto con un estado para cada una de esas celdas. Una configuración contiene un patrón cuando los estados de las celdas del patrón son los mismos que los estados de las mismas celdas de la configuración (sin traducir las celdas antes de emparejarlas). La definición de predecesores de configuraciones puede extenderse a los predecesores de patrones: un predecesor de un patrón no es más que una configuración cuyo sucesor contiene el patrón. Un huérfano, por tanto, es un patrón sin predecesor.

## En busca del Jardín del Edén

Para los autómatas celulares unidimensionales, los Jardines del Edén pueden encontrarse mediante un algoritmo eficiente cuyo tiempo de ejecución es polinómico en el tamaño de la tabla de reglas del autómata. Para dimensiones mayores, determinar si existe un Jardín del Edén es un problema indecidible, lo que significa que no existe ningún algoritmo que pueda garantizar que termine y produzca la respuesta correcta. 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.
Sería posible que un programa informático buscara patrones huérfanos examinando sistemáticamente todos los patrones finitos, ordenados por tamaño creciente, y comprobando todos los posibles predecesores de cada patrón para determinar si, de hecho, es huérfano. Sin embargo, el número de patrones que habría que generar para encontrar un Jardín del Edén de este modo es exponencial en el área del patrón. Este enorme número de patrones haría que este tipo de búsqueda por fuerza bruta resultara prohibitivamente caro, incluso para patrones de tamaño relativamente pequeño.
Jean Hardouin-Duparc (1972-73, 1974) fue pionero en un método computacional más eficiente para encontrar patrones huérfanos. Su método se basa en la teoría de los lenguajes formales y requiere un tiempo exponencial en función de la anchura del patrón y no de su área. La idea clave es que, para cualquier anchura fija, es posible construir un autómata finito no determinista que reconozca patrones de una anchura dada que tengan un predecesor. Los símbolos de entrada a esta máquina describen cada fila del patrón, y los estados de la máquina describen las filas cercanas de posibles predecesores para la parte del patrón que se ha introducido hasta el momento. Se puede construir a partir de esta máquina otra máquina de estados finitos que reconozca el conjunto complementario, es decir, los patrones que no tienen predecesores, convirtiendo la máquina de estados finitos no determinista en un autómata finito determinista mediante la construcción de conjuntos de potencias y, a continuación, complementando su conjunto de estados de aceptación. Una vez que se ha construido una máquina que reconoce el conjunto complementario, se puede comprobar si el lenguaje que reconoce está vacío, buscando un camino desde el estado inicial hasta un estado de aceptación. Este camino, si existe, da una descripción fila por fila de un patrón huérfano.
Martin Gardner atribuye a Alvy Ray Smith la observación de que el teorema del Jardín del Edén se aplica al Juego de la Vida de Conway, y demuestra la existencia de Jardines del Edén para esta regla. 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. Posteriormente, Hardouin-Duparc utilizó su enfoque de lenguaje formal para encontrar los Jardines del Edén más estrechos posibles en el Juego de la Vida de Conway, con la caja delimitadora para sus células vivas de sólo seis células de ancho.
El patrón huérfano más pequeño conocido del Juego de la Vida de Conway (por área de su caja delimitadora) fue hallado por Steven Eker en abril de 2016. Tiene 57 células vivas y cabe en un rectángulo de 8×12.

## Existencia de huérfanos

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. Pero lo contrario también es cierto: cada Jardín del Edén contiene al menos un huérfano. Para demostrarlo, Kari utiliza un argumento topológico basado en el teorema de Curtis-Hedlund-Lyndon, según el cual las funciones de transición de los autómatas celulares son exactamente las funciones continuas invariantes de traslación en el espacio de configuraciones. 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. Según el teorema de Tychonoff, se trata de un espacio compacto.
Para cada patrón finito, el conjunto de configuraciones que contienen el patrón es un conjunto abierto en esta topología, llamado cilindro. Los cilindros forman una base para la topología. Como observa Kari, la colección de configuraciones que no son Jardines del Edén no es más que la imagen de la función de transición, de modo que por el lema del mapa cerrado para espacios compactos es un conjunto cerrado. El conjunto de Jardines del Edén, en consecuencia, es un conjunto abierto. Como es abierto y los cilindros forman una base, el conjunto de Jardines del Edén puede representarse como una unión de cilindros. Cada uno de los cilindros de esta unión está formado sólo por Jardines del Edén, por lo que el patrón que determina cada cilindro debe ser huérfano. 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. Y cualquier Jardín del Edén particular debe pertenecer a uno de estos cilindros, y por lo tanto debe contener el huérfano para ese cilindro.

## Teorema del Jardín del Edén

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. Un autómata celular es inyectivo si cada par de configuraciones distintas del autómata siguen siendo diferentes después de un paso del autómata, y localmente inyectivo si no tiene gemelos. Es suryectivo si y sólo si cada configuración tiene un predecesor; es decir, si y sólo si no tiene ninguna configuración Jardín del Edén. Un autómata que es a la vez inyectivo y suryectivo se denomina autómata celular reversible.
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. En otras palabras, afirma que un autómata celular tiene un Jardín del Edén, si y sólo si tiene gemelos. 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. Moore demostró una dirección del teorema, que los autómatas con gemelos tienen huérfanos; Myhill demostró la inversa, que un autómata con un huérfano también tiene gemelos.
En el caso del Juego de la Vida de Conway, los gemelos son mucho más fáciles de encontrar que los huérfanos. Por ejemplo, un bloque de cinco por cinco de células muertas y un bloque de cinco por cinco con su célula central viva y las restantes muertas son gemelos: el estado de la célula central no puede afectar a las configuraciones posteriores del patrón. Así, en este caso, el teorema del Jardín del Edén permite demostrar la existencia de un Jardín del Edén mucho más fácilmente que encontrando un patrón huérfano explícito.

### Boceto de prueba

La idea principal de la demostración del teorema es utilizar un argumento de recuento, para mostrar que cualquier fallo de inyectividad local (patrones gemelos) conduce a un patrón huérfano, y viceversa. En concreto, supongamos que la red subyacente del autómata es una rejilla cuadrada bidimensional, que tiene s estados de celda diferentes, que los patrones gemelos P y Q encajan en un cuadrado n × n y que el radio de la vecindad de cualquier celda es como máximo n. Entonces, para determinar si un patrón que cabe en un cuadrado mn × mn es huérfano, basta con mirar las partes de los posibles predecesores que caben en un cuadrado (m + 2)n × (m + 2)n y que no contienen el patrón Q. Pero sólo hay ($^{sn}$ $^{×n}$ - 1)$^{(m+2)×(m+2)}$ de estos posibles predecesores. Para valores suficientemente grandes de m este número es menor que el número $^{smn}$ $^{×mn}$ de huérfanos potenciales. Por lo tanto, uno de los huérfanos potenciales no tiene predecesor y es realmente huérfano; es decir, la no inyectividad implica la no subjetividad. A la inversa (siendo n el tamaño de la caja delimitadora de un huérfano), un argumento de recuento muy similar muestra que el número de modelos que caben en un cuadrado (m + 2)n × (m + 2)n y no contienen un huérfano es demasiado pequeño para proporcionar un sucesor distinto a cada modelo inicial dentro de un cuadrado mn × mn, de lo que se deduce que algunos dos de los posibles modelos iniciales son gemelos. Por lo tanto, la no subjetividad implica la no inyectividad local.

### Inyectividad frente a inyectividad local

La distinción entre inyectividad e inyectividad local en el teorema es necesaria, ya que existen autómatas celulares que son localmente inyectivos pero no inyectivos. Un ejemplo es la Regla 90, el autómata binario unidimensional cuya regla de actualización sustituye el estado de cada celda por el o exclusivo de sus dos vecinas. En este autómata, cada estado tiene cuatro predecesores, por lo que no es inyectivo pero tampoco tiene Jardín del Edén.

### Con estados de inactividad

En autómatas como el Juego de la Vida de Conway, existe un estado especial «quiescente» en el que una célula quiescente cuya vecindad es totalmente quiescente permanece quiescente. En este caso, se puede definir una «configuración finita» como una configuración con sólo un número finito de células no quiescentes. 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. También es posible que un autómata tenga una configuración finita cuyos únicos predecesores no sean finitos (por ejemplo, en la regla 90, una configuración con una única célula viva tiene esta propiedad). Sin embargo, el teorema del Jardín del Edén no caracteriza la existencia de tales modelos.

### En geometrías no euclidianas

En los autómatas celulares definidos sobre teselaciones del plano hiperbólico, o de espacios hiperbólicos de dimensiones superiores, el argumento de recuento de la prueba del teorema del Jardín del Edén no funciona, porque depende implícitamente de la propiedad de los espacios euclidianos de que el límite de una región crece menos rápidamente que su volumen en función del radio. Existen autómatas celulares hiperbólicos que tienen gemelos pero que no tienen un Jardín del Edén, y otros autómatas celulares hiperbólicos que tienen un Jardín del Edén pero que no tienen gemelos; estos autómatas pueden definirse, por ejemplo, de una manera invariante de la rotación en los teselados hiperbólicos uniformes en los que tres heptágonos se encuentran en cada vértice, o en los que cuatro pentágonos se encuentran en cada vértice.
Sin embargo, el teorema del Jardín del Edén puede generalizarse más allá de los espacios euclidianos, a los autómatas celulares definidos sobre los elementos de un grupo susceptible. Una forma más débil del teorema del Jardín del Edén afirma que todo autómata celular inyectivo es suryectivo. 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. En términos más generales, los grupos para los que se cumple esta forma más débil se denominan grupos surjuntivos, No se conocen ejemplos de grupos que no sean surjuntivos.

## En la ficción

En la novela de Greg Egan Permutation City, el protagonista utiliza una configuración del Jardín del Edén para crear una situación en la que una copia de sí mismo pueda demostrar que vive dentro de una simulación. Anteriormente, todas sus copias simuladas se habían encontrado en alguna variante del «mundo real»; aunque tenían recuerdos de ser copias simuladas que vivían en una simulación, siempre había una explicación más sencilla de cómo surgieron esos recuerdos. Sin embargo, la configuración del Jardín del Edén sólo puede darse en una simulación diseñada de forma inteligente. Los paralelismos religiosos son intencionados.