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 otra forma.John Tukey nombró estas configuraciones en honor al Jardín del Edén en las religiones abrahámicas , que fue creado de la nada. [2]
Un jardín del Edén está determinado por el estado de cada celda en el autómata (generalmente una red de celdas cuadradas infinitas unidimensionales o bidimensionales ). Sin embargo, para cualquier Jardín del Edén existe un patrón finito (un subconjunto de celdas y sus estados, llamado huérfano ) con la misma propiedad de no tener predecesor, sin importar cómo se llenen las celdas 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 los 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 cuadrada, o en un mosaico de cualquier espacio euclidiano de dimensión superior , tiene un Jardín del Edén si y solo si tiene gemelos , dos patrones finitos que tienen la misma sucesores siempre que uno sea sustituido por el otro.
Un autómata celular se define mediante 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 el retículo cuadrado infinito 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 algunas 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 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 aplicando 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 configuración de X es de 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 sin 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 celdas en el patrón son los mismos que los estados de las mismas celdas en la configuración (sin traducir las celdas antes de emparejarlas). La definición de predecesores de configuraciones puede extenderse 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]
