The Mystery of Langton's Ant
and the Cardioid
An applet should open in an external window when you load this page.
Press "Reload" in your browser window to reopen the applet after
you close it.
Directions:
- You can deform the grid by selecting the menu
item "Deform Grid/Subdivide." Then by clicking on a quadrilateral with
green edges, the program will subdivide the quadrilateral into three
quadrilaterals preserving the "checkered" property of the grid. The
program will similarly subdivide the quadrilateral attained by
reflection across the y-axis.
- You can move around the grid by using the
"Change view" menu.
- If you select translate, you can drag the
plane around
- If you select zoom, you can click and drag to
zoom in or away from the point you first click
- After you have deformed the grid to your liking,
click "Ant/Start" to see the grid start to become colored by the Ant
- You can speed up and slow down the Ant using the
"Speed" menu
- If you select one of the "Fast" Speeds the Ant
will quickly leave your viewing angle. Select "View/Global" to see the
Ant's drawing from a distance- each square will appear as a pixel and
the green square represents the region you were alowed to deform (after
some time, the outline should converge to a cardioid)
How the Ant moves:
- The "Ant" has two properties: a location and a
direction, he starts on a quadrilateral just to the "east" of the y-axis
facing "east"
- Think of the grid as being numbered by elements
of the cyclic group Z4. To denote this numbering,
we use the colors [0]=Black, [1]=Blue, [2]=White, [3]=Yellow.
- The Ant proceeds by repeating the following
pattern:
- If the square he is standing on is numbered
[0] or [1] he turns left and otherwise he turns right.
- He increments the numbering of the square by
adding one modulo 4.
- He walks forward.
New Features:
- New Views:
- Immediate
Change/Global Immediate Change: Shows the squares of type [1] and [3] in
red (the ones that will change next time the ant passes them)
- Visits: Shows the
number of times the Ant has visited a square (colored mod 500)
- Visits Under
Square Root: Changes what looks like a cardioid into what looks like a
circle
- New Deform Grid Options:
- Selecting two adjacent squares
after selecting Cut and Reglue (I/II) removes the two squares and
reglues them in two distinct ways. (I) is essentially the inverse
operation to Subdivision. (II) adds handles to the grid.
- The first four grid coloring
options allow you to paint the region you are able to edit in such a way
as to not mess up the symmetry of the Ant. You should do any physical
grid deformations first (or else symmetry might become messed up)
- The last two coloring options
allow for experimentation, but using these will most likely ruin the
symmetry.
- Random Jumps:
- If from the Deform Grid menu,
you check Random Jumps, when he completes a full loop, he will restart
at some other randomly choosen square on the axis of symmetry. (does
not work well with deformations yet)
What is known:
- Under these circumstances, the ant returns to
the square where he starts facing the same direction as he started
infinitely often. At these points when he returns, the coloring of the
grid exhibits reflective symmetry.
- The Ant's path is unbounded, thus the pattern
cannot repeat.
(*The conjecture:
- Consider any tiling by squares of an oriented
once punctured surface that admits reflective symmetry and a checkered
pattern. If in a nieghborhood of the puncture, the tiling looks like the
ususal tiling of plane by squares with some finite number removed, then
the asymptotic limit of the set of all squares visited by the Ant in
time t can be taken to be a
cardioid. (Probably not rigorously stated)
*)
- This fails when Cut and Reglue II is selected and used to
remove the two squares directly above where the ant starts. As below. It
also fails if the two squares directly below where the ant starts used
to Cut and Reglue II. However interestingly,
if both deformations are done at the same time, the Ant draws as usual,
only upside down. Returning infinitely often with symmetry is still
satisified by these examples.
Here is a good reference on Langton's Ant:
D. Gale, J. Propp, S. Sutherland, S. Troubetzkoy
Further travels with my ant.
Mathematical Intelligencer 17 (1995), no. 3, 48--56.
Among other things, they demonstrate this reflective symmetry property of some Ants. A while back I wrote
a similar proof of this fact. It is available here.
