Hormiga de Langton

La hormiga de Langton es la más sencilla de una familia de hormigas. Con n colores, numerados desde 0 para las casillas vacías, una regla es una cadena $r = r_0 r_1 \cdots r_{n-1}$ de letras R y L, una por color. La hormiga de Langton es RL. La hormiga está en una casilla p mirando en una dirección d, y un paso es

La hormiga no tiene memoria y solo ve el color que pisa. Aquí puedes verla crear orden, después una maraña y luego una carretera; también puedes hacerla retroceder, colorear casillas en su camino y probar otras cadenas de letras.

Los colores son los estados de la regla. El plano no tiene bordes ni conecta un lado con el opuesto. La curva de la parte superior del panel cuenta las casillas coloreadas después de cada paso.

Al empezar en el plano vacío mirando hacia arriba, la hormiga crea primero pequeños patrones ordenados, algunos simétricos bajo media vuelta, como en el paso 473. Después aparece una maraña aparentemente aleatoria durante unos diez mil pasos. Desde el paso 9 977, la hormiga repite los mismos 104 movimientos, con cada ciclo desplazado (−2, 2): dos casillas a la izquierda y dos hacia abajo. Construye una franja diagonal llamada autopista, y cada 104 pasos añade exactamente 12 casillas coloreadas. Solo se repiten los movimientos de la hormiga y la franja bajo ella. La maraña de atrás permanece donde estaba.

Repetir unos cuantos ciclos no demuestra nada: el siguiente podría encontrarse con una casilla coloreada y desviarse. Por eso la página solo garantiza una carretera después de comprobarla. Al terminar el último ciclo, las casillas que leyó, trasladadas según el desplazamiento de la hormiga, deben mostrar los colores que tenían las casillas originales antes del ciclo; la hormiga también debe mirar en la misma dirección que entonces. Además, en cada ciclo futuro, las casillas que quedan fuera de las del ciclo anterior deben estar vacías ahora y no haber sido visitadas por ningún ciclo desde el comprobado. Así, cada ciclo encuentra exactamente lo mismo que el anterior y repite los mismos movimientos para siempre. La línea discontinua de la curva marca el comienzo de la repetición. Si hay una casilla coloreada por delante, la página la rodea con un círculo y no da ninguna garantía.

Para el plano vacío, la carretera queda por tanto demostrada mediante el cálculo y esta comprobación. Con RL, todos los tableros con un número finito de casillas coloreadas que se han probado terminan en una carretera, pero nadie ha demostrado que todos lo hagan.

Cada paso se puede deshacer. La hormiga mira en la dirección en la que acaba de moverse, así que la casilla de la que vino está detrás, y el color de esa casilla ha avanzado una posición en el ciclo. Un paso atrás es

Por tanto, el tablero y la hormiga determinan el estado del paso anterior. Atrás hace retroceder a la hormiga según la regla, sin reproducir una grabación al revés.

Con más letras, cada visita cambia una casilla al siguiente color. Partiendo del plano vacío, los botones de reglas producen formas muy distintas: un patrón aparentemente simétrico con LLRR, un cuadrado casi macizo con LRRRRRLLR y un triángulo que crece con RRLLLRLLLRRR. No se sabe cómo terminan estos tres casos. LLRRRLRLRLLR sí construye una carretera, tras unos treinta mil pasos.

Chris Langton describió la hormiga en 1986 como ejemplo de vida artificial.