Hispanopedia Wiki
Articulo de referencia

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

Un Jardín del Edén en El juego de la vida de Conway , descubierto por R. Banks en 1971. [ 1 ] Las células fuera de la imagen están todas muertas (blancas). Un huérfano en la vid...

Hispanopedia WikiContenido en espanolLectura gratuita
Este es un buen artículo. Haz clic aquí para obtener más información.

Un Jardín del Edén en El juego de la vida de Conway , descubierto por R. Banks en 1971. [ 1 ] Las células fuera de la imagen están todas muertas (blancas).
Un huérfano en la vida encontrado por Achim Flammenkamp. Los cuadrados negros representan células vivas; las cruces azules representan células muertas.

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 denominó a estas configuraciones en honor al 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 celda del autómata (generalmente una red cuadrada infinita de celdas unidimensional o bidimensional). Sin embargo, para cualquier Jardín del Edén existe al menos un patrón finito (un subconjunto de celdas y sus estados, llamado huérfano ) con la misma propiedad de no tener predecesor, independientemente de cómo se completen 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 autómatas celulares unidimensionales, los huérfanos y los Jardines del Edén pueden encontrarse mediante un algoritmo eficiente, pero para dimensiones superiores este es un problema indecidible . No obstante, las búsquedas computacionales 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 recubrimiento 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 los mismos sucesores cuando uno se sustituye 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 una red cuadrada infinita unidimensional o bidimensional . 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 ciertas celdas cercanas (el vecindario de la celda). El vecindario puede ser un conjunto finito arbitrario de celdas, pero cada par de celdas debe tener vecinos en las mismas posiciones relativas y todas las celdas deben usar la misma regla de actualización. Una configuración del autómata es la 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 celdas junto con un estado para cada una de ellas. [ 6 ] 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 en la configuración (sin trasladar las celdas antes de compararlas). 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 patrón huérfano, entonces, es un patrón sin predecesor. [ 6 ]

En busca del Jardín del Edén

Para autómatas celulares unidimensionales, los Jardines del Edén pueden hallarse mediante un algoritmo eficiente cuyo tiempo de ejecución es polinomial respecto al 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 ningún algoritmo que garantice la finalización y la obtención de la respuesta correcta. [ 7 ] Sin embargo, en muchos casos es posible utilizar el teorema del Jardín del Edén (véase más adelante) para inferir la existencia de una solución y, a continuación, emplear 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 un patrón 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 resultara prohibitivamente costosa, incluso para patrones de tamaño relativamente pequeño. [ 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 un tiempo exponencial con respecto al ancho del patrón, en lugar de 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 introducido hasta el momento. A partir de esta máquina, se puede construir otra máquina de estados finitos que reconoce 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 del conjunto potencia y, posteriormente, complementando su conjunto de estados de aceptación. 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 el Juego de la Vida, con sus células vivas encajando en un rectángulo de 9 × 33 , fue identificado como candidato a Jardín del Edén por Roger Banks en 1971, y luego verificado mediante una búsqueda exhaustiva 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 de solo seis células 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 ]

Existencia de huérfanos

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 arbitrariamente un estado para cada celda restante, siempre producirá un Jardín del Edén. Pero lo contrario también es cierto: todo Jardín del Edén contiene al menos un huérfano. [ 12 ] [ 13 ] Para demostrar 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 por 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 celda del autómata para construir un espacio topológico cuyos puntos son las configuraciones del autómata. Por el teorema de Tychonoff, es un espacio compacto . [ 12 ]

Para cada patrón finito, el conjunto de configuraciones que lo contienen 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 simplemente la imagen de la función de transición, por lo que, según 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. 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 únicamente 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 particular debe pertenecer a uno de estos cilindros y, por lo tanto, debe contener el huérfano para ese cilindro. [ 12 ]

El teorema del Jardín del Edén

En un autómata celular, dos patrones finitos son gemelos si uno puede sustituirse por el otro en cualquier lugar donde aparezca, sin alterar las configuraciones futuras. Un autómata celular es inyectivo si cada par de configuraciones distintas del autómata permanece diferente después de un paso del mismo, 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 a la vez inyectivo y 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. De manera más contundente, 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 sobreyectivo. Moore demostró una dirección del teorema, que los autómatas con gemelos tienen huérfanos; [ 2 ] Myhill demostró el recíproco, 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 celdas muertas y un bloque de cinco por cinco con su celda central viva y las demás muertas son gemelos: el estado de la celda 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 ]

Boceto de prueba

