Máquina de Turing bidimensional con comportamiento emergente
La hormiga de Langton después de 11.000 pasos. Un píxel rojo muestra 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 un comportamiento emergente complejo . Fue inventado por Chris Langton en 1986 y se ejecuta en un entramado cuadrado 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 tienen distintos colores, ya sea blanco o 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 según las siguientes reglas:
En un cuadrado blanco, gire 90° en el sentido de las agujas del reloj, cambie el color del cuadrado y avance una unidad.
En un cuadrado negro, gire 90° en el sentido contrario a las agujas del reloj, cambie el color del cuadrado y avance una unidad.
La hormiga de Langton también puede describirse como un autómata celular , donde la cuadrícula es de color blanco o negro y el cuadrado de "hormiga" tiene uno de los ocho colores diferentes asignados para codificar la combinación de estado blanco/negro y la dirección actual de movimiento de la hormiga. . [2]
Modos de comportamiento
Estas reglas simples conducen a un comportamiento complejo. Son evidentes tres modos distintos de comportamiento [3] cuando se comienza en una cuadrícula completamente blanca.
Sencillez. Durante los primeros cientos de movimientos crea patrones muy simples que a menudo son simétricos.
Caos. Después de unos cientos de movimientos, aparece un patrón grande e irregular de cuadrados blancos y negros. La hormiga sigue un camino pseudoaleatorio hasta unos 10.000 pasos.
Orden emergente. Finalmente, la hormiga comienza a construir un patrón recurrente de "carretera" de 104 pasos que se repite indefinidamente.
Todas las configuraciones iniciales finitas probadas eventualmente convergen al mismo patrón repetitivo, lo que sugiere que la "carretera" es un atractor de la hormiga de Langton, pero nadie ha podido demostrar que esto sea cierto para todas esas configuraciones iniciales. Sólo se sabe que la trayectoria de la hormiga siempre es ilimitada independientemente de la configuración inicial [4] ; esto se conoce como teorema de Cohen -Kong. [5]
Propiedades computacionales
En 2000, Gajardo et al. mostró una construcción que calcula cualquier circuito booleano utilizando la trayectoria de una sola instancia de la hormiga de Langton. [2]
Extensió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 forma cíclica. Se utiliza un esquema de nomenclatura simple: para cada uno de los colores sucesivos, se usa 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, esté formado por 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 fichas de Truchet .
Algunos patrones de ejemplo en la extensión de múltiples colores de las hormigas de Langton:
RLR: Crece caóticamente. No se sabe si esta hormiga alguna vez produce una carretera.
LLRR: Crece simétricamente.
LRRRRRLLR: Llena el espacio en un cuadrado alrededor de sí mismo.
LLRRRLRLRLLR: Crea una carretera 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 rejilla hexagonal permite hasta seis rotaciones diferentes, que aquí se indican como N (sin cambios), 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). en el sentido de 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 llaman turmitas , una contracción de " termitas de la máquina de Turing ". Los comportamientos comunes incluyen la construcción de carreteras, el crecimiento caótico y el crecimiento en espiral. [7]
Algunos ejemplos de turmitas:
Crecimiento en espiral.
Crecimiento semicaótico.
Realización de una autopista tras un periodo 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 formas de modelar su interacción y los resultados de la simulación pueden depender en gran medida de las elecciones que se hagan. [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ó hormigas que pueden girar, por ejemplo, hacia la izquierda y hacia la derecha, dividiéndose en dos y aniquilándose entre sí cuando se encuentran. [9]
Bucles de Langton : patrones de autómatas celulares que se reproducen a sí mismos
Gusanos de Paterson : familia de autómatas celulares para modelar el comportamiento alimentario
Referencias
^ Langton, Chris G. (1986). «Estudiando la vida artificial con autómatas celulares» (PDF) . Physica D: Fenómenos no lineales . 22 (1–3): 120–149. Código bibliográfico : 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ática Aplicada Discreta . 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 los autómatas celulares de gas de red de Lorentz". Revista de Física Estadística . 67 (1–2): 289–302. Código Bib : 1992JSP....67..289B. doi :10.1007/BF01049035. S2CID 121346477.
^ Stewart, I. (1994). "Lo último en antipartículas" (PDF) . Ciencia. Soy . 271 (1): 104-107. Código Bib : 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 Entretenimientos Matemáticos, Intelligencer Matemático . 17 : 48–56. arXiv : matemáticas/9501233 . doi :10.1007/BF03024370. S2CID 123800756.
^ Pegg, hijo, ed. "Turmita". De MathWorld: un recurso web de Wolfram, creado por Eric W. Weisstein . Consultado el 15 de octubre de 2009 ..
^ Belgacem, S.; Fatès, N. (2012). "Robustez de los 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, hijo, ed. "Rompecabezas matemático" . Consultado el 15 de octubre de 2009 ..
enlaces externos
Wikimedia Commons tiene medios relacionados con la hormiga de Langton y Turmite .
Chris Langton demostrando múltiples hormigas interactuando en una "colonia"
Columna de Recreaciones Matemáticas de Ian Stewart que 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.
Script Golly para generar reglas en la extensión de múltiples colores de la hormiga de Langton
