37
$\begingroup$

Langton's ant runs on an infinite white grid. At every white square, it turns right, flips the color of the square, and moves forward one square. At every black square, it turns left, flips the color of the square, and moves forward one square. After many interations, you get complex emergent behavior, such as "recurrent highways" starting at step ~10,000.

Let's suppose that Langton's ant awakens instead on a torus of size $n \times n$. It follows its two rules, thus changing the coloring of the torus. At some point, however, it encounters a colouration it has seen before, while being in the same spot as before, and finds itself in a cycle. How do we find the length of a cycle for a size $n$ torus, and is this result known? We can get a stupid upper bound by observing that there are at most $2^{n^2}$ colorings, $n^2$ positions, and $4$ orientations, so a cycle cannot be longer than $2^{n^2+2}n^2$. Is there a closed form for this, or at least some tighter bounds?


EDIT 1

I ran some quick calculations just to get a feel for the magnitudes of the numbers1. Here's an animation of Langton's ant on a $3 \times 3$ torus, where the cycle takes 22 steps: gif of 3x3 langton's ant

Some more results I got are: $$\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{matrix}$$

The values for $n=9$ and $10$ are due to Connor Harris.

This does not, to my knowledge, match any sequence in OEIS.


EDIT 2

The only real pattern I've found thus far is in the prime factorizations—for odd-sized tori, there is (so far) exactly one factor of 2 in the factorization. However, in even-sized tori, the factors of 2 have multiplicities 3, 5, 4, and 7, which seems interesting. Is there any reason to believe this pattern holds for all even/odd-sized periods?



Footnotes

1: as per Connor Harris's comment, I only checked until the initial state reappeared (i.e., the torus became blank).
2: using Connor Harris's definition of a quasi-cycle as the amount of time it takes to get back to a blank (or full) grid.

$\endgroup$
  • 5
    $\begingroup$ As a first observation, Langton's ant is reversible (i.e. there are no two distinct states of the grid and ant that map to the same state after an additional turn), so on a finite grid however wrapped, the first state that recurs is the initial state. $\endgroup$ – Connor Harris Jul 18 at 14:36
  • 1
    $\begingroup$ Also, I think that cycle should be counted as 22 steps, not 21? You're ignoring both the step into the blank torus and the step out of the blank torus. $\endgroup$ – Connor Harris Jul 18 at 18:14
  • 1
    $\begingroup$ The bound can be tightened a bit by some parity arguments to note that certain configurations of the board are impossible. For example, the board has an odd number of black squares if and only if the ant is rotated a quarter turn from its initial position (because both conditions are equivalent to an odd number of turns having passed), and on an even-sized torus where a taxicab metric mod 2 can be defined, the parity of the ant's distance from its initial location must also be odd. $\endgroup$ – Connor Harris Jul 18 at 18:55
  • 1
    $\begingroup$ @ConnorHarris you're right about the first step, fixed! $\endgroup$ – 416E64726577 Jul 18 at 18:56
  • 1
    $\begingroup$ There's a related Math Overflow question asking for the time it takes for the ant to visit every square on the torus at least once: mathoverflow.net/questions/199543/… $\endgroup$ – Connor Harris Jul 18 at 19:33
12
$\begingroup$

Not an answer, but a quick table with the number of turns until the recurrence of the initial position on rectangular grids small enough to be testable by computer.

The ant is initially facing up (that is, along a column); this matters for non-square boards that may have different periods depending on whether the ant starts by facing in the "long" or the "short" direction. Numbers show the length of time until the first full recurrence: an all-white board with the ant in the original position facing up. A bracketed number before the entry indicates that a "quasi-recurrence," or an all-white or all-black grid with the ant in any cell facing either up or down (or left and right, in the case of a square grid), occurs before the first full recurrence. The development of the board after a quasi-recurrence is isomorphic to that of the actual initial position, but translated, rotated, and (if the board is all black at the beginning of the quasi-recurrence) mirrored across the ant's initial line of sight. The bracketed number shows the number of quasi-recurrences up to and including the first full recurrence; thus, an entry of $[3]~66$ means quasi-recurrences on turns 22 and 44 before a full recurrence on turn 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}

