¿Cuál es el período de la hormiga de Langton en un toro?

Question

La hormiga de Langton se ejecuta en un infinito de rejilla blanca. En cada cuadrado blanco, voltea a la derecha, mueve de un tirón el color de la plaza, y se mueve una casilla hacia adelante. En cada cuadrado negro, se gira a la izquierda, mueve de un tirón el color de la plaza, y se mueve una casilla hacia adelante. Después de muchos interations, consigue complejo comportamiento emergente, tales como "recurrente autopistas" a partir del paso ~10,000.

Supongamos que la hormiga de Langton despierta en lugar de un toro de tamaño $n \times n$. Sigue sus dos reglas, cambiando así la coloración del toro. En algún punto, sin embargo, se encuentra con una coloración que haya visto antes, y al mismo tiempo en el mismo lugar que antes, y se encuentra a sí mismo en un ciclo. ¿Cómo podemos encontrar la longitud de un ciclo para un tamaño de $n$ toro, y este resultado se conoce? Se puede obtener un estúpido límite superior observando que hay en la mayoría de las $2^{n^2}$ colorantes, $n^2$ posiciones, y $4$ orientaciones, por lo que un ciclo no puede tener más de $2^{n^2+2}n^2$. Hay una forma cerrada para esto, o al menos algunos de los más estrictos límites?

EDICIÓN 1

Corrí unos rápidos cálculos sólo para tener una idea de las magnitudes de los números¹. He aquí una animación de la hormiga de Langton en un $3 \times 3$ toro, donde el ciclo lleva 22 pasos:

Algunos resultados más que tengo son: $$\begin{matrix} \text{Size} & \text{Steps} & \text{Factorization}\\ \hline 1 & 2 & 2\\ 2 & 8 & 2^3\\ 3 & 66 & 2 \cdot 3 \cdot 11\\ 4 & 96 & 2^5 \cdot 3\\ 5 & 11,710 & 2 \cdot 5 \cdot 1171\\ 6 & 4,592 & 2^4 \cdot 7 \cdot 41\\ 7 & 64,165,598 & 2 \cdot 7^2 \cdot 31 \cdot 21121\\ 8 & 11,502,464 & 2^7 \cdot 73 \cdot 1231\\ 9 & 919,057,222,998 & 2 \cdot 3^2 \cdot 51058734611 \\ 10 & 150,192,928,160 & 2^{5}\cdot5\cdot11\cdot85336891 \\ 11 & >5.7 \cdot 10^{11} & \\ 12 & >5.6 \cdot 10^{11} & \\ \end{de la matriz}$$

Los valores de $n=9$ e $10$ son debido a Connor Harris.

Esto no significa, a mi entender, encontrar cualquier secuencia en OEIS.

EDIT 2

El único patrón que he encontrado hasta ahora es en el primer factorizations-de tamaño irregular tori, no hay (hasta ahora) exactamente un factor de 2 en la factorización. Sin embargo, incluso del tamaño de tori, los factores de 2 multiplicidades 3, 5, 4, y 7, que parece interesante. ¿Hay alguna razón para creer que este patrón se mantiene para todos los pares/impares del tamaño de los periodos?

Notas a pie de página

1: como por Connor Harris comentario, solo he comprobado hasta el estado inicial reapareció (es decir, el toro se convirtió en blanco).
2: el uso de Connor Harris con la definición de un cuasi-ciclo como la cantidad de tiempo que toma para conseguir a un espacio en blanco (o completa) de la cuadrícula.

Answer 1

No una respuesta, pero una rápida tabla con el número de vueltas hasta que la recurrencia de la posición inicial en cuadrículas rectangulares lo suficientemente pequeño como para ser probado por el equipo.

La hormiga es inicialmente hacia arriba (es decir, a lo largo de una columna); esto es importante para que no sean cuadrados tablas que pueden tener diferentes períodos dependiendo de si la hormiga empieza por la frente en el "largo" o "corto" de dirección. Los números muestran que la duración del tiempo hasta la primera recurrencia: un tablero blanco con la hormiga en la posición original hacia arriba. Un número entre corchetes antes de la entrada indica que un "cuasi-periodicidad," o todo blanco o todo negro cuadrícula con la hormiga en cualquier celda mirando hacia arriba o hacia abajo (o hacia la izquierda y la derecha, en el caso de un cuadrado de la cuadrícula), se produce antes de la primera recurrencia. El desarrollo de la junta después de un cuasi-la recurrencia es isomorfo a que de el real de la posición inicial, pero traducido, rotar, y (si la junta es todo negro al principio de la cuasi-recurrencia) reflejado a través de la hormiga inicial de la línea de visión. El número entre corchetes indica el número de cuasi-recurrencias hasta e incluyendo la primera recurrencia; por lo tanto, una entrada de $[3]~66$ significa cuasi-recurrencias en turnos de 22 y 44 ante un lleno total de la recurrencia en la vuelta 66.