La idea principal de la demostración del teorema es usar un argumento de conteo para mostrar que cualquier fallo de inyectividad local (patrones gemelos) conduce a un patrón huérfano, y viceversa. En más detalle, supongamos para mayor 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 caben en un cuadrado n × n , y que el radio del vecindario de cualquier celda es como máximo n . Entonces, para determinar si un patrón que cabe dentro de un cuadrado mn × mn es huérfano, solo se necesita mirar las partes de los predecesores potenciales que caben 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 huérfanos potenciales no tiene predecesor y es realmente un huérfano; es decir, la no inyectividad implica la no sobreyectividad. Recíprocamente (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 inicial dentro de un cuadrado mn × mn , superpuesto sobre algún fondo arbitrario pero inmutable. De esto se deduce que dos patrones ( m + 2) n × ( m + 2) n enmarcados por un fondo son gemelos, por lo que la no sobreyectividad implica la no inyectividad local. [ 15 ]

Inyectividad versus inyectividad local

Diagrama espacio-temporal de la Regla 90 , que carece de Jardín del Edén a pesar de no ser inyectiva. Cada fila representa una configuración, con el tiempo avanzando hacia abajo.

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 la disyunción exclusiva de sus dos vecinas. En este autómata, cada configuración tiene dos predecesoras, por lo que no es inyectivo, pero tampoco tiene un Jardín del Edén. [ 17 ]

Con estados de reposo

En autómatas como el Juego de la Vida de Conway , existe un estado especial de "quiescencia" tal que una celda quiescente cuyo vecindario es completamente quiescente permanece quiescente. En este caso, se puede definir una "configuración finita" como una configuración con solo un número finito de celdas 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 una celda huérfana. 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 viva 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 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 no poseen un Jardín del Edén, y otros autómatas celulares hiperbólicos que sí poseen un Jardín del Edén pero no tienen gemelos; estos autómatas pueden definirse, por ejemplo, de forma invariante a la rotación sobre los recubrimientos hiperbólicos uniformes en los que tres heptágonos convergen en cada vértice, o en los que cuatro pentágonos convergen 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 amenable . [ 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 forma 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 sobrejuntivos. [ 23 ]

En la ficción

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 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 viviendo en una simulación, siempre existía una explicación más simple para el origen de esos recuerdos. Sin embargo, la configuración del Jardín del Edén solo puede darse en una simulación diseñada inteligentemente. Los paralelismos religiosos son intencionados. [ 24 ]

Notas

  1. 1 2 En Lifeline Vol. 3 (septiembre de 1971), el editor Robert T. Wainwright anunció que Roger Banks y Steve Ward habían demostrado la existencia de un Jardín del Edén cuyas células vivas cabían en un rectángulo de 9 × 33 , y presentó una configuración que Banks creía que era un Jardín del Edén. En Lifeline Vol. 4 (diciembre de 1971), Wainwright informó que un grupo en Honeywell , utilizando un 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) .
  2. 1 2 Moore (1962) .
  3. 1 2 3 Kari (2012) , Sección 2.1, "Definiciones básicas", págs. 5–6.
  4. 1 2 Toffoli y Margolus (1990) . Sin embargo, cabe señalar que Toffoli y Margolus se refieren a la función de transición como el mapa global.
  5. ↑ Kari (2012) , pág. 10.
  6. 1 2 3 Kari (2012) , pág. 11.
  7. ↑ Kari (1990) ; Kari (1994) . El resultado principal de Kari es que es indecidible comprobar si un autómata celular es reversible, pero también demuestra la indecidibilidad de comprobar si existe un Jardín del Edén.
  8. ↑ Toffoli y Margolus (1990) : "Incluso si uno estuviera dispuesto a recurrir a una búsqueda por fuerza bruta, un tiempo de búsqueda prolongado generaría solo unos pocos elementos, e incluso estos serían en su mayor parte bastante poco interesantes."
  9. ↑ Hardouin-Duparc (1972-1973) .
  10. ↑ Hardouin-Duparc (1974) .
  11. ↑ Flammenkamp (2016) .
  12. 1 2 3 4 Kari (2012) , Proposición 2, pág. 11.
  13. ↑ El caso unidimensional de este resultado es el Teorema 5.1 de Hedlund (1969) . Al igual que en la demostración más sencilla que se presenta aquí, utiliza la compacidad del espacio de configuración. En su trabajo anterior, Moore y Myhill no distinguieron entre huérfanos y Jardines del Edén, y demostraron sus resultados únicamente en términos de huérfanos.
  14. ↑ Hedlund (1969) , Teorema 3.4.
  15. 1 2 Myhill (1963) .
  16. ↑ Gardner (1983) .
  17. ↑ Sutner (1991) .
  18. ^ Amoroso y Cooper (1970) ; Skyum (1975) .
  19. ↑ Margenstern (2009) . Margenstern se atribuye el resultado conjuntamente a él y a Jarkko Kari .
  20. ↑ Ceccherini-Silberstein, Machì y Scarabotti (1999) ; Capobianco, Guillón y Kari (2013) ; Bartholdi2019 .
  21. ↑ Gromov (1999) .
  22. ↑ Gottschalk (1973) .
  23. ↑ Ceccherini-Silberstein y Coornaert (2010) .
  24. ↑ Blackford, Ikin y McMullen (1999) ; Hayles (2005) .

Referencias

  • Amoroso, S.; Cooper, G. (1970), "El teorema del Jardín del Edén para configuraciones finitas", Actas de la Sociedad Matemática Americana , 26 (1): 158– 164, doi : 10.1090/S0002-9939-1970-0276007-5
  • Bartholdi, Laurent (2019), "La amenabilidad de los grupos se caracteriza por el teorema de Myhill", Journal of the European Mathematical Society , 21 (10), con un apéndice de Dawid Kielak: 3191–3197 , arXiv : 1605.09133 , doi : 10.4171/JEMS/900 , MR 3994103 
  • 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, vol.  80, Greenwood Publishing Group, pp. 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 e Informática Teórica , 15 (3): 41– 60, MR 3141826 
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), "Grupos sobrejuntivos", Autómatas celulares y grupos , Monografías de Springer en Matemáticas, 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), "Jardín del Edén / Huérfano" , Página del Juego de la Vida de Achim
  • Gardner, Martin (1983), "Capítulos 20 y 21: El juego de la vida, partes I y II" (PDF) , Wheels, Life, and Other Mathematical Amusements , WH Freeman, págs. 214–258 , archivado del original (PDF) el 26 de octubre de 2020 , consultado el 11 de marzo de 2019. ; véanse en particular las páginas  230 y 248 .
  • Gottschalk, Walter (1973), "Algunas nociones dinámicas generales", Avances recientes en dinámica topológica (Actas de la Conferencia sobre Dinámica Topológica, Universidad de Yale, New Haven, Connecticut, 1972; en honor a Gustav Arnold Hedlund) , Lecture Notes in Mathematics, vol.  318, Springer-Verlag , pp. 120–125 , doi : 10.1007/BFb0061728 , ISBN  978-3-540-06187-8, MR 0407821 
  • Gromov, M. (1999), "Endomorfismos de variedades algebraicas simbólicas", Journal of the European Mathematical Society , 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. Burdeos Année , 4 : 51– 89
  • Hardouin-Duparc, J. (1974), "Paradis terrestre dans l'automate cellulaire de Conway", Rev. Française Automat. Información. Búsqueda operativa Ser. Rojo , 8 (R-3): 64– 71
  • Hartman, Christian; Heule, Marijn JH ; Kwekkeboom, Kees; Noels, Alain (2013), "Simetría en los jardines del Edén", Electronic Journal of Combinatorics , 20 (3): P16, doi : 10.37236/2611 , MR 3104514 
  • Hayles, N. Katherine (2005), «Cosmología subjetiva y el régimen de la computación: la intermediación en la ficción de Greg Egan», My mother was a computer: digital subjects and literary texts , University of Chicago Press, pp. 214–240 , ISBN  978-0-226-32147-9
  • Hedlund, GA (1969), "Endomorfismos y automorfismos de los sistemas dinámicos de desplazamiento", Mathematical Systems Theory , 3 (4): 320– 375, doi : 10.1007/BF01691062 , S2CID 21803927 
  • Kari, Jarkko (1990), "La reversibilidad de los autómatas celulares 2D es indecidible", Physica D , 45 ( 1–3 ): 379–385 , Bibcode : 1990PhyD...45..379K , doi : 10.1016/0167-2789(90)90195-U
  • Kari, Jarkko (1994), "Problemas de reversibilidad y sobreyectividad de 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, pp. 3–24 , doi : 10.1007/978-3-540-92910-9_1 , ISBN  978-3-540-92909-3
  • Margenstern, Maurice (2009), "Acerca de los teoremas del Jardín del Edén para autómatas celulares en el plano hiperbólico", XV Taller Internacional sobre Autómatas Celulares y Sistemas Complejos Discretos , Electronic Notes in Theoretical Computer Science, vol.  252, pp. 93–102 , doi : 10.1016/j.entcs.2009.09.016 
  • Moore, EF (1962), "Modelos de máquinas de autorreproducción", Problemas matemáticos en las ciencias biológicas , Actas de simposios en matemáticas aplicadas, vol.  14, pp. 17–33 , doi : 10.1090/psapm/014/9961 , ISBN  9780821813140{{citation}}: CS1 maint: se ignoraron los errores de ISBN ( enlace ) ; reimpreso en Burks, Arthur W. ( 1970), Essays on Cellular Automata , University of Illinois Press, pp. 187–203 .
  • Myhill, J. (1963), "El recíproco del teorema del Jardín del Edén de Moore", Actas de la Sociedad Matemática Americana , 14 (4): 685– 686, doi : 10.1090/S0002-9939-1963-0155764-9 , JSTOR 2034301 ; reimpreso en Burks, Arthur W. ( 1970), Essays on Cellular Automata , University of Illinois Press, pp. 204–205 .
  • Skyum, Sven (1975), "Confusión en el Jardín del Edén", Actas de la Sociedad Matemática Americana , 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 , Bibcode : 1990PhyD...45..229T , doi : 10.1016/0167-2789(90)90185-R , MR 1094877