Hispanopedia Wiki
Articulo de referencia

Autómata celular realista

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: La matriz de celdas del autómata ...

Hispanopedia WikiContenido en espanolLectura gratuita

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:

  • La matriz de celdas del autómata tiene dos dimensiones.
  • Cada celda del autómata tiene dos estados (conocidos convencionalmente como "vivo" y "muerto", o alternativamente "encendido" y "apagado").
  • El entorno de cada celda es el entorno de Moore ; este consta de las ocho celdas adyacentes a la que se está considerando y (posiblemente) la propia celda.
  • En cada paso de tiempo del autómata, el nuevo estado de una célula se puede expresar 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 totalista externa (a veces llamada semitotalista ).

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 con todos estos criterios. Se utilizan diversos términos 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 las 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 número posible de vecinos y al 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 x e y son secuencias de dígitos distintos del 0 al 8, en orden numérico. La presencia del dígito d en la cadena x indica que una célula viva con d vecinos vivos sobrevive a la siguiente generación del patrón, y la presencia de d en la cadena y indica que una célula muerta con d vecinos vivos cobra vida en la siguiente generación. Por ejemplo, en esta notación, el Juego de la Vida de Conway se denota como 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 las mismas que en la notación MCell. Así, 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 ] Por lo tanto, B3/S23 establece que:

  • Si una célula está muerta y tiene 3 vecinas, entonces la célula nace en el siguiente ciclo.
  • Si una célula está viva y tiene 2 o 3 vecinas, entonces la célula sobrevive hasta el siguiente ciclo.
  • De lo contrario, la celda quedará vacía en el siguiente ciclo.

Una selección de reglas realistas

Diamantes caóticos en la regla Diamoeba (B35678/S5678)
Caos explosivo en la regla Semillas (B2/S)
El juego de la vida de Conway (B3/S23)
Recocido (B4678/S35678)

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

Varias reglas más se enumeran y describen en la lista de reglas MCell [ 2 ] y por Eppstein (2010) , incluyendo algunas reglas con B0 en las que el fondo del campo de células alterna entre vivas y muertas 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 ni la expansión de patrones porque cualquier celda fuera de una caja rectangular que contenga el patrón tiene como máximo tres vecinos. 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 las direcciones en lugar de permanecer de tamaño limitado, con un frente que se mueve a la velocidad de la luz (c) . Por lo tanto, las reglas restantes "interesantes" son las que comienzan con B3 (Juego de la Vida, Highlife, Morley, 2x2, Día y Noche) o las que comienzan con B0 (y no incluyen S8, ya que de lo contrario se puede estudiar el dual). [ 4 ]

Generalizaciones

Existen otros autómatas celulares inspirados en el Juego de la Vida, pero que no se ajustan a la definición de " similar a la vida " que se da en este artículo, porque sus vecindarios son mayores que el vecindario de Moore, o están definidos en retículos tridimensionales, o utilizan una topología de retículo 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. 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 forma idéntica bajo rotación y reflexión. Hay 2 102 ≈5,07*10 30 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 pasan 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 "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 estudiada 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 de "planeador" y "parpadeo" extrañamente orgánicas. [ 23 ]
  • RealLife es el límite continuo del autómata celular Larger Than Life de Evans, en el límite cuando el radio del vecindario tiende a infinito, mientras que el espaciado de la red tiende a cero. Técnicamente, no son autómatas celulares, 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 amplios, actualizaciones fraccionarias yestados de números reales , respectivamente.
  • Carter Bays ha propuesto diversas generalizaciones del Juego de la Vida a autómatas celulares tridimensionales definidos en Z3 ( 3D Life ). [ 25 ] Bays también ha estudiado autómatas celulares 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), Cellular Automata and Complexity , Westview Press, pp. 211–249 , ISBN  978-0-201-62664-3.
  2. 1 2 3 4 5 6 7 8 9 10 11 Wójtowicz, Mirek, Cellular Automaton Rules Lexicon — Family: Life , Mirek's Cellebration, archivado del original el 14-09-2011 , recuperado el 11-09-2011.
  3. 1 2 Wuensche, Andrew (2011), "16.10 El juego de la vida y otras reglas similares a la vida – rcode", Explorando la dinámica discreta: El manual de DDLAB , Luniver Press, pp. 145–146 , ISBN  978-1-905986-31-6.
  4. 1 2 3 4 5 6 7 8 9 10 11 Eppstein, David (2010), "Crecimiento y decaimiento en autómatas celulares similares a la vida", en Adamatzky, Andrew (ed.), Game of Life Cellular Automata , Springer, pp. 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", The Virtual Computer , 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 de 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 "la vida" de John Conway"Scientific American , 223 : 120–123​.
  11. ↑ Berlekamp, ​​ER ; Conway, John Horton ; Guy, RK (2004), Winning Ways for your Mathematical Plays (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 LIFE.
  14. ↑ 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 .
  15. ↑ Johnston, Nathaniel (2010), "El autómata celular realista B36/S125 "2x2"", en Adamatzky, Andrew (ed.), Game of Life Cellular Automata , Springer, pp. 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 interesante variante de la vida.
  18. ↑ Morley, Stephen (2005), b368s245 Armas , archivado del 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 , Serie NATO ASI, vol. 20, Springer-Verlag, pp. 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 en física estadística, Cambridge University Press, Cambridge, pp. 37–38 , doi : 10.1017/CBO9780511549755 , ISBN  0-521-46168-5, MR 1669736 .
  22. ↑ Sapin, Emmanuel (2010), "Más grande que la vida: escalamiento de rango umbral de las estructuras coherentes de la vida", en Adamatzky, Andrew (ed.), Juego de la vida: Autómatas celulares , pp. 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 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", Sistemas complejos , 16 ( 4): 381–386.
  26. ↑ Bays, Carter (2007), "El descubrimiento de cañones planeadores en un juego de la 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.
  • Griffeath, David, "Reglas de crecimiento totalista con vecindario de Moore" , The Primordial Soup Kitchen , Departamento de Matemáticas, Universidad de Wisconsin.
  • Juego de la Vida - Conway y sus variantes - Herramienta de software en línea