Travels of an ant: mathematical mysteries in the trails of virtual ants.

Scurrying across a sidewalk, navigating the ridges of a wrinkled picnic blanket, or crowding around a crumb on a kitchen floor, these spindly, communal insects typically attract scant attention to their varied doings--except when they get in the way. Yet in their foraging and social organization, ants display remarkable behavior worthy of detailed study.

James Propp, however, is interested in the activities of a different sort of ant. A mathematician at the Massachusetts Institute of Technology, he has spent the better part of a decade tracking an imaginary critter--a virtual ant--roaming an infinite checkerboard.

Exhibited on a computer screen, this mathematical ant blindly follows the dictates of the simple rules that Propp imposes on it and traces out a winding path across the plane. "These rules allow no freedom at all, yet you can generate very complicated--even baffling--patterns," Propp says.

"The movements may remind you a little bit of a real ant," he adds.

But Propp doesn't insist on a connection between the actions of the carefully shepherded, simple-minded ants in his simulations and the multifarious antics of ants in the wild. What intrigues him are the intricate patterns and symmetries that can emerge out of a bare-bones mathematical framework.

This pursuit represents more than just recreational mathematics. Computer scientists have studied similar models to probe the limits of computation, and physicists have used them to simulate particle interactions in a liquid.

Propp's ant universe is an example of a cellular automaton.

The mathematician starts by setting up a field of cells, typically in a checkerboard or honeycomb pattern, and allowing each cell to exist in one of several possible states. A set of rules specifying how neighboring cells influence each other determines how these states change from one moment to the next. The resulting transitions can be visualized on a grid and strung together into a movie.

One of the most famous of these models is the game "Life," invented by mathematician John H. Conway of Princeton University. The game is played on an infinite grid of square cells. Each cell is initially marked as either occupied or vacant, creating some sort of arbitrary starting configuration.

Changes occur in jumps, with each cell responding according to the rules. Any cell having two occupied cells as neighbors stays in its original state. An empty cell adjacent to three occupied cells gets filled. An occupied cell surrounded by four or more occupied cells is emptied.

These simple rules engender a surprisingly complex world that displays a wide assortment of interesting events and patterns--a microcosm that captures elements of life, birth, growth, evolution, and death. Indeed, cellular automata in general have become important mechanisms for investigating pattern formation, evolution, and artificial life (SN: 7/23/94, p.63; 5/19/90, p.312).

Virtual ants inhabit a similar realm, but the rules they obey operate a little differently. In this type of cellular automaton, a change of state occurs in only one cell at a time instead of across the board with each step.

"Their lifestyle is a humble one," Propp says.

Suppose all the cells of a particular ant universe begin in one of two possible states, designated 0 and 1 (or white and black when visualized on a computer screen). Initially, the virtual ant sits on a cell, facing in one of the four compass directions. The ant then moves in that direction to the adjacent cell.

When it arrives at its new location, the ant is programmed to change its heading by 90o to the left if it lands on a 0 cell or 90o to the right if it lands on a 1 cell. As it leaves, it causes the cell's state to switch from 0 to 1 or from 1 to 0. Thus, on its next visit to this particular cell, the ant will find an altered state and behave accordingly.

Depending on the initial distribution of states, the ant appears to perform an intricately choreographed dance across the plane.

This is a cybercritter that can't stick to the straight and narrow. Constantly changing direction, it interacts with its own path--its own history--as it treks from cell to cell.

Propp didn't actually invent the basic ant universe. He originally came across it in the work of Christopher G. Langton of the Santa Fe (N.M.) Institute. In the mid-1980s, Langton created a number of these simulated ant farms, including examples in which several ants move at the same time, to explore how cellular automata might serve as models of various processes characteristic of living systems.

The special case in which all cells are initially in the 0 state provides a glimpse of how a virtual ant typically behaves. From time to time, the ant returns to its starting point, leaving a symmetrical pattern of cells, all in the 1 state, in its wake. At other times, the pattern gets scrambled.

"This sort of symmetry is not that of an idealized, growing snowflake, which remains completely symmetrical from beginning to end," Propp observes. "Rather, it is a recurrent symmetry that is repeatedly destroyed and recreated."

Hence, most of the time the ant's track looks disorganized. But at certain intervals a symmetrical pattern emerges, only to be broken up again.

This behavior intrigued Propp. Picking up where Langton left off, he extended the original model to an infinite array of cells and many more steps.

"To determine the potentially complicated consequences of these extremely simple rules, the ant had to do its dance for at least 10,000 steps before you could see its long-term destiny," he says.

Propp was surprised to find that after thousands of steps of rather chaotic movement, the ant would suddenly appear to make up its mind about where it wanted to go. It would head off, creating a broad track--a highway--in one of the four possible diagonal directions, never to return to its starting point.

