La hormiga de Langton es una máquina de Turing universal 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 universalidad de la hormiga de Langton fue probada en 2000. [2] La idea se ha generalizado de varias formas diferentes, como turmitas que añaden más colores y más estados.
Reglas
Los cuadrados de un avión se colorean de forma variada, ya sea en blanco o negro. Identificamos arbitrariamente un cuadrado como la "hormiga". La hormiga puede viajar en cualquiera de las cuatro direcciones cardinales en cada paso que da. La "hormiga" se mueve de acuerdo con las siguientes reglas:
- En un cuadrado blanco, gire 90 ° en el sentido de las agujas del reloj, voltee el color del cuadrado, avance una unidad
- En un cuadrado negro, gire 90 ° en el sentido contrario a las agujas del reloj, voltee el color del cuadrado, avance una unidad
La hormiga de Langton también se puede describir como un autómata celular , donde la cuadrícula es de color negro o blanco y el cuadrado de la "hormiga" tiene uno de ocho colores diferentes asignados para codificar la combinación del estado blanco y negro y la dirección actual de movimiento de la hormiga. . [2]
Modos de comportamiento
Estas simples reglas 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 traza un camino pseudoaleatorio hasta alrededor de 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 probadas eventualmente convergen en el mismo patrón repetitivo, lo que sugiere que la "autopista" es un atractor de la hormiga de Langton, pero nadie ha podido probar que esto sea cierto para todas estas configuraciones iniciales. Solo se sabe 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]
Universalidad
En 2000, Gajardo et al. mostró una construcción que calcula cualquier circuito booleano usando la trayectoria de una sola instancia de la hormiga de Langton. [2] Además, sería posible simular una máquina de Turing arbitraria utilizando la trayectoria de la hormiga para el cálculo. Esto significa que la hormiga es capaz de realizar cálculos universales.
Extensión a varios colores
Greg Turk y Jim Propp consideraron una simple extensión 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 usa 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 oa la derecha. La hormiga de Langton tiene el nombre "RL" en este esquema de nomenclatura.
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 fichas de Truchet .
RLR: Crece de forma caótica. 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 enrevesada.
RRLLLRLLLRRR: Crea una forma de triángulo relleno que crece y se mueve.
L2NNL1L2L1: Rejilla hexagonal, crece circularmente.
L1L2NUL2L1R2: Rejilla hexagonal, crecimiento en espiral.
R1R2NUR2R1L2: Animación.
La cuadrícula hexagonal permite hasta seis rotaciones diferentes, que se indican aquí como N (sin cambios), R1 (60 ° en el sentido de las agujas del reloj), R2 (120 ° en el sentido de las agujas del reloj), U (180 °), L2 (120 ° en el sentido contrario a las agujas del reloj), L1 (60 ° en sentido antihorario).
Extensión a varios 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 las " termitas de la máquina de Turing ". Los comportamientos comunes incluyen la producción de carreteras, el crecimiento caótico y el crecimiento en espiral. [7]
Crecimiento en espiral.
Crecimiento semicaótico.
Producción de una carretera después de un período de crecimiento caótico.
Crecimiento caótico con textura distintiva.
Crecimiento con una textura distintiva dentro de un marco en expansión.
Construyendo una espiral de Fibonacci .
Construyendo un diamante en crecimiento
Extensión a varias hormigas
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. No hay necesidad de resolución de conflictos, ya que todas las hormigas que se sientan en el mismo cuadrado quieren hacer el mismo cambio en la cinta. Hay un video de YouTube que muestra estas múltiples interacciones de hormigas.
Múltiples turmitas pueden coexistir en el plano 2D siempre que exista una regla sobre lo que sucede cuando se encuentran. Ed Pegg, Jr. consideró a las hormigas que pueden girar, por ejemplo, tanto a la izquierda como a la derecha, dividiéndose en dos y aniquilándose entre sí cuando se encuentran. [8]
Ver también
- Juego de la vida de Conway: autómata celular bidimensional ideado por JH Conway en 1970
- Bucles de Langton : patrones de autorreproducción en una regla de autómata celular particular, investigados en 1984 por Christopher Langton
- Gusanos de Paterson : una familia de autómatas celulares para modelar el comportamiento de alimentación
- Turmita : una máquina de Turing que tiene una orientación y un estado actual y una "cinta" que consiste en una cuadrícula bidimensional infinita de celdas.
Referencias
- ^ Langton, Chris G. (1986). "Estudio de 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 .
- ^ a b c 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 .
- ^ Pratchett, Terry (1999). La ciencia del Mundodisco .
- ^ Bunimovich, Leonid A .; Troubetzkoy, Serge E. (1992). "Propiedades de recurrencia de autómatas celulares de gas de celosía de Lorentz". Revista de física estadística . 67 (1-2): 289-302. Código Bibliográfico : 1992JSP .... 67..289B . doi : 10.1007 / BF01049035 . S2CID 121346477 .
- ^ Stewart, I. (1994). "Lo último en Anty-Particles" (PDF) . Sci. Am . 271 (1): 104-107. Código Bibliográfico : 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, Inteligencia matemática . 17 : 48–56. arXiv : matemáticas / 9501233 . doi : 10.1007 / BF03024370 . S2CID 123800756 .
- ^ Pegg, Jr., Ed. "Turmita" . De MathWorld - Un recurso web de Wolfram, creado por Eric W. Weisstein . Consultado el 15 de octubre de 2009 . Cite journal requiere
|journal=
( ayuda ). - ^ Pegg, Jr., Ed. "Rompecabezas matemático" . Consultado el 15 de octubre de 2009 ..
enlaces externos
- Weisstein, Eric W. "La hormiga de Langton" . MathWorld .
- Simulación interactiva de hormigas de Langton basada en JavaScript
- Demostración en línea de la hormiga de Langton
- Chris Langton demostrando la interacción de varias hormigas en una "colonia"
- Hormigas generalizadas
- Un ejemplo interactivo en línea
- Demostración de JavaScript
- Applet de Java con varios colores y hormigas programables
- La hormiga de Langton en 3-D (ejemplos y un pequeño programa de demostración)
- Una implementación más de la hormiga de Langton en 3-D
- 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.
- Applet de Java en varias cuadrículas y gráficos editables, muestra cómo la hormiga puede calcular puertas lógicas
- Programando las hormigas de Langton en Python usando Pygame .
- Una demostración en video de diferentes hormigas Langton de varios colores
- Guión de Golly para generar reglas en la extensión de múltiples colores de la hormiga de Langton
- Aplicación hormigas de Langton con configuraciones personalizadas , desarrollada en C ++ usando SDL 1.2
- DataGenetics, la hormiga de Langton (y la vida)
- Aplicación de escritorio de Windows 10