Máquina de Turing bidimensional con comportamiento emergente
La hormiga de Langton después de 11.000 pasos. Un píxel rojo indica la ubicación de la hormiga.
La hormiga de Langton es una máquina de Turing bidimensional con un conjunto de reglas muy simple pero con un comportamiento emergente complejo . Fue inventada por Chris Langton en 1986 y funciona en una red cuadrada de celdas blancas y negras. [1] La idea se ha generalizado de varias maneras diferentes, como las turmitas, que añaden más colores y más estados.
Normas
Animación de los primeros 200 pasos de la hormiga de Langton
Los cuadrados de un plano están coloreados de diferentes formas, ya sea en blanco o en negro. Identificamos arbitrariamente un cuadrado como la "hormiga". La hormiga puede viajar en cualquiera de los cuatro puntos cardinales en cada paso que da. La "hormiga" se mueve de acuerdo con las siguientes reglas:
En un cuadrado blanco, gira 90° en el sentido de las agujas del reloj, cambia el color del cuadrado y avanza una unidad.
En un cuadrado negro, gira 90° en sentido antihorario, cambia el color del cuadrado y avanza una unidad.
La hormiga de Langton también puede describirse como un autómata celular , donde la cuadrícula está coloreada de negro o blanco y el cuadrado "hormiga" tiene uno de ocho colores diferentes asignados para codificar la combinación del estado negro/blanco y la dirección actual del movimiento de la hormiga. [2]
Modos de comportamiento
Estas reglas simples conducen a un comportamiento complejo. Se pueden observar tres modos distintos de comportamiento [3] cuando se parte de una cuadrícula completamente blanca.
Sencillez. Durante los primeros cientos de movimientos se crean patrones muy simples que suelen ser simétricos .
Caos. Después de unos cientos de movimientos, aparece un patrón irregular de cuadrados blancos y negros. La hormiga recorre un camino pseudoaleatorio hasta llegar a unos 10.000 pasos.
Orden emergente. Finalmente, la hormiga comienza a construir un patrón recurrente de "autopista" de 104 pasos que se repite indefinidamente.
Todas las configuraciones iniciales finitas que se han probado convergen finalmente al mismo patrón repetitivo, lo que sugiere que la "autopista" es un atractor de la hormiga de Langton, pero nadie ha podido demostrar que esto sea cierto para todas esas configuraciones iniciales. Lo único que se sabe es que la trayectoria de la hormiga siempre es ilimitada independientemente de la configuración inicial [4] – esto se conoce como el teorema de Cohen -Kong. [5]
Propiedades computacionales
En 2000, Gajardo et al. mostraron una construcción que calcula cualquier circuito booleano utilizando la trayectoria de una única instancia de la hormiga de Langton. [2]
Ampliación a múltiples colores
Greg Turk y Jim Propp consideraron una extensión simple de la hormiga de Langton donde en lugar de solo dos colores, se usan más colores. [6] Los colores se modifican de manera cíclica. Se utiliza un esquema de nombres simple: para cada uno de los colores sucesivos, se utiliza una letra "L" o "R" para indicar si se debe girar a la izquierda o a la derecha. La hormiga de Langton tiene el nombre "RL" en este esquema de nombres.
Algunas de estas hormigas de Langton extendidas producen patrones que se vuelven simétricos una y otra vez. Uno de los ejemplos más simples es la hormiga "RLLR". Una condición suficiente para que esto suceda es que el nombre de la hormiga, visto como una lista cíclica, consista en pares consecutivos de letras idénticas "LL" o "RR". (el término "lista cíclica" indica que la última letra puede emparejarse con la primera) La prueba involucra las fichas de Truchet .
Algunos patrones de ejemplo en la extensión multicolor de las hormigas de Langton:
RLR: Crece de forma caótica. No se sabe si esta hormiga alguna vez construye una autopista.
LLRR: Crece simétricamente.
LRRRRRLLR: Rellena el espacio de un cuadrado a su alrededor.
LLRRRLRLRLLR: Crea una autopista complicada.
RRLLLRLLLRRR: Crea una forma de triángulo relleno que crece y se mueve después de 15900~ iteraciones.
L 2 NNL 1 L 2 L 1 : Rejilla hexagonal, crece circularmente.
L 1 L 2 NUL 2 L 1 R 2 : Rejilla hexagonal, crecimiento en espiral.
R 1 R 2 NUR 2 R 1 L 2 : Animación.
La cuadrícula hexagonal permite hasta seis rotaciones diferentes, que aquí se indican como N (sin cambio), R 1 (60° en el sentido de las agujas del reloj), R 2 (120° en el sentido de las agujas del reloj), U (180°), L 2 (120° en el sentido contrario a las agujas del reloj), L 1 (60° en el sentido contrario a las agujas del reloj).
Extensión a múltiples estados
Una extensión adicional de las hormigas de Langton es considerar múltiples estados de la máquina de Turing, como si la propia hormiga tuviera un color que pudiera cambiar. Estas hormigas se denominan turmitas , una contracción de " termitas de la máquina de Turing ". Los comportamientos comunes incluyen la producción de autopistas, el crecimiento caótico y el crecimiento en espiral. [7]
Algunos ejemplos de turmitas:
Crecimiento en espiral.
Crecimiento semi-caótico.
Producción de una autopista después de un período de crecimiento caótico.
Crecimiento caótico con una textura distintiva.
Crecimiento con una textura distintiva dentro de un marco en expansión.
Una colonia (como oscilador absoluto) construye un triángulo
Varias hormigas de Langton pueden coexistir en el plano 2D, y sus interacciones dan lugar a autómatas complejos de orden superior que construyen colectivamente una amplia variedad de estructuras organizadas.
Hay diferentes maneras de modelar su interacción y los resultados de la simulación pueden depender en gran medida de las elecciones realizadas. [8]
Pueden coexistir múltiples turmitas en el plano 2D siempre que exista una regla que defina lo que sucede cuando se encuentran. Ed Pegg, Jr. consideró que las hormigas pueden girar, por ejemplo, tanto a la izquierda como a la derecha, dividiéndose en dos y aniquilándose entre sí cuando se encuentran. [9]
Los bucles de Langton : patrones de autómatas celulares que se reproducen a sí mismos
Gusanos de Paterson : una familia de autómatas celulares para modelar el comportamiento alimentario
Referencias
^ Langton, Chris G. (1986). "Estudio de la vida artificial con autómatas celulares" (PDF) . Physica D: Nonlinear Phenomena . 22 (1–3): 120–149. Bibcode :1986PhyD...22..120L. doi :10.1016/0167-2789(86)90237-X. hdl : 2027.42/26022 .
^ ab Gajardo, A.; Moreira, A.; Goles, E. (15 de marzo de 2002). "Complejidad de la hormiga de Langton" (PDF) . Matemáticas Aplicadas Discretas . 117 (1–3): 41–50. arXiv : nlin/0306022 . doi :10.1016/S0166-218X(00)00334-6. S2CID 1107883.
^ Bunimovich, Leonid A.; Troubetzkoy, Serge E. (1992). "Propiedades de recurrencia de autómatas celulares de gas en red de Lorentz". Journal of Statistical Physics . 67 (1–2): 289–302. Bibcode :1992JSP....67..289B. doi :10.1007/BF01049035. S2CID 121346477.
^ Stewart, I. (1994). "The Ultimate in Anti-Particles" (PDF) . Sci. Am . 271 (1): 104–107. Bibcode :1994SciAm.271a.104S. doi :10.1038/scientificamerican0794-104. Archivado desde el original (PDF) el 3 de marzo de 2016 . Consultado el 6 de mayo de 2013 .
^ Gale, D.; Propp, J.; Sutherland, S.; Troubetzkoy, S. (1995). "Más viajes con mi hormiga". Columna de entretenimiento matemático, Mathematical Intelligencer . 17 : 48–56. arXiv : math/9501233 . doi :10.1007/BF03024370. S2CID 123800756.
^ Pegg, Jr., Ed. "Turmite". De MathWorld--A Wolfram Web Resource, creado por Eric W. Weisstein . Consultado el 15 de octubre de 2009 ..
^ Belgacem, S.; Fatès, N. (2012). "Robustez de modelos multiagente: el ejemplo de colaboración entre turmitas con actualización sincrónica y asincrónica" (PDF) . Sistemas complejos . 21 (3): 165–182. doi :10.25088/ComplexSystems.21.3.165.
^ Pegg, Jr., Ed. "Math Puzzle" . Consultado el 15 de octubre de 2009 ..
Enlaces externos
Wikimedia Commons alberga una categoría multimedia sobre La hormiga de Langton y Turmite .
Chris Langton muestra la interacción de varias hormigas en una "colonia"
Columna de Ian Stewart titulada Mathematical Recreations, en la que se utiliza la hormiga de Langton como metáfora de una teoría del todo . Contiene la prueba de que la hormiga de Langton no tiene límites.
Guión de Golly para generar reglas en la extensión de múltiples colores de la hormiga de Langton
