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]
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/6/6f/Garden_of_Eden_pattern.png/300px-Garden_of_Eden_pattern.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/9/9e/Garden_of_Eden_4.png)
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 células y sus estados, llamado huérfano ) con la misma propiedad de no tener predecesor, sin importar cómo se llenen 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 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 el mismo sucesores siempre que uno sea sustituido por el otro.
Definiciones
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]
Buscando el huerto del Edén
Para los autómatas celulares unidimensionales, Gardens of Eden se puede encontrar mediante un algoritmo eficiente cuyo tiempo de ejecución es polinomial en el tamaño de la tabla de reglas del autómata. Para dimensiones superiores, determinar si existe un Jardín del Edén es un problema indecidible , lo que significa que no existe un algoritmo que pueda garantizar que termine y produzca la respuesta correcta. [7] Sin embargo, en muchos casos es posible usar el teorema del Jardín del Edén (abajo) para inferir que existe una solución y luego usar un algoritmo de búsqueda para encontrar una.
Sería posible que un programa de computadora buscara patrones huérfanos examinando sistemáticamente todos los patrones finitos, en orden aumentando el tamaño, y probando todos los predecesores posibles de cada patrón para determinar si de hecho es huérfano. Sin embargo, la cantidad de patrones que se necesitarían 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 relativamente pequeños de patrones. [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 los lenguajes formales y requiere una cantidad de tiempo exponencial en el ancho del patrón más que en su área. La idea clave es que, para cualquier ancho fijo, es posible construir un autómata finito no determinista que reconozca patrones de un ancho dado que tengan un predecesor. Los símbolos de entrada de 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 utilizando la construcción del conjunto de potencias , y luego complementando su conjunto de estados de aceptación. . Una vez que se ha construido una máquina que reconoce el conjunto complementario, se puede probar si el lenguaje que reconoce está vacío, buscando una ruta desde el estado inicial hasta el 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 los Jardines del Edén para esta regla. El primer Jardín del Edén explícito en la vida, con sus células vivas encajadas en un rectángulo de 9 × 33 , fue identificado como un candidato para ser un Jardín del Edén por Roger Banks en 1971, y luego verificado por una búsqueda exhaustiva de predecesores. [1] Posteriormente, Hardouin-Duparc usó 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 celdas vivas de 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 área de su cuadro delimitador) fue encontrado por Steven Eker en abril de 2016. Tiene 57 células vivas y cabe en un rectángulo de 8 × 12. [11]
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 un estado para cada celda restante arbitrariamente, 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. [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 en la traducció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 usando una topología de producto con un término en el producto para cada celda en el autómata para construir un espacio topológico cuyos puntos son los configuraciones de autómatas. Según el teorema de Tychonoff, es un espacio compacto . [12]
Para cada patrón finito, el conjunto de configuraciones que contiene el patrón es un conjunto abierto en esta topología, llamado cilindro . [6] Los cilindros forman la base de 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 del mapa cerrado para espacios compactos es un conjunto cerrado . El conjunto de los Jardines del Edén, en consecuencia, es un conjunto abierto. Debido a que está abierto y los cilindros forman una base, el conjunto de los Jardines del Edén se puede representar como una unión de cilindros. Cada uno de los cilindros de esta unión consta únicamente de Gardens of Eden, por lo que el patrón que determina cada cilindro debe ser huérfano. Si el conjunto de Gardens of Eden 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 de ese cilindro. [12]
El teorema del jardín del Edén
En un autómata celular, dos patrones finitos son gemelos si uno puede ser sustituido por el otro dondequiera que aparezca, sin cambiar configuraciones futuras. Un autómata celular es inyectivo si cada par de configuraciones distintas del autómata permanecen diferentes después de un paso del autómata, y localmente inyectable si no tiene gemelos. Es sobreyectiva si y solo si cada configuración tiene un predecesor; es decir, si y solo si no tiene la configuración del Jardín del Edén. Un autómata que es tanto inyectivo como sobreyectivo se denomina 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 fuertemente, todo autómata celular no inyectable localmente 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 de Game of Life 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 celda central viva y las restantes células muertas son gemelas: el estado de la celda central no puede afectar 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. [dieciséis]
Boceto de prueba
La idea principal de la demostración del teorema es usar un argumento de conteo para mostrar que cualquier falla de la inyectividad local (patrones gemelos) conduce a un patrón huérfano, y viceversa. En más detalle, supongamos por concreción que la red subyacente del autómata es una rejilla cuadrada de dos dimensiones, que tiene s diferentes estados celulares, que los patrones individuales P y Q tanto ajuste en un n × n cuadrados, y que el radio de la vecindad de cualquier celda es como máximo n . Luego, para determinar si un patrón que encaja dentro de un cuadrado mn × mn es huérfano, solo es necesario observar las partes de los predecesores potenciales que encajan dentro de 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 posibles huérfanos no tiene antecesor y es realmente un huérfano; es decir, la no inyectividad implica la no sobrejetividad. Por el contrario ( 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 encajan 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 inicial dentro de un cuadrado mn × mn , de lo cual se deduce que dos de los posibles patrones iniciales son gemelos. Por tanto, la no sobrejetividad implica la no inyectividad local. [15]
Inyectividad versus inyectividad local
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/e/e4/Rule90rand-expanded.png/170px-Rule90rand-expanded.png)
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 celda con el exclusivo o 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]
Con estados inactivos
En autómatas como el Juego de la vida de Conway , hay un estado especial de "reposo" tal que una celda inactiva cuyo vecindario está completamente inactivo permanece inactivo. 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 inyectable localmente con un estado inactivo 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 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 sola celda activa tiene esta propiedad). Sin embargo, el teorema del Jardín del Edén no caracteriza la existencia de tales patrones. [18]
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 conteo en la demostración 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 un 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 forma invariante en 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 se puede generalizar más allá de los espacios euclidianos, a los autómatas celulares definidos en los elementos de un grupo susceptible . [20] Una forma más débil del teorema del Jardín del Edén afirma que todo autómata celular inyectivo es sobreyectivo. Se puede probar para grupos soficos usando el teorema de Ax-Grothendieck , una relación análoga entre inyectividad y bijetividad en geometría algebraica. [21] De manera más general, los grupos para los que se mantiene esta forma más débil se denominan grupos sobreyuntivos . [22] No se conocen ejemplos de grupos que no sean supuestos. [23]
En ficción
En la novela Permutation City de Greg Egan , el protagonista usa 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 está viviendo 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. La configuración del Jardín del Edén, sin embargo, no puede ocurrir excepto en una simulación diseñada inteligentemente. Los paralelos religiosos son intencionales. [24]
Notas
- ^ a b En Lifeline Vol. 3 (septiembre de 1971), el editor Robert T.Wainwright anunció que Roger Banks y Steve Ward habían probado la existencia de un Jardín del Edén cuyas células vivas encajaban en un rectángulo de 9 × 33 , y presentó una configuración que Banks creía que era un Jardín del Edén. Edén. En Lifeline Vol. El 4 (diciembre de 1971), Wainwright informó que un grupo en Honeywell que usaba software de Don Woods había verificado que la configuración de Banks era un Jardín del Edén. Véase también Gardner (1983) .
- ↑ a b Moore (1962) .
- ^ a b c Kari (2012) , Sección 2.1, "Definiciones básicas", págs. 5-6.
- ↑ a b Toffoli y Margolus (1990) . Sin embargo, tenga en cuenta que Toffoli y Margolus se refieren a la función de transición como el mapa global.
- ↑ Kari (2012) , p. 10.
- ↑ a b c Kari (2012) , pág. 11.
- ^ Kari (1990) ; Kari (1994) . El resultado principal de Kari es que es indecidible probar si un autómata celular es reversible, pero también muestra la indecidibilidad de probar si existe un Jardín del Edén.
- ^ Toffoli y Margolus (1990) : "Incluso si uno estuviera dispuesto a recurrir a una búsqueda de fuerza bruta, un tiempo de búsqueda prolongado generaría sólo unos pocos elementos, e incluso esos serían en su mayor parte poco interesantes".
- ^ Hardouin-Duparc (1972–73) .
- ^ Hardouin-Duparc (1974) .
- ^ Flammenkamp (2016) .
- ↑ a b c d Kari (2012) , Proposición 2, p. 11.
- ↑ El caso unidimensional de este resultado es el Teorema 5.1 de Hedlund (1969) . Como en la prueba más simple dada aquí, usa la compacidad del espacio de configuración. En su trabajo anterior, Moore y Myhill no distinguieron a los huérfanos de Gardens of Eden, y probaron sus resultados solo en términos de huérfanos.
- ^ Hedlund (1969) , Teorema 3.4.
- ↑ a b Myhill (1963) .
- ^ Gardner (1983) .
- ^ Sutner (1991) .
- ^ Amoroso y Cooper (1970) ; Skyum (1975) .
- ^ Margenstern (2009) . Margenstern atribuye el resultado conjuntamente a él y a Jarkko Kari .
- ^ Ceccherini-Silberstein, Machì y Scarabotti (1999) ; Capobianco, Guillon y Kari (2013) ; Bartholdi y Kielak (2016) .
- ^ Gromov (1999) .
- ^ Gottschalk (1973) .
- ^ Ceccherini-Silberstein y Coornaert (2010) .
- ^ Blackford, Ikin y McMullen (1999) ; Hayles (2005) .
Referencias
- Amoroso, S .; Cooper, G. (1970), "El teorema del jardín del Edén para configuraciones finitas", Proceedings of the American Mathematical Society , 26 (1): 158-164, doi : 10.1090 / S0002-9939-1970-0276007-5
- Bartholdi, Laurent; Kielak, Dawid (2016), La capacidad de los grupos se caracteriza por el teorema de Myhill , arXiv : 1605.09133
- Blackford, Russell; Ikin, Van; McMullen, Sean (1999), "Greg Egan", Constelaciones extrañas: una historia de la ciencia ficción australiana , Contribuciones al estudio de la ciencia ficción y la fantasía, 80 , Greenwood Publishing Group, págs. 190-200 , ISBN 978-0-313-25112-2
- Capobianco, Silvio; Guillon, Pierre; Kari, Jarkko (2013), "Autómatas celulares sobreyectivos lejos del jardín del Edén" , Matemáticas discretas y ciencias informáticas teóricas , 15 (3): 41-60, MR 3141826
- Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), "Grupos de supervivencia", Autómatas y grupos celulares , Springer Monographs in Mathematics, Springer-Verlag , pp. 57-75, doi : 10.1007 / 978-3-642-14034-1_3 , ISBN 978-3-642-14033-4, MR 2683112
- Ceccherini-Silberstein, TG; Machì, A .; Scarabotti, F. (1999), "Grupos susceptibles y autómatas celulares" , Annales de l'Institut Fourier , 49 (2): 673–685, doi : 10.5802 / aif.1686 , MR 1697376
- Flammenkamp, Achim (abril de 2016), "Garden of Eden / Orphan" , página de Achim's Game of Life
- Gardner, Martin (1983), "Capítulos 20 y 21: El juego de la vida, Partes I y II" (PDF) , Ruedas, vida y otras diversiones matemáticas , WH Freeman, págs. 214-258; véanse en particular las págs. 230 y 248
- Gottschalk, Walter (1973), "Algunas nociones dinámicas generales", Recent Advances in Topological Dynamics (Proc. Conf. Topological Dynamics, Yale Univ., New Haven, Connecticut, 1972; en honor a Gustav Arnold Hedlund) , Lecture Notes in Math., 318 , Springer-Verlag , págs. 120-125, doi : 10.1007 / BFb0061728 , MR 0407821
- Gromov, M. (1999), "Endomorfismos de variedades algebraicas simbólicas", Revista de la Sociedad Matemática Europea , 1 (2): 109-197, doi : 10.1007 / PL00011162 , MR 1694588 , Zbl 0998.14001
- Hardouin-Duparc, J. (1972–73), "À la recherche du paradis perdu", Publ. Matemáticas. Univ. Bordeaux Année , 4 : 51–89
- Hardouin-Duparc, J. (1974), "Paradis terrestre dans l'automate cellulaire de Conway", Rev. Française Automat. Informat. Recherche Operationnelle Ser. Rouge , 8 (R-3): 64–71
- Hartman, Christiaan; Heule, Marijn JH ; Kwekkeboom, Kees; Noels, Alain (2013), "Symmetry in Gardens of Eden", Revista electrónica de combinatoria , 20 (3): P16, doi : 10.37236 / 2611 , MR 3104514
- Hayles, N. Katherine (2005), "Cosmología subjetiva y el régimen de computación: intermediación en la ficción de Greg Egan", Mi madre era una computadora: sujetos digitales y textos literarios , University of Chicago Press, págs. 214-240, ISBN 978-0-226-32147-9
- Hedlund, GA (1969), "Endomorfismos y automorfismos de los sistemas dinámicos de desplazamiento", Teoría de sistemas matemáticos , 3 (4): 320–375, doi : 10.1007 / BF01691062
- Kari, Jarkko (1990), "La reversibilidad de los autómatas celulares 2D es indecidible", Physica D , 45 (1–3): 379–385, doi : 10.1016 / 0167-2789 (90) 90195-U
- Kari, Jarkko (1994), "Problemas de reversibilidad y sobrejetividad de los autómatas celulares", Journal of Computer and System Sciences , 48 (1): 149-182, doi : 10.1016 / S0022-0000 (05) 80025-X , MR 1259654
- Kari, Jarkko J. (2012), "Conceptos básicos de autómatas celulares", en Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (eds.), Handbook of Natural Computing , Springer, págs. 3–24, doi : 10.1007 / 978-3-540-92910-9_1
- Margenstern, Maurice (2009), "Acerca de los teoremas del jardín del Edén para autómatas celulares en el plano hiperbólico", 15º Taller internacional sobre autómatas celulares y sistemas complejos discretos , Electronic Notes in Theoretical Computer Science, 252 , pp. 93-102, doi : 10.1016 / j.entcs.2009.09.016
- Moore, EF (1962), "Modelos de máquina de autorreproducción", Proc. Symp. Matemáticas aplicadas , Actas de simposios en matemáticas aplicadas, 14 : 17–33, doi : 10.1090 / psapm / 014/9961 , ISBN 9780821813140; reimpreso en Burks, Arthur W. (1970), Ensayos sobre autómatas celulares , University of Illinois Press, págs. 187–203.
- Myhill, J. (1963), "El inverso del teorema del Jardín del Edén de Moore", Proceedings of the American Mathematical Society , 14 : 685–686, doi : 10.2307 / 2034301 , JSTOR 2034301; reimpreso en Burks, Arthur W. (1970), Ensayos sobre autómatas celulares , University of Illinois Press, págs. 204–205.
- Skyum, Sven (1975), "Confusion in the Garden of Eden", Proceedings of the American Mathematical Society , 50 (1): 332–336, doi : 10.1090 / S0002-9939-1975-0386350-1
- Sutner, Klaus (1991), "Gráficos de De Bruijn y autómatas celulares lineales" (PDF) , Complex Systems , 5 : 19–30, MR 1116419
- Toffoli, Tommaso ; Margolus, Norman (1990), "Autómatas celulares invertibles: una revisión", Physica D: Nonlinear Phenomena , 45 (1-3): 229-253, doi : 10.1016 / 0167-2789 (90) 90185-R , MR 1094877
enlaces externos
- Jardín del Edén , LifeWiki
- Jardín del Edén (El tesoro del juego de la vida de Eric Weisstein)