Hormiga de LangtonBeta

Acerca de Hormiga de Langton

La hormiga de Langton es una máquina con dos reglas. En una celda blanca gira 90° a la derecha; en una negra, 90° a la izquierda. Después invierte el color de la celda donde estaba y avanza una casilla. Christopher Langton la presentó en 1986 en su trabajo sobre vida artificial. La regla por defecto de esta herramienta, «RL», es justamente esa: cada letra corresponde a un color, de modo que el color 0 (blanco) significa R y el color 1 significa L.

Al reiniciar hay una hormiga en el centro de una cuadrícula de 256×256 mirando hacia arriba. Los bordes están unidos con el lado opuesto, así que la hormiga nunca se sale. El control de velocidad fija cuántos pasos se calculan por fotograma; con el valor por defecto, 100 a 60 fotogramas por segundo, son unos 6.000 pasos por segundo.

Qué observar 1: la autopista después del caos

Durante los primeros cientos de pasos la hormiga dibuja figuras pequeñas y casi simétricas; luego el dibujo se convierte en una mancha irregular que crece. Esa fase dura unos 10.000 pasos. Entonces, de golpe, entra en un ciclo de 104 pasos que se repite para siempre y va trazando una franja diagonal recta: la «autopista». A la velocidad por defecto llegas en poco más de dos segundos.

En la autopista la hormiga avanza 2 celdas en horizontal y 2 en vertical cada 104 pasos, es decir, 52 pasos por celda diagonal. La prueba automática de la herramienta comprueba exactamente eso: tras 11.000 pasos, otros 104 deben desplazarla (±2, ±2).

Por qué aparece la autopista, y si aparece desde cualquier patrón inicial, sigue sin demostrarse. Lo demostrado es algo más débil: en un plano infinito y partiendo de cualquier patrón finito, la trayectoria de la hormiga no queda acotada en ninguna región finita.

Qué observar 2: la autopista se encuentra consigo misma

En un plano infinito la autopista no terminaría nunca. Esta cuadrícula es una rosquilla finita: la autopista sale por un borde, reaparece por el opuesto y acaba chocando con la mancha caótica inicial o con su propio rastro. El movimiento regular se rompe y vuelve el caos; a veces después nace otra autopista en otra dirección.

Una estimación: en una cuadrícula de 256 celdas la autopista tiene que recorrer cerca de 200 celdas en cada eje para dar la vuelta y llegar a la mancha, y a 52 pasos por celda eso son otros 10.000 pasos aproximadamente. Por eso el choque suele ocurrir hacia el paso 20.000, antes o después según el tamaño de la mancha. Con 1024² la autopista dura mucho más.

Qué observar 3: reglas con más colores

La longitud de la regla es el número de colores. En una celda de color i la hormiga gira según la letra i y pasa esa celda al color i+1 (después del último vuelve al 0). L es izquierda, R derecha, N seguir recto y U media vuelta; se admiten hasta 32 colores.

• RLR: suele seguir creciendo de forma caótica sin llegar a construir autopista.
• LLRR: regla de cuatro colores; compara cómo crece su forma con la de RL.
• Reglas largas como LRRRRRLLR o RRLLLRLLLRRR: algunas rellenan figuras geométricas, como triángulos o cuadrados, en lugar de manchas.
• Reglas con N o U: seguir recto o dar media vuelta cambia por completo el carácter del dibujo.

Varias hormigas a la vez

Toca el lienzo para añadir una hormiga en ese punto con dirección aleatoria (hasta 256). En cada generación todas dan un paso, por orden, sobre la misma cuadrícula, así que una celda invertida por una la lee enseguida la siguiente. Basta con dos hormigas para que borren el trabajo de la otra y retrasen o impidan la autopista.

El marcador muestra por separado generaciones y movimientos. Con 10 hormigas cada generación incluye 10 movimientos, así que los movimientos crecen diez veces más rápido que las generaciones (una hormiga añadida a mitad cuenta desde que aparece). El control de velocidad reparte el total de movimientos por fotograma, de modo que con más hormigas las generaciones avanzan más despacio.

Completitud de Turing

En un artículo de 2002, Gajardo, Moreira y Goles demostraron que la trayectoria de una sola hormiga puede evaluar cualquier circuito booleano si se prepara adecuadamente el patrón inicial de celdas. Esta herramienta siempre parte de una cuadrícula vacía, así que no permite dibujar ese tipo de montaje.

Ejemplos

Cómo se usa

1. Elige una regla predefinida o escribe una con L, R, N y U (de 2 a 32 letras).
2. Ajusta los pasos por fotograma con el control de velocidad.
3. Toca para añadir hormigas; Reiniciar vuelve a una cuadrícula vacía con una sola hormiga.

Preguntas frecuentes

Guías relacionadas

• Cómo las reglas simples crean mundos complejos: del Juego de la Vida a los atascos fantasma