13
$\begingroup$

This post follows this other post about times cover by Langton's ant of $n$ by $n$ gridded torus.

For $n$ by $n$ gridded torus, I've checked for $n \le 1000$ that the ant covers all. This fact needs to be proved for every $n$, but this should be not surprising.

Contrariwise, we can easily checked that for the $n$ by $2$ gridded torus and $n \ge 3$, the ant enters into a cycle before covering the torus:

enter image description here

Idem for the $n$ by $4$ gridded torus and $n \ge 5$:

enter image description here

Now for $n$ by $6$ (with $n \ge 5$) there is a problem.
For $n=50$, it is not yet covered after around $10^4$ steps:

enter image description here

and it is not yet covered after around $10^5$ steps:

enter image description here

in fact I've checked that it's also not covered after $10^7$ steps.

So there are two possibilities:

  • for $n$ by $6$ gridded torus, the covering needs a long time, but finite (checked for $n \in [5, 60]$).
  • $\exists n_0$ such that the ant covers $n_0$ by $6$ but not $n$ by $6$ for $n > n_0$.

Question: Does Langton's ant cover every n by 6 gridded torus ($n \ge 5$)?
[If yes, what's the asymptotic of the covering time? Else, what's $n_0$?]

If no: i.e. if the ant enters into a cyclic pattern of width $n_0$ then we need a priori to go at least up to the step $4 \cdot 6 \cdot n_0 \cdot 2^{6 \cdot n_0}$ for checking that, which could become out of computation.

If yes: let $s^m_n$ be the number of steps Langton's ant needs for covering the $n$ by $m$ torus.

$\scriptsize{ \begin{array}{c|c} n &10&20&30&40&50&60&70&80 \newline \hline s^6_n &977&17623&87113&3135267&19563171&331665879&4738404219&44105120036 \newline \hline s^n_6 &240&6708&166542&2027581&32781038&220780386&4820615241&76325278885 \newline \hline n/ln(s^6_n) &1.45&2.04&2.6373&2.6741&2.9781&3.0581&3.1419&3.2639 \newline \hline n/ln(s^n_6) &1.82&2.26&2.4952&2.7543&2.8892&3.1229&3.1395 &3.1925 \end{array} } $

This new data (sage computation) suggests that: $s^6_n \sim s^n_6 \sim e^{n/c}$, with $c \sim 3$.

Remark: we can checked that there is no such a problem for the $n$ by $3$ or $5$ or $7$ $\dots$ gridded torus, but there is the same problem for the $n$ by $8$ or $10$ or $12$ $\dots$ gridded torus (at least up to $18$).

The pictures was computed online on http://www.turnerbohlen.com/langtonsant/

Improve this question
$\endgroup$
12
  • $\begingroup$ Where does 4.6 come from (in your upper remark)? $\;$ $\endgroup$
    – user5810
    Commented Mar 13, 2015 at 7:05
  • $\begingroup$ @RickyDemer: for $n_0$ by $6$ there are $6n_0$ squares and each square can have two states (black or white) so we get $2^{6n_0}$. Next about the position of the ant we have to multiply by $6n_0$, and about its state (up, down, left or right), we have to multiply by $4$. So finally, we get $4.6n_0.2^{6n_0}$. $\endgroup$
    – Sebastien Palcoux
    Commented Mar 13, 2015 at 7:12
  • 1
    $\begingroup$ I'm not sure how much this would help, but one could try splitting the grid into congruent pieces and computing a lookup table with [after_colors,exit_edge] for each possible [entry_edge,before_colors]. $\:$ (Such a table could presumably be compressed, and might reveal that some a-priori-possible color configurations of the pieces are not actually possible.) $\;\;\;\;$ $\endgroup$
    – user5810
    Commented Mar 13, 2015 at 7:40
  • 3
    $\begingroup$ Since this torus has a different shape, initial orientation matters. Did you check for both orientations? and are the numbers the same? $\endgroup$
    – The Masked Avenger
    Commented Mar 13, 2015 at 15:51
  • 2
    $\begingroup$ Following up on Ricky Demer's suggestion, it seems natural to me to replace the current system with a slightly more complicated one: for n=6, have a six-square ring replaced by a number in [0,63], with 144 combinations possible for entry and exit points, of which only 48 are used. Although this only halves the number of steps, using this representation may allow some number theoretical analysis to show how quickly certain configurations are reached. Gerhard "Also Has Small Transition Table" Paseman, 2015.03.13 $\endgroup$
    – Gerhard Paseman
    Commented Mar 13, 2015 at 18:26

1 Answer 1

Reset to default
1
$\begingroup$

Not sure if this helps but I have derived a wave equation for langtons ant so you can now evaluate it algebraically.

Octave online code available to support the math https://simple.m.wikipedia.org/wiki/User:Dakoder#/search

The rules of the ant model tbe coulomb force in newtons Move = a point charge displaced due to electric field Rotate = a point charge rotating under a magnetic field (spin) flip colour = photon emit and absorb event.

psi delta holds the total sum of all point charges Psi theta is the photon move and rotate The second iteration function is the photon even The whole equation is based on schroedingers equation with time and position fixed as a constant which is why x and omega t are absent as they are unity.

Improve this answer
$\endgroup$

You must log in to answer this question.

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