5
$\begingroup$

We have a simple (or single) block of Langton's Ants colony which includes two ants looking in the same direction. Their positions can be interpreted as knight's walk. The distances between each next and previous blocks are the same (and equals $1$ cell), so here you can see $3$ such blocks:

For any $n\in \mathbb{N}$ our colony always oscillates. In other words, it repeats all actions after several steps (you may verify it using program named Golly or any another). Therefore, it has a period. What is nice here is the fact that the period is linear and equals $4(8n+3)$ steps. If we increase distance between blocks from $1$ cell to $2$, so areas where they oscillates do not intersect and period is constant ($44$ steps). It is hard to say what exactly the colony does for small $n$, but when we take large values, we may notice $3$ main steps:

  1. builds first triangle after ~$6n$ steps
  2. builds second triangle after ~$12n$ steps
  3. after $2(8n+3)$ steps the ants repeat everything they did symmetrically in backward order

Also we may notice that:

  • Each ant moves in an area bounded by a square with side $n+5$
  • The real area where it moves (equivalently number of cells in area bounded by square which ant visit at least once) equals $5(n+3)$
  • colony moves in area bounded by rectangle with length $3(n+1)$ and width $2(n+2)$
  • real area for colony $3n(n+5)+2$

If we define $T_1(n,k)$ as number of white cells colored to black at the whole period by upper ant in $k$-th block of colony length $n$ blocks (and $T_2(n,k)$ for lower ant), so:

  • $T_1(n,k)=T_2(n,k)=0, n<k$

  • $T_1(n,k)=4(5n+1), k=1$ or $k=n$

  • $T_1(n,k)=2(11n+1), 1<k<n$

  • $T_2(n,k)=4(3n+2), k=1$ or $k=n$

  • $T_2(n,k)=10(n+1), 1<k<n$

  • $T_1(n,k)+T_2(n,k)=4(8n+3), n\geqslant k$

If we define $q(n,k)$ as number of black cells at $k$-th step of colony length $n$ blocks, $q_1(n,k)=q(n+1,k)-q(n,k)$, so:

  • $q(n,k)=q(n,4(8n+3)±k)$

  • $q(n,0)=q(n,4m(8n+3))=0$

  • $q_2(n,k)=q_1(n+1,k)-q_1(n,k)=0, 6n+9\geqslant k$

  • $q_3(n,k)=q_2(n+1,k+6)-q_2(n,k)=0, 12n+4\geqslant k$

  • $q_4(n,k)=q_3(n+1,k+12)-q_3(n,k)=0, 20n-4\geqslant k$

  • $q_5(n,k)=q_4(n+1,k+20)-q_4(n,k)=0, 26n+15\geqslant k$

Finally we have:

$$\sum\limits_{k=1}^{4(8n+3)} q_1(n,k) = 8(77n+31)$$ $$\sum\limits_{k=1}^{4(8n+3)} q(n,k) = 4(77n^2-3(5n-6))$$

How can we prove all (or part) of these facts? Is there another absolute oscillators in LA?

$\endgroup$
  • 1
    $\begingroup$ Hi, welcome to MO. It is still very hard to decipher what the ant colony do, and which of the many many things you wrote you want help with. $\endgroup$ – Amir Sagiv Feb 13 at 19:29
  • 2
    $\begingroup$ the point made in the comment is that there is no single well-defined question; for a helpful answer you want to formulate a specific thing that puzzles you and that can be answered in the answer box. $\endgroup$ – Carlo Beenakker Feb 13 at 20:26
  • 3
    $\begingroup$ I would start with one single pointed question; see how the response is; if there is no response, it makes no sense to ask more. $\endgroup$ – Carlo Beenakker Feb 13 at 20:36
  • 1
    $\begingroup$ I don't know too much about it, but there is an offhand comment on the Langton's Ant wikia that if you take a pair of ants (n,n+1) apart (of the same colour, facing the same direction) then you will get an oscillating pattern - your block seems to be of this type if I understand correctly. Any set of such blocks whose oscillations do not intersect will oscillate, presumably. langtons-ant.wikia.com/wiki/Oscillator $\endgroup$ – Christopher Purcell Feb 15 at 10:17
  • 1
    $\begingroup$ Duplicate on Math.SE. $\endgroup$ – Ilmari Karonen Feb 15 at 18:58

Your Answer

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

Browse other questions tagged or ask your own question.