He found that the same phenomenon occurs for many initial conditions, though precisely when the highway starts and in which direction it proceeds varies. This startling behavior is somehow encoded in the rules but becomes evident only when the ant is activated for a sufficiently long period.

Meanwhile, computer scientist Greg Turk of the University of North Carolina at Chapel Hill had independently developed the same kind of simulation while experimenting with a special type of Turing machine. Such a machine serves as a convenient mathematical model of computation, performing a sequence of basic operations to accomplish anything that a modern digital computer can.

Normally, a Turing machine can be pictured as a device that reads symbols--one at a time--from a row of cells on an infinitely long tape. The given rules specify which symbol to write in the current cell, in which direction to move the tape, and what instruction to follow next.

Turk extended this model to two dimensions, freeing the read-write device to traverse a square grid. Programmed appropriately, his "tur-mite" could generate a variety of patterns, including spirals, symmetrical shapes, and the highways that Propp had discovered.

At the same time, physicists turned up a connection between Propp's ant universe and theoretical structures called lattice gases. Consisting of particles (such as atoms) pinned to particular locations in a lattice and interacting only with their neighbors, a lattice gas is a useful model for studying how local forces acting on fixed particles add up to such observable characteristics as pressure, viscosity, or diffusion rate in a real gas or liquid.

Taking such an approach, Serge E. Troubetzkoy, now at the University of Alabama in Birmingham, and Leonid A. Bunimovich of the Georgia Institute of Technology in Atlanta proved what has become the fundamental theorem of cybermyrmecology--the study of virtual ants. They demonstrated that an ant's track is unbounded.

This means that no matter what the initial configuration, the ant never wanders about in such a way that its universe--the pattern of 0s and 1s in the cells as well as the ant's position and orientation--returns to its initial state. In other words, Propp remarks, the ant universe never repeats itself.

This theorem applies even when cells in the ant universe can exist in more than two states. For example, a cell may cycle through five states, going from 0 to 4 and back to 0, over the course of successive visits by the ant. The ant itself is programmed to turn left or right according to a rule string such as LLRRL, with one turning instruction for each of the five possible cell states.

Given enough time, a virtual ant will escape from any finite region. Along the way, depending on the particular rule string it obeys, the ant often manages to build a sequence of ever larger symmetrical structures before transforming its world into a chaotic jumble or a perpetual highway.

How recurrent symmetry arises was one of the first mathematical mysteries that confronted Propp and others enthralled by this ant universe. With no memory and no ability to plan, how did a single-stepping, short-sighted ant know what to do to maintain the resemblance between the way things look at one location and the way things look far away?

One of those who joined the hunt for a solution to this conundrum was Bernd Rummler, a mathematician working as a computer programmer at an insurance company in Gottingen, Germany. Limitations of the computer system to which he had access forced him to look for another way of representing an ant's movements on a computer screen.

Instead of using blocks of color or shades of gray to represent the state of each cell, he marked the squares with two quarter circles in opposite corners. Arrows showed the direction of travel for either a left turn or a right turn.

Such squares are known as Truchet tiles. Positioned next to each other to form a grid, they join together in such a way that the markings create circles and wavy curves across the plane (see illustrations).

"We get an entirely different way of visualizing what a virtual ant does," Propp says. In essence, the ant follows whatever curve it's on, flipping or not flipping a tile as required by its program when it leaves one cell for another.

From the patterns of the curves winding from cell to cell, it was easier than before to tell where the ant had been--and especially where it was going. The curves enabled Rummler and others to see that, between the moments when a symmetrical structure appears in the ant's universe, the symmetry is not completely destroyed; rather, it goes "underground," only to reappear a moment later in a larger pattern.

In other words, the recurrent emergence of symmetry is embedded in the curved tracks of a curiously switched railroad that the ant simply follows.

Propp, Troubetzkoy, Scott Sutherland of the State University of New York at Stony Brook, and David Gale of the University of California, Berkeley, describe these insights into the ant's behavior in the summer Mathematical Intelligencer.

Many mysteries of the ant universe remain unsolved. Lots of variations of the basic rules and the distribution of initial states haven't been explored. No one has looked seriously at virtual ants traversing a three-dimensional lattice of cubes.

Propp himself has started thinking about ant behavior on a field of hexagons. "I played with this during the summer on a courtyard with hexagonal tiles and little stones to mark the states," he says. "I got nice, symmetric patterns--in some ways, prettier that those of the [checkerboard] ant."

It's all part of the wonders of ants on the move.

Interested readers can look up virtual ants at Scott Sutherland's World Wide Web site at:

http://www.math.sunysb.edu/~scott/ants/.

Copies of his and Propp's ant simulators (computer programs written in C for Unix-based machines) are also available at that site.