These are usually much smaller than the trivial upper bound in your comment. Periods seem quite erratic in general, especially for boards with at least one small dimension: for example, the periods of boards with 3 rows and 18, 19, and 20 columns are respectively 10,930,388, 592, and 30,519,840. The relative infrequency of quasi-recurrences is striking, as a randomly chosen state of the board is much more likely to be a quasi-recurrence than a the initial state.

Edit: Some other observations. The square toruses of odd side-length $n \in \{3, 5, 7, 9\}$ all have a period divided into $n$ quasi-recurrences, and none of their period lengths is divisible by $4$. Furthermore, with the exception of the $2 \times 2$ torus (for which the quasi-recurrence occurs after turn $4$ with a black grid and the ant rotated 180 degrees in its starting square), every quasi-recurrence I have found in a square or rectangular torus has left a white grid with the ant moved forward or backward within its initial column, but not moved side to side or rotated. For anyone who wants to do their own experimenting, I have a C program (not especially well designed, but workable) here.

$\endgroup$
  • 1
    $\begingroup$ Quasi-recurrences seem unusually common for toruses with 5 columns: they occur for every number of rows between 8 and 17. $\endgroup$ – Connor Harris Jul 18 at 19:28
  • 1
    $\begingroup$ wow, this is awesome. $\endgroup$ – 416E64726577 Jul 18 at 19:29
  • 1
    $\begingroup$ From the table you can see that when the number of columns is 2 or 4, the ant never travels beyond a certain row. An interesting question is for which number of columns the number of rows is bounded. $\endgroup$ – Solomonoff's Secret Jul 18 at 19:36
5
+150
$\begingroup$

We can tighten the upper bound by looking at the symmetries on the torus. The ant's behavior will be the same no matter which of the $n²$ squares it starts on or which of the $4$ directions it is facing. In addition, a reflection coupled with a color inversion is another symmetry. These correspond to the symmetry groups $\mathbb{Z}_n \times \mathbb{Z}_n$, $\mathbb{Z}_4$, and $\mathbb{Z}_2 \times \mathbb{Z}_2$, respectively. The maximum order of any element of $\mathbb{Z}_n \times \mathbb{Z}_n$ is $n$. This means that the ant will find itself on a blank grid but possibly in the wrong position after $2^{n²+2}$ steps, but after doing this $n$ times it must be in the right position. Similarly, the maximum order of any element of $\mathbb{Z}_2 \times \mathbb{Z}_2$ is $2$, so after $2^{n²}n²$ steps we may end up reflected and inverted, but doing this twice we'll end up where we started. The maximum order of $\mathbb{Z}_4$ is $4$, so the symmetry of rotation doesn't help us.

Combining these two symmetries, a better upper bound is $\mathbf{2^{n²+1}n}$.

$\endgroup$
1
$\begingroup$

I've figured out some lower bounds for the number of factors of 2 in the period. This applies to any configuration, not just the all-white one.

It's more convenient if we say that at each time step, the ant is located at the middle of an edge, facing the center of one cell or the other.

Every step flips the color of one cell, so each cell is visited an even number of times, which means the period has to be divisible by 2.

Now consider a torus with an even number of columns. Separate the cells into two sets according to their horizontal coordinate modulo 2. Assume that the ant is pointing horizontally towards a cell in column $i$. In the next two steps, there are four possibilities for its path, but all of them visit two cells in column $i$, and afterwards the ant is horizontal again and pointing towards column $i-1$ or $i+1$. So every path visits two even cells, followed by two odd cells, then two even, two odd, and so on. That means that the period is divisible by 4.

Now let's examine a torus that is even in both directions. Put the cells into four equivalence classes by their coordinates modulo 2. The ant always travels through all four classes in a repeating cycle, either $(0,0), (0,1), (1,1), (1,0)$ or the reverse. To return to the same state, each class must be visited an even number of times, and each class is visited the same number of times, so the period is divisible by 8.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.