Esta página en español You're in the english version

Langton's Ant: Life and Deeds

Click to go   What is it?
Click to go   How does it work?
Click to go   What do we know about it?
Click to go   Where does it come from?
Click to go   What generalizations are possible?

What is it?

Langton's ant is a very simple and deterministic discrete dynamical system. It can be viewed as a cellular automaton, as a two-dimensional Turing machine, or as an agent-system. When we say that it's discrete, we mean that there is a discrete world, which is updated in discrete time (that's to say: "if we have this state of things in time 0, then the state of things in time 1 is this..."). The "world" is usually a bidimensional square grid, which in principle is supposed to be infinite. For practical reasons, it is customary to write the simulations using finite thoruses, where the upper border of the grid is identified with the lower, and the right border with the left one. Each position in the grid (i.e., the meeting points of the lines, also called cells or nodes) has a state, which can be either white or black (you can also take 0/1, false/true, or, directly, left/right). The ant is a little thing that walks on the grid, moving according to the states it finds, and changing these states as it walks over them.

How does it work?

The rule The ant is always moving from one cell to another. At each time step, it enters the cell in which it had its head, turns to the left or to the right, according to the state of the cell (to the left if it finds white -or 0-, and to the right in the other case), and toggles the state of the cell from white to black or from black to white. And that's all! There is no randomness, no complicated calculation, no long-distance sight.

Other graphs: A way to see the grid is as a set of squares, with some lines ("edges") connecting them, if they are neighbors. We can then extend the idea to other regular grids: take a honeycomb picture, put cells in the junctions of the lines, consider the cells joined by lines as neighbors, and voilà, that's the hexagonal grid. The triangular grid is defined in a similar way (see the picture below). We can define the rule in a general way for arbitrary graphs, if we have a picture of them: the ant enters a node (cell), and turns to the left or to the right, depending on the state it finds there. In a general graph, "turning to the left" means to take the next edge, moving clockwise around the node, and starting with the edge on which the ant was before.

hexagonal grid triangular grid a graph

By the way: a simple extension of the system is the inclusion of several ants; the easiest way to do it is to let the ants run simultaneously on the grid, ignoring each other (even if they walk over the same sites). We haven't studied systems with several ants: the dynamics generated by a single one is complicated enough! An applet involving multiple ants can be found here.

What do we know about it?

On the square grid

t=96 t=384
First, let us describe what happens when you let the ant run, starting with an empty grid (all the cells have the state 0); you can also watch it by yourself in the applet. At the first stage, for approximately 500 steps, the ant draws symmetrical patterns, with rotational symmetry of order 2 and 4. After iteration 500, the symmetry breaks down, and the ant seems to go crazy. Its walk looks random for ten thousand steps. Then, suddenly, the ant seems to decide where it wants to go: it begins building the so-called "highway", a periodic structure.
t=1440 t=9540
It's a periodic motion of the ant, but with a drift: after 104 steps, the position of the ant is the same as before, but standing on the next stair of the staircase it is building. The ant will now build the highway forever, if we give it an infinite space to do it, and we don't place obstacles in its way. One intriguing empirical observation is the following: if you place, at the beginning, any finite number of black states on the grid, the trajectory of the ant will be, of course, completely different
t=10640 t=12922
in each case, but it will always end up building the highway, in some direction. Try it in the applet. But there is no proof for this fact, it's only an observation! This is the most beautiful open problem related to the ant: find a proof, or find a counterexample. On the other hand, a more general fact has been proved: the trajectory of the ant is always unbounded. This was first shown by Bunimovich and Troubetzkoy in 1992; the second of them generalized the result later, showing that the set of cell that are visited infinitely often by the ant (for a given initial configuration) has no corners [where a corner of a set is defined as a cell where at least two neighbors are not in the set, and these are not opposite to each other].

On the hexagonal grid

t = 72 t = 408 t = 810 t = 2600 t = 15600
periodic When other regular grids are considered, the behavior is still interesting, but dramatically different. In the hexagonal grid, when the ant starts with an all-white configuration, it builds increasingly growing patterns with bilateral symmetry, and keeps returning to the origin (see pictures above). Moreover, in this case it is possible to build configurations for which the ant's trajectory is periodic (and therefore bounded). One of them, with period 92, is shown on the right, and is included in the applet.

On the triangular grid

For the triangular grid, the dynamics is very simple. For all initial configurations, the ant soon (after 3 or 4 steps) chooses a direction, and then follows it, its movement limited to two rows of cells, regardless of the states it finds. Two examples are shown here; the visited cells are shown with a black border.
Much of the work that has being done on the ant has been "experimental", and there is still a lack of exact results; most of the existing ones can be found in the references (see the Bibliography).

Where does it come from?

The ant was christened after his first discoverer, Chris Langton, who was looking for simple models with complex behaviors, and presented it (among others) in an article for Physica D in 1986. He was interested in the fundamental properties of biological systems, and is considered one of the fathers (or the father) of the young and popular field called artificial life. But this wasn't the only time the ant was discovered. In 1988 Greg Turk, a graduate student of computer science, considered different examples of simple two-dimensional Turing machines, allowing the machines to move on the (two-dimensional) tape instead of moving the tape under them. One of the "tur-mites" thus created was exactly Langton's ant, and is depicted (highway included) in the article of Scientific American in which A.K. Dewdney presented Turk's findings.

The third time, the ant arose in the land of physics. There are several models for the microscopical simulation of fluid dynamics. In the Lorenz Lattice Gases, a particle moves around between fixed scatterers, which modify its trajectory and, in some models, may be modified in turn by the collisions One of this models, the Ruijgrok-Cohen model, corresponds to the ant. In fact, much of the research on the ant has been done by Cohen and his co-workers. (Notice that this is E.G. Cohen, not to be confused with the Jack Cohen we mention in the Links page.)

What generalizations are possible?

Of course, the number of possible generalizations is infinite; here we will only mention the ones that have been already examinated in some publication.

As seen above, the first possible generalization is the inclusion of grids different from the square one. This is a sensible extension, since there is no special reason for supposing the square lattice to be the best approximation to two-dimensional interactions; moreover, as seen above, the dynamics of the system appears to strongly depend on the topology of the underlying graph. Further extension in this direction are the inclusion of general bi-regular graphs, or of general planar graphs (which have been done in our group), or the consideration of higher dimensions, as has been considered by L. Bunimovich.

On the other hand, the dimension of the grid may also be reduced: the ant can be defined on the line. Since the resulting dynamics is rather trivial, several other definitions of the rule have been considered (some by A. Gajardo in our group, some by L. Bunimovich).

Different definitions of the rule have been explored on the square lattice too. One way of generalization, which includes several rules, was considered by Jim Propp, and defines a rule through a rule-string: instead of going from 0 to 1 and back, a cell chooses its succesive states following a string like, say, 001011. Some of the resulting ants happen to build highways; other have increasing bilateral symmetrical patterns like the ones already found in the hexagonal grid; some seem to be "chaotic"... etc.

Some people have used multiple ants, sometimes with a non-trivial interaction among them. Further possibilities are the inclusion of some memory, of more information, etc.

Last updated: 03-31-2002.
Contact: agajardo@dim.uchile.cl