\begin{array}{r|rrrrrrrrr} \downarrow\text{rows/cols}\rightarrow&2&3&4&5&6&7&8&9&10 \\ \hline 2 & [2]~8 & 16 & 16 & 16 & 16 & 16 & 16 & 16 & 16\\ 3 & 8 & [3]~66 & 72 & [3]~954 & 196 & 208 & 3{,}008 & 6{,}064 & 304 \\ 4 & 8 & [2]~56 & [2]~96 & 624 & 696 & 3{,}448 & 2{,}336 & 13{,}360 & 2{,}608\\ 5 & 8 & [5]~170 & 96 & [5]~11{,}710 & 16{,}804 & [5]~344{,}300 & 606{,}688 & [5]~14{,}988{,}170 & 1{,}544{,}720\\ 6 & 8 & 120 & 96 & 4{,}184 & 4{,}592 & [3]~296{,}736 & 507{,}056 & 1{,}824{,}688 & 2{,}045{,}304 \\ 7 & 8 & [7]~322 & 96 & 17{,}432 & 714{,}592 & [7]~64{,}165{,}598 & 34{,}882{,}576 & 299{,}407{,}462 & 58{,}495{,}320 \\ 8 & 8 & 208 & 96 & [2]~31{,}600 & 147{,}424 & 10{,}003{,}800 & [2]~11{,}502{,}464 & [2]~1{,}634{,}057{,}664 & [2]~4{,}622{,}916{,}480 \\ 9 & 8 & [9]~522 & 96 & [9]~1{,}568{,}880 & 8{,}066{,}144 & [9]~2{,}508{,}401{,}214 & 3{,}586{,}271{,}200& [9]~919{,}057{,}222{,}998 & 133{,}648{,}022{,}836\\ 10 & 8 & [5]~320 & 96 & [5]~5{,}445{,}220 & 10{,}426{,}496 & [5]~2{,}107{,}770{,}700 & 2{,}084{,}996{,}112 & [5]~374{,}647{,}259{,}920 & 150{,}192{,}928{,}160 \end{array}

Estos son por lo general mucho más pequeño que el trivial límite superior en su comentario. Los períodos parecen bastante errático en general, especialmente para las tablas con al menos uno de pequeñas dimensiones: por ejemplo, los períodos de tablas con 3 filas y 18, 19, y 20 columnas son, respectivamente, 10,930,388, 592, y 30,519,840. La relativa infrecuencia de cuasi-recurrencias es llamativo, como un escogido de forma aleatoria del estado de la junta directiva es mucho más probable que sea un cuasi-la recurrencia de un estado inicial.

Edit: Algunas otras observaciones. La plaza toruses de extraño lado de longitud $n \in \{3, 5, 7, 9\}$ todos tienen un período dividido en $n$ cuasi-recurrencias, y ninguno de su período de longitudes es divisible por $4$. Además, con la excepción de la $2 \times 2$ toro (para que el cuasi-se produce la recurrencia después de girar a la $4$ con una rejilla negra y la hormiga girado 180 grados en su partida de un cuadrado), cada cuasi-recurrencia he encontrado en un cuadrado o rectangular toro ha dejado una cuadrícula blanca con la hormiga se mueve hacia adelante o hacia atrás dentro de su columna inicial, pero no se mueven de lado a lado o girado. Para cualquier persona que quiera hacer sus propios experimentos, tengo un programa en C (no especialmente bien diseñado, pero factible) aquí.

Answer 2

Podemos apretar el límite superior mirando las simetrías en el toro. La hormiga comportamiento será el mismo sin importar la $n²$ plazas empieza o que de la $4$ direcciones a los que se enfrenta. Además, una reflexión junto con una inversión de color es otro de simetría. Estos corresponden a los grupos de simetría $\mathbb{Z}_n \times \mathbb{Z}_n$, $\mathbb{Z}_4$, e $\mathbb{Z}_2 \times \mathbb{Z}_2$, respectivamente. El orden máximo de cualquier elemento de $\mathbb{Z}_n \times \mathbb{Z}_n$ es $n$. Esto significa que la hormiga se va a encontrar en una cuadrícula en blanco, pero posiblemente en la posición incorrecta después de $2^{n²+2}$ pasos, pero después de hacer esto $n$ veces debe estar en la posición correcta. Del mismo modo, el máximo orden de cualquier elemento de $\mathbb{Z}_2 \times \mathbb{Z}_2$ es $2$, así que después de $2^{n²}n²$ pasos que puede terminar refleja y invertida, pero hacerlo dos veces terminamos donde empezamos. El orden máximo de $\mathbb{Z}_4$ es $4$, por lo que la simetría de rotación no nos ayuda.

La combinación de estos dos tipos de simetrías, una mejor cota superior de la es $\mathbf{2^{n²+1}n}$.