La hormiga de Langton es un autómata celular que se ejecuta de la siguiente manera:
Los cuadrados de un plano se colorean de forma variada, ya sea en blanco o en negro. Nosotros 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 desplaza según las reglas siguientes:
- En un cuadrado blanco, gira 90° a la derecha, cambia el color del cuadrado, avanza una unidad
- En un cuadrado negro, gira 90° a la izquierda, cambia el color del cuadrado, avanza una unidad
Consideramos la hormiga de Langton en un toroide $n$ por $n$ cuadriculado de manera que todos los cuadrados sean blancos.
Pregunta preliminar : ¿Es cierto que la hormiga de Langton visitará cada plaza, para todos $n$ ?
Nota: : He comprobado que es cierto para $n \le 1000$ . De hecho, la hormiga de Langton podía entrar en un ciclo local sin haber visitado todas las plazas (véase aquí ), por lo que hay que demostrar que tales fenómenos no pueden aparecer.
Si es así, que $s_n$ sea el número de pasos que necesita la hormiga de Langton para visitar todas las casillas.
Pregunta : ¿cuál es la asintótica de $s_n$ ?
$\small{ \begin{array}{c|c} n &2&3& 4& 5& 6& 7& 8& 9& 10& 50 & 100 & 500 \newline \hline s_n &3&12&41&62&166&113&318&281&692&57672 & 225905 & 12740527 \end{array} } $
Nota: : Siguiendo la tabla anterior, esta asíntota parece ser $\frac{4}{\pi}(nln(n))^2$ , en cuanto al paseo aleatorio .
$\small{ \begin{array}{c|c} n &1000&2000 & 5000 &6000& 10000& 11000 & 12000 & 13000 & 14000 \newline \hline \frac{4(nln(n))^2}{s_n} &2.919&2.196&2.177&1.770&1.506&2.067&1.734&1.502&1.911 \end{array} } $
Nota: : Estos nuevos datos sugieren que no hay asintótica, porque para $n$ grande $\frac{4(nln(n))^2}{s_n}$ parece limitada en $[1,4]$ pero no convergente.
Para $n=50$ y la hormiga que empieza "arriba" en la posición $(25,25)$ la cuadrícula tiene el siguiente aspecto en el paso $s_n$ :
Ahora codificando el color del cuadrado por el número de veces que fue visitado (sin efecto en las reglas) obtenemos:
Y para $n=500$ en el paso $s_n = 12740527$ :
Estas imágenes fueron computadas en línea en http://www.turnerbohlen.com/langtonsant/
Y para $n=5000$ en el paso $s_n = 3331448985$ :
Para comparar, esta última imagen se generó a partir de un paseo aleatorio uniforme para $n=5000$ (cubierto después de $2410514205$ pasos):
Estas dos últimas imágenes fueron calculadas por Sage, con este código .
0 votos
¿Puedes proporcionar una imagen del camino de las hormigas cuando se colocan en un cuadrado de 50 por 50 antes de que el camino se auto-interse por la condición toroidal? Si r_n es la secuencia en la que se dan r_n pasos "antes de que se produzca un efecto envolvente", tal vez eso sugiera la asintótica de s_n.
2 votos
¿qué garantiza que la hormiga visite todas las casillas?
0 votos
@TheMaskedAvenger: No entiendo tu sugerencia. De todos modos, se puede computar dicha imagen en turnerbohlen.com/langtonsant Por debajo de la mesa, la asintótica parece ser la misma que un paseo aleatorio: $\frac{4}{\pi}(nln(n))^{2}$ .
1 votos
@Fry: Tienes toda la razón, esto también es un problema. De hecho la hormiga podría entrar en un ciclo local sin haber visitado todas las plazas. Hay que demostrar que ese fenómeno no puede aparecer.
0 votos
El sitio web sólo muestra las plazas cubiertas, no el camino recorrido. Esperaba una serie de imágenes, una mostrando un camino de 8 pasos (con algunas flechas de dirección, una de 16 pasos, una de 32 pasos, y una de 64, mostrando la trayectoria de la hormiga como una curva roja superpuesta en la cuadrícula.
2 votos
Por curiosidad, supongamos que nos olvidamos de los colores y hacemos que la hormiga gire al azar $90^\circ$ a la izquierda o a la derecha con probabilidad 1/2 para cada una, y luego caminar un paso hacia adelante. ¿Cuál es el número esperado de pasos para visitar todas las casillas de un $n\times n$ (o incluso $m\times n$ ) toroidal?
0 votos
@RichardStanley: para $n \times n$ torus, heurísticamente, la asíntota debería ser la misma porque la mayor parte del tiempo se utiliza para visitar las últimas áreas pequeñas, mientras que los otros cuadrados se ven distribuidos aleatoriamente blanco/negro, y en tal patrón aleatorio la trayectoria de la hormiga debería ser aleatoriamente izquierda/derecha. Ahora para $n \times m$ torus la situación podría ser muy diferente, véase este nuevo puesto
0 votos
@Sébastien Palcoux: ¿se puede demostrar que para el paseo aleatorio que he descrito anteriormente en el $n\times n$ toro, el tiempo de cobertura es asintóticamente $\frac{4}{\pi}(n\log n)^2$ ?
0 votos
@RichardStanley: No lo sé. Pero para la hormiga de Langton, he editado nuevos datos que sugieren que no hay asintótica.
1 votos
@RichardStanley Creo que la respuesta a su pregunta es "sí". El argumento seguiría el mismo patrón que en DPRZ. Este último trataba el caso de pasos independientes; en tu situación tienes una cadena de Markov subyacente de 4 estados, y el cálculo es más complicado, pero la estimación básica (que implica afirmar que la probabilidad de golpear una bola de radio R/2 antes de golpear una bola de radio 2R, comenzando en el límite de una bola de radio R, es "esencialmente" 1/2) debería seguir siendo válida.
0 votos
En las imágenes que muestran la frecuencia con la que aparece la hormiga en un cuadrado, ¿podrías dar una leyenda de qué color significa qué frecuencia?
1 votos
@ZsbánAmbrus: para la última foto, la hormiga visita una plaza entre $1$ y (alrededor) $300$ tiempos. El rojo corresponde a $1$ El violeta a $300$ y todas las frecuencias intermedias se distribuyen uniformemente en el espectro visible.
0 votos
Qué curioso: habiendo visto primero el hilo relacionado sobre un toroide nx6, cuando vi este, el título parecía decirme "y ahora es el momento de que la hormiga de Langton cubra un toroide cuadrado" :-) :-)