Autómata celular con apariencia real

Tipo de autómata celular con similitudes con el Juego de la Vida de Conway

Un autómata celular (AC) es similar a la vida (en el sentido de ser similar al Juego de la Vida de Conway ) si cumple los siguientes criterios:

• El conjunto de celdas del autómata tiene dos dimensiones.
• Cada célula del autómata tiene dos estados (denominados convencionalmente "vivo" y "muerto", o alternativamente "encendido" y "apagado").
• El vecindario de cada celda es el vecindario de Moore ; está formado por las ocho celdas adyacentes a la celda en consideración y (posiblemente) la celda misma.
• En cada paso de tiempo del autómata, el nuevo estado de una célula puede expresarse como una función del número de células adyacentes que están en estado vivo y del propio estado de la célula; es decir, la regla es totalística externa (a veces llamada semitotalística ).

Esta clase de autómatas celulares recibe su nombre del Juego de la Vida (B3/S23), el autómata celular más famoso, que cumple todos estos criterios. Se utilizan muchos términos diferentes para describir esta clase. Es habitual referirse a ella como la "familia de la Vida" o simplemente utilizar frases como "similar a la Vida".

Notación para reglas

Existen 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 posible número de vecinos y estado de una célula; los bits de este número son cero o uno según si una célula con ese vecindario está muerta o viva en la siguiente generación. ^[1] Las otras dos notaciones descomponen la misma secuencia de bits en una cadena de caracteres que es más fácil de leer para un humano.

En la notación utilizada por la Celebration de Mirek, una regla se escribe como una cadena x/y donde cada uno de x e y es una secuencia de dígitos distintos de 0 a 8, en orden numérico. La presencia de un dígito d en la cadena x significa que una célula 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 célula muerta con d vecinos vivos se vuelve viva en la siguiente 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 Golly y en el formato RLE para almacenar patrones de autómatas celulares, una regla se escribe en la forma By/Sx donde x e y son iguales que en la notación MCell. Por lo tanto, en esta notación, el Juego de la vida de Conway se denota B3/S23. La "B" en este formato significa "nacimiento" y la "S" significa "supervivencia". ^[4]

Una selección de reglas realistas

Los diamantes caóticos en la regla Diamoeba (B35678/S5678)

Caos explosivo en la regla de Semillas (B2/S)

El juego de la vida de Conway (B3/S23)

Recocido (B4678/S35678)

Existen 2 ¹⁸  = 262.144 reglas posibles para la vida, de las cuales solo una pequeña fracción se ha estudiado en detalle. En las descripciones que aparecen a continuación, todas las reglas se especifican en formato Golly/RLE.

Se enumeran y describen varias reglas más 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 celdas 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 la coordenada x mínima entre las celdas que están activadas, y entre dichas celdas la que tiene la 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 B0, B1, B2 o B3 no puede soportar el movimiento o la expansión de patrones porque cualquier celda fuera de una caja de construcción rectangular que contenga el patrón tiene como máximo tres vecinas. La mayoría de los patrones finitos en reglas cuya notación comienza con B2, y todos los patrones finitos en reglas que comienzan con B1, crecen en todas direcciones en lugar de permanecer de tamaño limitado, con un frente que se mueve a la velocidad de la luz. Por lo tanto, las reglas "interesantes" restantes son las que comienzan con B3 (Game of Life, Highlife, Morley, 2x2, Day&Night) o comienzan con B0 (y no incluyen S8, ya que de lo contrario se puede estudiar el dual en su lugar). ^[4]

Generalizaciones

Existen otros autómatas celulares inspirados en el Juego de la Vida, pero que no encajan en la definición de "similares a la vida" que se da en este artículo, porque sus vecindarios son más grandes que el vecindario de Moore, o están definidos en redes tridimensionales, o utilizan una topología de red diferente. Por ejemplo:

• Las reglas no totalitarias dependen de la configuración de las células vivas en el vecindario.
  • Reglas no isotrópicas que se comportan de manera diferente en distintas direcciones. Existen 2 ⁵¹² ≈1,34*10 ¹⁵⁴ reglas de este tipo, incluidas las reglas isotrópicas. ^{[ cita requerida ]}
  • Las reglas isótropas no totalistas se comportan de manera idéntica bajo rotación y reflexión. Existen 2 ¹⁰² ≈5,07*10 ³⁰ reglas de este tipo, incluidas las reglas totalistas externas. ^[22]
