23
$\begingroup$

Langton's ant is a cellular automaton running as follows:

Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to the rules below:

  • At a white square, turn 90° right, flip the color of the square, move forward one unit
  • At a black square, turn 90° left, flip the color of the square, move forward one unit

We consider Langton's ant on a torus $n$ by $n$ gridded such that all the squares are white.

Preliminary question: Is it true that Langton's ant will visit every square, for all $n$?

Remark: I've checked it's true for $n \le 1000$. In fact Langton's ant could enter into a local cycle without having visiting every square (see here), so the fact that such phenomena can't appear must be proved.

If so, let $s_n$ be the number of steps Langton's ant needs for visiting all the squares.

Question: what's the asymptotic of $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} } $

Remark: Following the table above, this asymptotic seems to be $\frac{4}{\pi}(nln(n))^2$, as for the random walk.

$\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} } $

Remark: This new data suggests that there is no asymptotic, because for $n$ large $\frac{4(nln(n))^2}{s_n}$ seems bounded in $[1,4]$ but not convergent.

For $n=50$ and the ant starting "up" at position $(25,25)$, the grid looks as follows at step $s_n$:

enter image description here

Now by encoding square's color by how many times it was visited (no effect on the rules) we get:

enter image description here

And for $n=500$ at step $s_n = 12740527$:

enter image description here

These pictures was computed online at http://www.turnerbohlen.com/langtonsant/

And for $n=5000$ at step $s_n = 3331448985$:

enter image description here

For comparison, this last picture was generated from a uniform random walk for $n=5000$ (covered after $2410514205$ steps):

enter image description here

These two last pictures were computed by Sage, with this code.

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ what guarantees that the ant will visit all the squares? $\endgroup$
    – user40023
    Commented Mar 10, 2015 at 8:32
  • 1
    $\begingroup$ @Fry: You're completely right, this is also a problem. In fact the ant could enter into a local cycle without having visiting every square. The fact that such phenomena can't appear must be proved. $\endgroup$
    – Sebastien Palcoux
    Commented Mar 10, 2015 at 8:53
  • 2
    $\begingroup$ Out of curiosity, suppose that we forget about colors and have the ant randomly turn $90^\circ$ left or right with probability 1/2 for each, and then walk one step forward. What is the expected number of steps to visit all the squares on an $n\times n$ (or even $m\times n$) torus? $\endgroup$
    – Richard Stanley
    Commented Mar 14, 2015 at 5:01
  • 1
    $\begingroup$ @RichardStanley I believe that the answer to your question is "yes". The argument would follow the same pattern as in DPRZ. The latter dealt with the case of independent steps - in your situation you have an underlying 4-states Markov chain, and the computation is messier, but the basic estimate (which involves claiming that the probability of hitting a ball of radius R/2 before you hit a ball of radius 2R, starting on the boundary of a ball of radius R, is "essentially" 1/2) should still hold. $\endgroup$
    – ofer zeitouni
    Commented Mar 15, 2015 at 18:45
  • 1
    $\begingroup$ @ZsbánAmbrus: for the last picture, the ant visits a square between $1$ and (around) $300$ times. The red corresponds to $1$, the violet to $300$ and all the intermediate frequencies are uniformly distributed in the visible spectrum. $\endgroup$
    – Sebastien Palcoux
    Commented Mar 16, 2015 at 16:27

1 Answer 1

Reset to default
4
$\begingroup$

I have been playing with Langtons ant for a while now, Have a look at this video which shows 10^30 iterations.

https://www.youtube.com/watch?v=LXDBJ4zKWvI

And the wave equations are here with octave script and a link to octave online where you can run the math.

https://sites.google.com/site/extendedlangtonsant/

Hope someone finds this useful.

Graham

Improve this answer
$\endgroup$
6
  • $\begingroup$ What is the size of the torus in your video? $\endgroup$
    – Sebastien Palcoux
    Commented Jan 5, 2017 at 11:56
  • $\begingroup$ 256x256 with 8 bit grey scale. $\endgroup$
    – user103223
    Commented Jan 5, 2017 at 11:58
  • $\begingroup$ Are you sure that there are $10^{30}$ iterations? (because $s_{250}<10^7$) $\endgroup$
    – Sebastien Palcoux
    Commented Jan 5, 2017 at 12:19
  • 1
    $\begingroup$ 2^30 not 10 sorry, typo. $\endgroup$
    – user103223
    Commented Jan 5, 2017 at 12:33
  • 2
    $\begingroup$ I have now made the langtons ant engine available online. buzwordsalad.com/one.html $\endgroup$
    – user103223
    Commented Oct 13, 2017 at 12:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .