Hormiga de langton

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 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 una red cuadrada de celdas en blanco y negro. La universalidad de la hormiga de Langton se demostró en el año 2000. La idea se ha generalizado de varias maneras diferentes, como las turmitas que agregan más colores y más estados.

Reglas

Animación de los primeros 200 pasos de la hormiga de Langton

Los cuadrados de un plano se colorean de forma diversa, ya sea en 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 de acuerdo con las siguientes reglas:

• En una plaza blanca, girar 90° en el reloj, girar el color de la plaza, avanzar una unidad
• En una plaza negra, girar 90° en sentido contrario, girar el color de la plaza, avanzar una unidad

La hormiga de Langton también se puede describir como un autómata celular, donde la cuadrícula es de color blanco o negro y la "hormiga" el cuadrado 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.

Modos de comportamiento

Estas reglas simples conducen a un comportamiento complejo. Tres modos distintos de comportamiento son evidentes cuando se comienza en una cuadrícula completamente blanca.

1. Simplicidad. Durante los primeros cientos de movimientos crea patrones muy simples que a menudo son simétricos.
2. Caos. Después de unos pocos cientos de movimientos, aparece un gran patrón irregular de cuadrados negros y blancos. La hormiga rastrea un camino pseudo-aleatorio hasta alrededor de 10.000 pasos.
3. Orden urgente. Por último, la hormiga comienza a construir un patrón recurrente de "autopista" de 104 pasos que repite indefinidamente.

Todas las configuraciones iniciales finitas probadas finalmente 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 demostrar que esto sea cierto para todas las configuraciones iniciales. Solo se sabe que la trayectoria de la hormiga siempre es ilimitada, independientemente de la configuración inicial, esto se conoce como el teorema de Cohen-Kong.

Universalidad computacional

En 2000, Gajardo et al. mostró una construcción que calcula cualquier circuito booleano utilizando la trayectoria de una única instancia de la hormiga de Langton. 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 computación universal.

Extensión a varios 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. Los colores se modifican de forma cíclica. Se utiliza un esquema de nombres simple: para cada uno de los colores sucesivos, una letra "L" o "R" se utiliza 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, consta de 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 multicolor de las hormigas de Langton:
• 

  RLR: Crece caóticamente. No se sabe si esta hormiga produce alguna vez una carretera.

• 

  LLRR: Crece simétricamente.

• 

  LRRRLLR: Llena el espacio en una plaza alrededor de sí mismo.

• 

  LLRRRLRLRLLR: Crea una carretera convocada.

• 

  RRLLLRLLLRRR: Crea una forma de triángulo llena que crece y se mueve.

• 

  L₂NNL₁L₂L₁: Rejilla hexagonal, crece circularmente.

• 

  L₁L₂NUL₂L₁R₂: Cuadrícula hexagonal, crecimiento espiral.

• 

  R₁R₂NUR₂R₁L₂: Animación.

La cuadrícula hexagonal permite hasta seis rotaciones diferentes, que se indican aquí como N (sin cambios), R₁ (60° en el sentido de las agujas del reloj), R₂ (120 ° en sentido horario), U (180°), L₂ (120° en sentido antihorario), L₁ (60° en sentido antihorario).

Extensión a varios estados

Otra extensión 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 máquina de Turing". Los comportamientos comunes incluyen la producción de autopistas, el crecimiento caótico y el crecimiento en espiral.

• Algunos ejemplos de turmitas:
• 

  Crecimiento espiral.

• 

  Crecimiento semi-caótico.

• 

  Producción de una carretera 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 de expansión.

• 

  Construyendo una espiral Fibonacci.

• 

  Construcción de un diamante en crecimiento

Extensión a múltiples hormigas

Una colonia (como oscilador absoluto) construye un triángulo

Múltiples 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 realizadas.

Se puede elegir que todas las hormigas sentadas en el mismo cuadrado hagan simultáneamente el mismo cambio en la cinta. Hay un video de YouTube que muestra la simulación de tales interacciones múltiples de hormigas. También existe una familia de colonias que es un oscilador absoluto con periodo lineal 4(8n+3).

Múltiples turmitas pueden coexistir en el plano 2D siempre que haya una regla que defina lo que sucede cuando se encuentran. Ed Pegg, Jr. consideró hormigas que pueden girar, por ejemplo, tanto hacia la izquierda como hacia la derecha, partiéndose en dos y aniquilándose entre sí cuando se encuentran.