• Las reglas de generaciones incluyen uno o más estados de "muerte" a los que las células cambian en lugar de morir instantáneamente. Los ejemplos más famosos de esta categoría son las reglas "El cerebro de Brian" (B2/S/3) y "La guerra de las galaxias" (B2/S345/4). Los patrones aleatorios en estas dos reglas presentan una gran variedad de naves espaciales y rastrillos con una velocidad de c, que a menudo chocan y se combinan para formar aún más objetos.
• Larger than Life es una familia de autómatas celulares estudiados por Kellie Michele Evans. Tienen vecindarios de radio muy grande, pero realizan un umbral de "nacimiento/muerte" similar al de la vida de Conway. Estos autómatas tienen estructuras "planeadoras" y "intermitentes" extrañamente orgánicas. ^[23]
• RealLife es el límite continuo del CA Larger Than Life de Evan, en el límite a medida que el radio de vecindad tiende a infinito, mientras que el espaciado reticular tiende a cero. Técnicamente, no son autómatas celulares en absoluto, porque el "espacio" subyacente es el plano euclidiano continuo R ² , no la red discreta Z ² . Han sido estudiados por Marcus Pivato. ^[24]
• Lenia es una familia de autómatas celulares continuos creada por Bert Wang-Chak Chan. El espacio, el tiempo y los estados del Juego de la Vida se generalizan a dominios continuos, utilizando vecindarios grandes, actualizaciones fraccionarias y estados de números reales, respectivamente.
• Carter Bays ha propuesto una variedad de generalizaciones del Juego de la Vida a CA tridimensionales definidas en Z ³ ( 3D Life ). ^[25] Bays también ha estudiado CA bidimensionales similares a la vida con vecindarios triangulares o hexagonales. ^{[26] [27]}

Referencias

1. 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/BF01010423Reimpreso en Wolfram, Stephen (1994), Autómatas celulares y complejidad , Westview Press, págs. 211–249, ISBN 978-0-201-62664-3.
2. Wójtowicz, Mirek, Léxico de reglas de autómatas celulares - Familia: vida, celebración de Mirek.
3. Wuensche, Andrew (2011), "16.10 El juego de la vida y otras reglas similares a las de la vida – rcode", Explorando la dinámica discreta: el manual DDLAB, Luniver Press, págs. 145-146, ISBN 978-1-905986-31-6.
4. Eppstein, David (2010), "Crecimiento y decadencia en autómatas celulares realistas", 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.
5. Silverman, Brian, "Cambiando las reglas", La computadora virtual, Asociación Matemática de América.
6. Patrones para semillas recopilados por Jason Summers.
7. Nivasch, Gabriel (2007), El sistema fotón/XOR.
8. Toffoli, Tommaso ; Margolus, Norman (1987), "1.2 Animación por números", Máquinas autómatas celulares: un nuevo entorno para el modelado , MIT Press, págs. 6-7.
9. Griffeath, David; Moore, Cristopher (1996), "La vida sin muerte es P-completa", Complex Systems , 10 : 437–447.
10. 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.
11. Berlekamp, ​​ER ; Conway, John Horton ; Guy, RK (2004), Maneras ganadoras para sus jugadas matemáticas (2.ª ed.), AK Peters Ltd.
12. Poundstone, William (1985), El universo recursivo: complejidad cósmica y los límites del conocimiento científico , Contemporary Books, pág. 134, ISBN 978-0-8092-5202-2.
13. Eisenmann, Jack, 34 VIDA.
14. Gravner, Janko; Griffeath, David (1998), "Crecimiento de autómatas celulares en Z ² : teoremas, ejemplos y problemas", Advances in Applied Mathematics , 21 (2): 241–304, doi : 10.1006/aama.1998.0599 , MR  1634709.
15. Johnston, Nathaniel (2010), "El autómata celular realista B36/S125 "2x2"", 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.
16. Bell, David, HighLife: una variante interesante de la vida.
17. Bell, David, Día y noche: una variante interesante de la vida.
18. Morley, Stephen (2005), b368s245 Armas, archivado desde el original el 11 de marzo de 2006.
19. Vichniac, Gérard Y. (1986), "Modelos de autómatas celulares de desorden y organización", en Bienenstock, E.; Fogelman Soulié, F.; Weisbuch, G. (eds.), Sistemas desordenados y organización biológica , NATO ASI Series, vol. 20, Springer-Verlag, págs. 3–20, doi :10.1007/978-3-642-82657-3_1.
20. Pickover, Clifford A. (1993), "Lámparas de lava en el siglo XXI", The Visual Computer , 10 (3): 173–177, doi :10.1007/bf01900906.
21. Chopard, Bastien; Droz, Michel (1998), "2.2.4 La regla de recocido", Modelado de sistemas físicos mediante autómatas celulares , Colección Aléa-Saclay: Monografías y textos de física estadística, Cambridge University Press, Cambridge, pp. 37–38, doi :10.1017/CBO9780511549755, ISBN 0-521-46168-5, Sr.  1669736.
22. Sapin, Emmanuel (2010), "Más grande que la vida: escalamiento del 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
23. Evans, Kellie Michele (2003), "Más grande que la vida: escalamiento del 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.
24. Pivato, Marcus (2007), "RealLife: el límite continuo de los autómatas celulares más grandes que la vida", Theoretical Computer Science , 372 (1): 46–68, arXiv : math.DS/0503504 , doi :10.1016/j.tcs.2006.11.019.
25. 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.
26. Bays, Carter (2007), "El descubrimiento de los cañones planeadores en un juego de vida para la teselación triangular", Journal of Cellular Automata , 2 (4): 345–350.
27. 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 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