Generalized Langton's ant, with programs
Quick introduction - what is an ant ?
An ant is here an automaton that moves on an infinite rectangular grid
called the (ant's) world.
Each cell of the grid as a fixed number of states, numbered from 0 to N-1 (say);
after an ant enters a cell, it turns left or right or back or continues
straight ahead,
according to the cell's state.
After the ant leaves a cell, that cell's state is increased by one
(wrapping from N-1 to 0).
This simple rule leads to surprisingly intricate ant trajectories.
An ant's rule is summarized by a sequence of characters:
| Char. |
Meaning |
| + | turn left |
| - | turn right |
| 0 | continue straight ahead |
| R | U-turn ("reverse") |
The i-th character (1 <= i <= N) tells the ant what to do in state i-1.
The original Langton's ant moves on a grid with two
states 0="left" and 1="right" with the
respective effect on the ant's trajectory.
So its rule is "+-".
Here is an image of Langton's ant's world after 11111 ant steps;
yellow represents state 0=left,
blue represents state 1=right, and the red square is the ant:
At that time Langton's ant is actually building a highway.
The programs
I wrote two complementary programs to explore ant behaviour.
Both programs allow for rules up to 65536 states at least, and the four
+-0R instructions. To determine colours they can use
palettes stored on disk
under a simple text format (Fractint-compatible).
The first program, Ant-ology, features an unbounded world and
the ability to zoom in into any fragment of this world, and to move
inside the world by dragging with the mouse.
The second program, Ant-card, also offers an unbounded world but
in a much less practical way (no zoom-in yet) and uses much more memory
for each world cell;
as a counterpart it is much faster and offers more flexible colouring schemes:
you can colour cells according to diverse cell data.
Both programs require Windows 95 or NT4 or higher.
(They may work with earlier versions but this has not been tested).
Ant-ology
Latest version:
Ant-Card
The second program was designed in order to study the
cardioid
generated by ant ++--, and hence
is called AntCard (under the influence of a well-known DOS restriction,
but on the other hand AntCard is no longer restricted to the cardioid-generating
ant.)
From the "scientifical" point of view it is much more complete,
as it can display not only the world's current state, but several
other measures about each world's cell C:
- number of ant passages at C
- time of first or last ant passage at C
- time since first or last ant passage at C
- cycle index of first or last ant passage at C
- cycles since first or last ant passage at C
(The cycle index is defined as the number of times the ant has
passed through its original position.)
These measures can be displayed according to different scales (linear, logarithmic)
with different palettes (it can read and write
Fractint
palette files).
From the aesthetic point of view it is richer too and produced
images
that I find appealing, some of them strangely reminiscent of
astrophysical images.
Ant-card is also faster than Ant-ology,
mainly because it does no try to be as clever about memory use and other nice
but slow design tricks. (Most of Ant-card's memory use comes from the fact
that it memorizes so much data about each world cell, though.)
Theory about ants
I'm going to expand this chapter in a new page, but I'm a bit lazy, so in short here are...
Some definitions to start with:
- State 0 is named the empty state,
the world is said to be empty
when all its cells are in empty state,
and the world is said to be in
finite state when only finitely many cells are in non-empty state.
- Highways:
according to a result below, non-trivial ants with no R in the rule
cannot have periodic trajectories that bring them back
infinitely many times
to their starting point.
But they can have almost that:
trajectories that repeat periodically modulo a drift of the ant in the world
Such a trajectory is called a highway.
(If you did not understand this you may have better luck on
Anahí Gajardo's pages.)
Some results:
- If the ant rule contains only
+ - and 0 instructions
and contains at least two different instructions,
then the ant's trajectory cannot be periodic,
and hence the ant explores an infinite part of the world
(For a proof in the +- case see [???] or search it
for yourself;
the proof with 0 builds on that result and uses a similar argument.)
- "Butterfly" ants:
Some ants have nice trajectories when they start from an empty world:
- They pass infinitely many times though their starting position
- Each time they pass through the initial position, the
world state is symmetric along an axe.
This is proved for ants whose rule consists of + and -
instruction,
that go in consecutive pairs of identical instructions
(the last instruction may pair with the first one)
(examples: ++--, ++----, +--++--+ (pairing across ends)
but not ++--- (unpaired -)).
(Proof: see
Further travels...
What's striking in the proof is that it relies on the topology on the plane.
)
I call butterfly ants the +/- ants with such an
instruction pairing.
-
Ants whose rule consist only of + and 0 behave like butterfly
ants when they start from an empty world, but for apparently different reasons.
(Proof left as an exercise to the reader.)
(Same for ants with only - and 0 instructions, by symmetry.)
and some open questions:
- Does ant "+-" always produce a highway when it starts from a
non-empty finite world state ?
- Does ant "+0" ever produce a highway, starting from some finite world state ?
(I conjecture that it does not, and would be very happy to see a proof or disproof of
that conjecture.)
- Can some ant do Turing-complete computations, like Conway's Game of Life can ?
Can the halting problem be reduced, for some ant U, to a question
like "does ant U form a highway" ?
- Explain why a few ants like ++---
seem to pass infinitely many times through
their original position, when they start from an empty world, like butterfly ants do.
(Note: ant ++--- does not regularly produce symmetrical patterns.)
- Starting from an empty world,
ant +R-R moves back and forth along a trajectory identical to
that of ant +- (? modulo symmetry ?). Prove that behaviour.
Explore similar situations that arise with other ants with R in the rule.
- Cells visited by ant ++-- (starting from an empty world)
tend to form a surprisingly regular
cardioid-like figure:
explain that. Other ants draw other regular figures.
- In the same vein: for ant ++--- (and others)
starting from an empty world,
when time goes to infinity
the "number of passages" function tends
to get an asymptotical
circular symmetry around the origin: why ?
(I'm surprised to see the continuous circular symmetry stem from such
discrete computations on a discrete cartesian grid !)
(Mathematicians please excuse my loose wording on this problem:
what exactly is meant here needs to be precised. Please use my program
Ant-Card
to see what I mean.)
External links
Note that most other people consider ants with only + and -
instructions, noted L and (ouch!) R.
(© Frédéric van der Plancke 2001;
free of charge license is granted for private and non-profit educational purposes.)