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 manera. John Tukey nombró a estas configuraciones como el Jardín del Edén de las religiones abrahámicas , que fue creado de la nada. [2]
Un Jardín del Edén está determinado por el estado de cada célula del autómata (normalmente una red cuadrada infinita de células unidimensional o bidimensional). Sin embargo, para cualquier Jardín del Edén existe un patrón finito (un subconjunto de células y sus estados, llamado huérfano ) con la misma propiedad de no tener predecesor, sin importar cómo se rellenen las células restantes. Una configuración de todo el autómata es un Jardín del Edén si y solo si contiene un huérfano. Para autómatas celulares unidimensionales, los huérfanos y los Jardines del Edén se pueden encontrar mediante un algoritmo eficiente, pero para dimensiones superiores este es un problema indecidible . Sin embargo, las búsquedas por computadora 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, o en una teselación 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.
Un autómata celular se define por una cuadrícula de celdas, un conjunto finito de estados que se pueden asignar a cada celda y una regla de actualización. A menudo, la cuadrícula de celdas es una red cuadrada infinita unidimensional o bidimensional . La regla de actualización determina el siguiente estado de cada celda como una función de su estado actual y de los estados actuales de ciertas otras celdas cercanas (el vecindario de la celda). El vecindario 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 usar la misma regla de actualización. Una configuración del autómata es una asignación de un estado a cada celda. [3]
El sucesor de una configuración es otra configuración, formada al aplicar la regla de actualización simultáneamente a cada celda. [4] La función de transición del autómata es la función que asigna cada configuración a su sucesor. [3] 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. [4] Un Jardín del Edén se define como una configuración con cero predecesores. [5]
Un patrón , para un autómata celular dado, consiste en un conjunto finito de células junto con un estado para cada una de esas células. [6] Una configuración contiene un patrón cuando los estados de las células en el patrón son los mismos que los estados de las mismas células en la configuración (sin traducir las células antes de hacerlas coincidir). La definición de predecesores de configuraciones se puede extender a predecesores de patrones: un predecesor de un patrón es simplemente una configuración cuyo sucesor contiene el patrón. Un huérfano, entonces, es un patrón sin predecesor. [6]
En el caso de autómatas celulares unidimensionales, los Jardines del Edén se pueden encontrar mediante un algoritmo eficiente cuyo tiempo de ejecución es polinomial en el tamaño de la tabla de reglas del autómata. En el caso de dimensiones superiores, 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. [7] Sin embargo, en muchos casos es posible utilizar el teorema del Jardín del Edén (a continuación) para inferir que existe una solución y luego 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, en orden creciente de tamaño, y probando todos los posibles predecesores de cada patrón para determinar si de hecho es huérfano. Sin embargo, la cantidad de patrones que se necesitaría generar para encontrar un Jardín del Edén de esta manera es exponencial en el área del patrón. Esta enorme cantidad de patrones haría que este tipo de búsqueda por fuerza bruta fuera prohibitivamente costosa, incluso para tamaños de patrones relativamente pequeños. [8]
Jean Hardouin-Duparc (1972–73, 1974) fue pionero en un enfoque computacional más eficiente para encontrar patrones huérfanos. Su método se basa en la teoría de lenguajes formales y requiere una cantidad de tiempo que es exponencial en el ancho del patrón en lugar de en su área. La idea clave es que, para cualquier ancho fijo, es posible construir un autómata finito no determinista que reconoce patrones de un ancho dado que tienen 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 ingresado hasta ahora. Se puede construir a partir de esta máquina otra máquina de estados finitos que reconozca el conjunto complementario , los patrones que no tienen predecesores, convirtiendo la máquina de estados finitos no determinista en un autómata finito determinista mediante el uso de la construcción de conjuntos potencia y luego complementando su conjunto de estados aceptantes. Una vez construida una máquina que reconoce el conjunto complementario, se puede comprobar si el lenguaje que reconoce está vacío, buscando una ruta desde el estado inicial hasta un estado de aceptación. Esta ruta, si existe, proporciona una descripción fila por fila de un patrón huérfano. [9]
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. [1] 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 el cuadro delimitador para sus células vivas con solo seis celdas de ancho. [10]
El patrón huérfano más pequeño conocido en el Juego de la Vida de Conway (por el área de su cuadro delimitador) fue descubierto por Steven Eker en abril de 2016. Tiene 57 células vivas y cabe en un rectángulo de 8×12. [11]
Por definición, cada huérfano pertenece a un Jardín del Edén: extender un huérfano a una configuración de todo el autómata, eligiendo un estado para cada célula restante arbitrariamente, siempre producirá un Jardín del Edén. Pero lo inverso también es cierto: cada Jardín del Edén contiene al menos un huérfano. [12] [13] Para probar esto, Kari [12] 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. [14] Aquí, la continuidad se define asignando una topología discreta al conjunto finito de estados del autómata, y luego utilizando una topología de producto con un término en el producto para cada célula en el autómata para construir un espacio topológico cuyos puntos son las configuraciones del autómata. Por el teorema de Tichonoff es un espacio compacto . [12]
Para cada patrón finito, el conjunto de configuraciones que contienen el patrón es un conjunto abierto en esta topología, llamado cilindro . [6] Los cilindros forman una base para la topología. Como observa Kari, la colección de configuraciones que no son Jardines del Edén es solo la imagen de la función de transición, por lo que, por el lema de la función cerrada para espacios compactos, es un conjunto cerrado . El conjunto de Jardines del Edén, correspondientemente, es un conjunto abierto. Debido a que 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 en esta unión consta solo de 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 está 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 en particular debe pertenecer a uno de estos cilindros y, por lo tanto, debe contener el huérfano para ese cilindro. [12]
En un autómata celular, dos patrones finitos son gemelos si uno puede sustituir al otro dondequiera que aparezca, sin cambiar las configuraciones futuras. Un autómata celular es inyectivo si cada par de configuraciones distintas del autómata sigue siendo diferente después de un paso del autómata, y localmente inyectivo si no tiene gemelos. Es sobreyectivo si y solo si cada configuración tiene un predecesor; es decir, si y solo si no tiene una configuración del Jardín del Edén. Un autómata que es tanto inyectivo como sobreyectivo se llama autómata celular reversible . [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 solo si es sobreyectivo. En otras palabras, afirma que un autómata celular tiene un Jardín del Edén, si y solo si tiene gemelos. Más firmemente, cada autómata celular no localmente inyectivo tiene un patrón huérfano. Un corolario inmediato es que un autómata celular inyectivo debe ser sobreyectivo. Moore demostró una dirección del teorema, que los autómatas con gemelos tienen huérfanos; [2] Myhill demostró lo contrario, que un autómata con un huérfano también tiene gemelos. [15]
En el caso del Juego de la Vida de Conway, es mucho más fácil encontrar gemelos que 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 células restantes muertas son gemelos: el estado de la célula central no puede afectar las configuraciones posteriores del patrón. Por lo tanto, 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. [16]
La idea principal de la prueba del teorema es usar un argumento de conteo , para mostrar que cualquier falla de inyectividad local (patrones gemelos) lleva a un patrón huérfano, y viceversa. Con más detalle, supongamos para concreción que la red subyacente del autómata es una cuadrícula 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 . Luego, para determinar si un patrón que encaja en un cuadrado mn × mn es huérfano, solo hay que mirar las partes de los predecesores potenciales que encajan en un cuadrado ( m + 2) n × ( m + 2) n y que no contienen el patrón Q. Pero solo hay ( s n × n − 1) ( m + 2) × ( m + 2) de estos predecesores potenciales. Para valores suficientemente grandes de m, este número es menor que el número s mn × mn de huérfanos potenciales. Por lo tanto, uno de los huérfanos potenciales no tiene predecesor y es realmente un huérfano; es decir, la no inyectividad implica no sobreyectividad. A la inversa (siendo n el tamaño de un cuadro delimitador de un huérfano) un argumento de conteo muy similar muestra que el número de patrones que caben dentro de 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 patrón de inicio dentro de un cuadrado mn × mn , de lo que se sigue que algunos dos de los posibles patrones de inicio son gemelos. Por lo tanto, la no sobreyectividad implica no inyectividad local. [15]
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 reemplaza el estado de cada célula con el o exclusivo de sus dos vecinos. En este autómata, cada estado tiene cuatro predecesores, por lo que no es inyectivo pero tampoco tiene Jardín del Edén. [17]
En autómatas como el Juego de la Vida de Conway , existe un estado "quiescente" especial, de modo que una célula quiescente cuyo vecindario es completamente 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 inyectivo localmente con un estado quiescente tiene Jardines del Edén que son en sí mismos configuraciones finitas, por ejemplo, cualquier configuración finita que contenga un huérfano. También puede ser 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 sola célula viva tiene esta propiedad). Sin embargo, el teorema del Jardín del Edén no caracteriza la existencia de tales patrones. [18]
En los autómatas celulares definidos sobre teselaciones del plano hiperbólico , o de espacios hiperbólicos de dimensiones superiores, el argumento de conteo en 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 no tienen gemelos; estos autómatas pueden definirse, por ejemplo, de una manera invariante a la rotación en las teselaciones hiperbólicas uniformes en las que tres heptágonos se encuentran en cada vértice, o en las que cuatro pentágonos se encuentran en cada vértice. [19]
Sin embargo, el teorema del Jardín del Edén puede generalizarse más allá de los espacios euclidianos, a autómatas celulares definidos sobre los elementos de un grupo ameno . [20] Una forma más débil del teorema del Jardín del Edén afirma que todo autómata celular inyectivo es sobreyectivo. Puede demostrarse para grupos sóficos utilizando el teorema de Ax-Grothendieck , una relación análoga entre inyectividad y biyectividad en geometría algebraica. [21] De manera más general, los grupos para los que se cumple esta forma más débil se denominan grupos sobrejuntivos . [22] No se conocen ejemplos de grupos que no sean sobreyectivos. [23]
En la novela Permutation City de Greg Egan , 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 puede 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 simple de cómo surgieron esos recuerdos. Sin embargo, la configuración del Jardín del Edén no puede ocurrir excepto en una simulación diseñada inteligentemente. Los paralelos religiosos son intencionales. [24]