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

El Jardín del Edén ( orphan , English  Garden of Eden, huérfano ) [2] [3]  es una configuración en el Juego de la Vida de Conway u otro autómata celular que no puede aparecer como resultado de la evolución porque no tiene predecesores. El término "Jardín del Edén" fue acuñado por John Tukey en la década de 1950, mucho antes de que apareciera Life.

Búsqueda de los Jardines del Edén

Se puede intentar realizar una búsqueda sistemática de los jardines del Edén en orden ascendente del número de celdas, clasificando para cada candidato a "huérfano" todas las posibles configuraciones previas. Sin embargo, este método no es práctico porque el número de configuraciones de "Vida" en un rectángulo de un área dada N es 2 N , y la enumeración exhaustiva se vuelve inaceptable incluso para áreas moderadas.

Un método de cálculo más eficiente se basa en la teoría de los lenguajes formales ; la complejidad temporal de este enfoque depende exponencialmente no del área, sino del ancho del cuadro delimitador [4] [5] .

El primer Jardín del Edén conocido en Life, ubicado en un rectángulo de 9 × 33, fue encontrado por Roger Banks en 1971 [1] . En 1973-74. los Jardines del Edén se construyeron en rectángulos de 6 × 122 y 6 × 117 [6] [7] [8] . En diciembre de 2011, se encontró el jardín del Edén, que consta de 56 celdas vivas y encaja en un cuadrado de 10 × 10; también se encontró que no hay Jardines del Edén en rectángulos menores de 6 × 6 [9] .

Teorema del Jardín del Edén

Dos configuraciones finitas de un autómata celular se denominan gemelos si sus evoluciones , a partir de la siguiente generación, coinciden completamente. Un autómata celular se llama inyectivo si no hay gemelos en este autómata. Se dice que un autómata celular es sobreyectivo si y solo si cada configuración tiene un padre, es decir, si no hay Jardines del Edén. Un autómata que es a la vez inyectivo y sobreyectivo se llama autómata celular reversible .  

El teorema del Jardín del Edén establece que un autómata celular en un universo euclidiano  es localmente inyectivo si y solo si es sobreyectivo. En otras palabras, el teorema establece que los Jardines del Edén existen solo en aquellos autómatas en los que existen gemelos.

El teorema se aplica a la "Vida" porque es fácil encontrar dos configuraciones diferentes que evolucionan en la próxima generación hacia la misma configuración. Un "universo muerto" y una célula viva solitaria en un "universo muerto" evolucionan hacia la misma configuración, todas sus células están muertas. Por lo tanto, en "Vida" hay jardines del Edén [6] [7] [8] .

El teorema del Jardín del Edén fue propuesto por Edward Moore y probado por Moore y John Myhill [10] [11] [8] .

Cuestiones relacionadas

Todavía se desconoce si existe una configuración que tenga un "padre" pero no un "abuelo" [12] [13] [14] .

Aunque cualquier configuración de Vida tiene un solo hijo, lo contrario no es cierto. Una configuración dada puede tener dos o más "padres". Por eso es tan difícil encontrar los jardines del Edén: la computadora debe explorar todos los padres posibles en cada paso "hacia el pasado". <...> Por cierto, el hecho de que un "hijo" del Jardín del Edén pueda tener más de un "padre" llevó a Conway a ofrecer un premio de $50 a la primera persona que pueda encontrar una configuración que tenga un "padre" pero sin "abuelo". La existencia de tal configuración es todavía una pregunta abierta.Martín Gardner [13]

Notas

1. ↑ 1 2 en Lifeline vol. 3 Archivado el 19 de marzo de 2012 en Wayback Machine (septiembre de 1971) se hizo un anuncio de que Roger Banks y Steve Ward habían probado la existencia de un Jardín del Edén rectangular de 9x33 y presentaron un espécimen que Banks creía que era el Jardín del Edén . En línea de vida vol. 4 Archivado el 19 de marzo de 2012 en Wayback Machine (diciembre de 1971). El editor Robert Wainwright informó que un grupo de Honeywell analizó de forma independiente la muestra de Banks y confirmó el resultado. Ver también Gardner, Martin, Wheels, Life, and Other Mathematical Amusements , p. 248 , < http://maa.org/pubs/focus/Gardner_GameofLife10-1970.pdf > . Consultado el 11 de agosto de 2013. Archivado el 17 de junio de 2011 en Wayback Machine .  
2. ↑ Huérfano . Diccionario de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 10 de octubre de 2012. (indefinido)
3. ↑ Huérfano . léxico de la vida. Archivado desde el original el 15 de octubre de 2014. (indefinido)
4. ↑ Hardouin-Duparc, J. (1972/73), À la recherche du paradis perdu, Publ. Matemáticas. Universidad Burdeos Année T. 4: 51–89 
5. ↑ Hardouin-Duparc, J. (1974), Paradis terrestre dans l'automate cellulaire de Conway, Rev. Francaise Automat. informat. Recherche Operationnelle Ser. Rojo T. 8 (R-3): 64–71 
6. ↑ 1 2 Jardín del Edén . Diccionario de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 10 de octubre de 2012. (indefinido)
7. ↑ 12 Jardín del Edén . léxico de la vida. Archivado desde el original el 18 de abril de 2009. (indefinido)
8. ↑ 1 2 3 Jardín del Edén . conwaylife.com. Consultado el 11 de agosto de 2013. Archivado desde el original el 1 de agosto de 2013. (indefinido)
9. ↑ Jardines del Edén (enlace descendente) . El Jardín del Edén más pequeño (14 de enero de 2012). Consultado el 20 de enero de 2022. Archivado desde el original el 24 de noviembre de 2012. (indefinido) 
10. ↑ Moore, EF (1962), Modelos de máquinas de autorreproducción, Proc. Síntoma Matemáticas aplicadas volumen 14:17–33 
11. ↑ Myhill, J. (1963), Lo contrario del teorema del Jardín del Edén de Moore , Actas de la American Mathematical Society Vol. 14: 685–686 , DOI 10.2307/2034301  . Reimpreso en Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, p. 204–205 
12. ↑ Eric Weistein. Jardín del Edén (enlace no disponible) . Tesoro escondido de El juego de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 6 de enero de 2009. (indefinido) 
13. ↑ 12 Martín Gardner . 22. El Juego de la Vida, Parte III // Ruedas, vida y otras diversiones matemáticas  (inglés) . — WH Freeman and Company, 1983.
14. ↑ Volumen 6 de Lifeline . conwaylife.com. Fecha de acceso: 16 de octubre de 2015. Archivado desde el original el 10 de diciembre de 2015. (indefinido)

Literatura

• 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 , vol. 252, Apuntes electrónicos en informática teórica, p. 93–102 , DOI 10.1016/j.entcs.2009.09.016 
• Moore, E. F. (1962), Modelos de máquinas de autorreproducción, Proc. Síntoma Matemáticas aplicadas T. 14:17–33  . Reimpreso en Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, p. 187–203