Un autómata celular (CA) es realista (en el sentido de ser similar al Juego de la vida de Conway ) si cumple con los siguientes criterios:
- La matriz de células del autómata tiene dos dimensiones.
- Cada celda del autómata tiene dos estados (convencionalmente denominados "vivo" y "muerto", o alternativamente "encendido" y "apagado")
- El vecindario de cada celda es el vecindario de Moore ; consta de las ocho celdas adyacentes a la que se está considerando y (posiblemente) la celda en sí.
- En cada paso de tiempo del autómata, el nuevo estado de una celda puede expresarse en función del número de celdas adyacentes que están en el estado vivo y del propio estado de la celda; es decir, la regla es totalista externa (a veces llamada semitotalista ).
Esta clase de autómatas celulares lleva el nombre del Juego de la vida (B3 / S23), el autómata celular más famoso, que cumple con todos estos criterios. Se utilizan muchos términos diferentes para describir esta clase. Es común referirse a ella como la "familia de la vida" o simplemente usar frases como "similar a la vida".
Notación para reglas
Hay tres notaciones estándar para describir estas reglas, que son similares entre sí pero incompatibles. Wolfram y Packard (1985) utilizan el código Wolfram , un número decimal cuya representación binaria tiene bits que corresponden a cada número posible de vecinos y estado de una celda; los bits de este número son cero o uno en consecuencia, ya que una celda con ese vecindario está muerta o viva en la próxima generación. [1] Las otras dos notaciones descomponen la misma secuencia de bits en una cadena de caracteres que un humano puede leer más fácilmente.
En la notación utilizada por Cellebration de Mirek, una regla se escribe como una cadena x / y donde cada uno de xey es una secuencia de dígitos distintos del 0 al 8, en orden numérico. La presencia de un dígito d en la cadena x significa que una celda viva con d vecinos vivos sobrevive en la siguiente generación del patrón, y la presencia de d en la cadena y significa que una celda muerta con d vecinos vivos se vuelve viva en el próxima generación. Por ejemplo, en esta notación, el Juego de la vida de Conway se denota 23/3. [2] [3]
En la notación utilizada por el paquete de autómatas celulares de código abierto de Golly y en el formato RLE para almacenar patrones de autómatas celulares, se escribe una regla en la forma By / Sx donde xey son iguales que en la notación MCell. Por tanto, en esta notación, el Juego de la vida de Conway se denota como B3 / S23. La "B" en este formato significa "nacimiento" y la "S" significa "supervivencia". [4]
Una selección de reglas realistas
Hay 2 18 = 262,144 posibles reglas realistas, de las cuales solo una pequeña fracción se ha estudiado en detalle. En las descripciones siguientes, todas las reglas se especifican en formato Golly / RLE.
Regla | Nombre | Descripción y fuentes |
---|---|---|
B1357 / S1357 | Replicador | El autómata replicante de Edward Fredkin : cada patrón es eventualmente reemplazado por múltiples copias de sí mismo. [2] [3] [4] |
B2 / S | Semillas | Todos los patrones son fénix, lo que significa que cada célula viva muere inmediatamente, y muchos patrones conducen a un crecimiento caótico explosivo. Sin embargo, se conocen algunos patrones de ingeniería con comportamiento complejo. [2] [5] [6] |
B25 / S4 | Esta regla admite un pequeño patrón de autorreplicación que, cuando se combina con un patrón de planeador pequeño, hace que el planeador rebote hacia adelante y hacia atrás en una caminata pseudoaleatoria. [4] [7] | |
B3 / S012345678 | Vida sin muerte | También conocido como Inkspot o Flakes. Las células que cobran vida nunca mueren. Combina un crecimiento caótico con patrones de escalera más estructurados que se pueden utilizar para simular circuitos booleanos arbitrarios. [2] [4] [8] [9] |
B3 / S23 | La vida | Comportamiento muy complejo. [10] [11] |
B34 / S34 | 34 Vida | Inicialmente se pensó que era una alternativa estable a Life , hasta que la simulación por computadora descubrió que los patrones más grandes tienden a explotar. Tiene muchos pequeños osciladores y naves espaciales. [2] [12] [13] |
B35678 / S5678 | Diamoeba | Forma diamantes grandes con límites caóticamente fluctuantes. Primero estudiado por Dean Hickerson, quien en 1993 ofreció un premio de $ 50 para encontrar un patrón que llenara el espacio con células vivas; el premio fue ganado en 1999 por David Bell. [2] [4] [14] |
B36 / S125 | 2x2 | Si un patrón está compuesto por bloques de 2x2, seguirá evolucionando de la misma forma; agrupar estos bloques en potencias mayores de dos conduce al mismo comportamiento, pero más lento. Tiene osciladores complejos de periodos altos así como un pequeño planeador. [2] [15] |
B36 / S23 | HighLife | Similar a Life pero con un pequeño patrón de autorreplicación. [2] [4] [16] |
B3678 / S34678 | Día y noche | Simétrico bajo inversión on-off. Ha diseñado patrones con un comportamiento muy complejo. [2] [4] [17] |
B368 / S245 | Morley | El nombre de Stephen Morley; también llamado Move. Admite naves espaciales lentas y de período muy alto. [2] [4] [18] |
B4678 / S35678 | Recocer | También se llama la regla de la mayoría retorcida. Simétrico bajo inversión on-off. Aproxima el flujo de acortamiento de la curva en los límites entre células vivas y muertas. [19] [20] [21] |
Varias reglas más se enumeran y describen en la lista de reglas de MCell [2] y por Eppstein (2010) , incluidas algunas reglas con B0 en las que el fondo del campo de células alterna entre vivo y muerto en cada paso. [4]
Cualquier autómata de la forma anterior que contenga el elemento B1 (por ejemplo, B17 / S78 o B145 / S34) siempre será explosivo para cualquier patrón finito: en cualquier paso, considere la celda ( x , y ) que tiene una coordenada x mínima entre celdas que están en, y entre tales celdas la que tiene una coordenada y mínima. Entonces la celda ( x -1, y -1) debe tener exactamente un vecino y se activará en el siguiente paso. De manera similar, el patrón debe crecer en cada paso en cada una de las cuatro direcciones diagonales. Por lo tanto, cualquier patrón inicial no vacío conduce a un crecimiento explosivo. [4]
Cualquier autómata de la forma anterior que no incluya ninguno de B0, B1, B2 o B3 no puede soportar el movimiento o la expansión de patrones porque cualquier celda fuera de una caja de edificio rectangular que contiene el patrón tiene como máximo tres vecinos. La mayoría de los patrones finitos en las reglas cuya notación comienza con B2, y todos los patrones finitos en las reglas que comienzan con B1, crecen en todas las direcciones en lugar de permanecer de tamaño limitado, con un frente que se mueve a la velocidad de la luz. Así, el resto de reglas "interesantes" son las que comienzan con B3 (Game of Life, Highlife, Morley, 2x2, Day & Night) o comienzan con B0 (y sin incluir S8, ya que de lo contrario se puede estudiar el dual). [4]
Generalizaciones
Hay otros autómatas celulares que están inspirados en el Juego de la vida, pero que no se ajustan a la definición de "realistas" dada en este artículo, porque sus vecindarios son más grandes que el vecindario de Moore, o están definidos en tres dimensiones. celosías, o utilizan una topología de celosía diferente. Por ejemplo:
- Las reglas no totalistas dependen de la configuración de células vivas en el vecindario.
- Reglas no isotrópicas que se comportan de manera diferente en diferentes direcciones. Hay 2 512 ≈1,34 * 10 154 reglas de este tipo, incluidas las reglas isotrópicas.
- Las reglas isotrópicas no totalistas se comportan de manera idéntica bajo rotación y reflexión. Hay 2 102 ≈5.07 * 10 30 reglas de este tipo, incluyendo las reglas exterior-totalistic. [22]
- Larger than Life es una familia de autómatas celulares estudiada por Kellie Michele Evans. Tienen vecindarios de radio muy grande, pero realizan un umbral de "nacimiento / muerte" similar a la vida de Conway. Estos autómatas tienen estructuras de "planeador" y "intermitente" inquietantemente orgánicas. [23]
- RealLife es el "límite continuo" de Larger Than Life CA de Evan, en el límite cuando el radio de vecindad llega al infinito, mientras que el espaciado de celosía llega a cero. Técnicamente, no son autómatas celulares en absoluto, porque el "espacio" subyacente es el plano euclidiano continuo R 2 , no el retículo discreto Z 2 . Han sido estudiados por Marcus Pivato. [24]
- Carter Bays ha propuesto una variedad de generalizaciones del Juego de la vida al CA tridimensional definido en Z 3 ( 3D Life ). [25] Bays también ha estudiado CA bidimensional de aspecto real con vecindarios triangulares o hexagonales. [26] [27]
Referencias
- ^ Wolfram, Stephen ; Packard, NH (1985), "Autómatas celulares bidimensionales", Journal of Statistical Physics , 38 (5-6): 901-946, Bibcode : 1985JSP .... 38..901P , doi : 10.1007 / BF01010423 Reimpreso en Wolfram, Stephen (1994), Cellular Automata and Complexity , Westview Press, págs. 211–249, ISBN 978-0-201-62664-3.
- ^ a b c d e f g h yo j k Wójtowicz, Mirek, Léxico de reglas de autómatas celulares - Familia: Vida , Cellebration de Mirek.
- ^ a b Wuensche, Andrew (2011), "16.10 El juego de la vida y otras reglas similares a la vida - rcode", Exploring Discrete Dynamics: The DDLAB manual , Luniver Press, págs. 145-146, ISBN 978-1-905986-31-6.
- ^ a b c d e f g h yo j k Eppstein, David (2010), "Crecimiento y decadencia en autómatas celulares similares a la vida", en Adamatzky, Andrew (ed.), Game of Life Cellular Automata , Springer, págs. 71–98, arXiv : 0911.2890 , doi : 10.1007 / 978-1-84996-217-9_6 , ISBN 978-1-84996-216-2.
- ^ Silverman, Brian, "Cambiando las reglas", La computadora virtual , Asociación Matemática de América.
- ^ Patrones de semillas recolectados por Jason Summers.
- ^ Nivasch, Gabriel (2007), El sistema de fotones / XOR.
- ^ Toffoli, Tommaso ; Margolus, Norman (1987), "1.2 Animate-by-numbers", Cellular Automata Machines: A New Environment for Modeling , MIT Press, págs. 6–7.
- ^ Griffeath, David; Moore, Cristopher (1996), "Life without Death is P-complete" , Complex Systems , 10 : 437–447.
- ^ Gardner, Martin (octubre de 1970), "Juegos matemáticos: las fantásticas combinaciones del nuevo juego de solitario" life " de John Conway ", Scientific American , 223 : 120-123.
- ^ Berlekamp, ER ; Conway, John Horton ; Guy, RK (2004), Winning Ways for Your Mathematical Plays (2a ed.), AK Peters Ltd.
- ^ Poundstone, William (1985), The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge , Contemporary Books, p. 134, ISBN 978-0-8092-5202-2.
- ^ Eisenmann, Jack, 34 VIDA.
- ^ Gravner, Janko; Griffeath, David (1998), "Crecimiento de autómatas celulares en Z 2 : teoremas, ejemplos y problemas", Advances in Applied Mathematics , 21 (2): 241-304, doi : 10.1006 / aama.1998.0599 , MR 1634709.
- ^ Johnston, Nathaniel (2010), "The B36 / S125" 2x2 "Life-Like Cellular Automata ", en Adamatzky, Andrew (ed.), Game of Life Cellular Automata , Springer, págs. 99-114, arXiv : 1203.1644 , Bibcode : 2010golc.book ... 99J , doi : 10.1007 / 978-1-84996-217-9_7 , ISBN 978-1-84996-216-2.
- ^ Bell, David, HighLife: una variante interesante de la vida.
- ^ Bell, David, Day & Night: una variante interesante de la vida.
- ^ Morley, Stephen (2005), b368s245 Guns , archivado desde el original el 11 de marzo de 2006.
- ^ Vichniac, Gérard Y. (1986), "Modelos de autómatas celulares de desorden y organización", en Bienenstock, E .; Fogelman Soulié, F .; Weisbuch, G. (eds.), Organización biológica y sistemas desordenados , Serie ASI de la OTAN, 20 , Springer-Verlag, págs. 3–20, doi : 10.1007 / 978-3-642-82657-3_1.
- ^ Pickover, Clifford A. (1993), "Lámparas de lava en el siglo XXI", The Visual Computer , 10 (3): 173-177, doi : 10.1007 / bf01900906.
- ^ Chopard, Bastien; Droz, Michel (1998), "2.2.4 La regla de recocido", Modelado de sistemas físicos con autómatas celulares , Colección Aléa-Saclay: Monographs and Texts in Statistical Physics, Cambridge University Press, Cambridge, pp. 37-38, doi : 10.1017 / CBO9780511549755 , ISBN 0-521-46168-5, MR 1669736.
- ^ Sapin, Emmanuel (2010), "Más grande que la vida: escala de rango de umbral de las estructuras coherentes de la vida", en Adamatzky, Andrew (ed.), Game of Life Cellular Automata , págs. 135-165, doi : 10.1007 / 978-1 -84996-217-9_9
- ^ Evans, Kellie Michele (2003), "Más grande que la vida: escala de rango de umbral de las estructuras coherentes de la vida", Physica D , 183 (1–2): 45–67, Bibcode : 2003PhyD..183 ... 45E , doi : 10.1016 / S0167-2789 (03) 00155-6.
- ^ Pivato, Marcus (2007), "RealLife: el límite continuo de los autómatas celulares más grandes que la vida", Informática teórica , 372 (1): 46-68, arXiv : math.DS / 0503504 , doi : 10.1016 / j.tcs. 2006.11.019.
- ^ Bays, Carter (2006), "Una nota sobre el descubrimiento de muchas reglas nuevas para el juego de la vida tridimensional", Complex Systems , 16 (4): 381–386.
- ^ Bays, Carter (2007), "El descubrimiento de cañones de planeador en un juego de la vida para la teselación triangular", Journal of Cellular Automata , 2 (4): 345–350.
- ^ Bays, Carter (2005), "Una nota sobre el juego de la vida en teselaciones hexagonales y pentagonales", Complex Systems , 15 (3): 245–252.
enlaces externos
- Griffeath, David, "Reglas de crecimiento totalista con el vecindario de Moore" , The Primordial Soup Kitchen , Departamento de Matemáticas, Universidad de Wisconsin.
- Juego de la vida - Conway y variantes - Herramienta de software en línea