MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo IMG
HOME > PAST ISSUE > Article Detail

COMPUTING SCIENCE

In Search of the Optimal Scumsucking Bottomfeeder

Brian Hayes

Rectangulus and the Quadrille Worm

A few years after the Raup-Seilacher model appeared, Frank Papentin of Tübingen chose trace fossils as one of several examples he explored in a simulation of Darwinian evolution. Instead of tuning parameters by hand to achieve the desired patterns, Papentin encoded the parameters in genes subject to mutation and recombination, then applied selection pressure favoring compact but self-avoiding configurations. His worms lived on a square lattice—he named the species Rectangulus—and so they could make turns only in multiples of 90 degrees. If you make allowance for this geometric limitation, the patterns bear a strong resemblance to some trace fossils.

On the other hand, the genes that governed the behavior of Rectangulus were rather complex, which somewhat diminishes the sense of wonder when an intricate pattern evolves without the programmer's direct intervention. The genes regulated behaviors such as turning spontaneously, turning to avoid a trail, avoiding narrow channels between trails, maintaining contact with existing trails, and switching from spiraling to zigzag motion. Given these traits as tools to work with, it's not hard to see how Darwinian selection would construct patterns as elaborate as those of the trace fossils; the question is how such traits evolved. Still, Papentin's study was another pioneering one, an early application of the technique now known as genetic programming.

In the same period, Michael S. Paterson of the University of Warwick, John Horton Conway of the University of Cambridge and Michael Beeler of MIT were also inspired by the trace-fossil patterns. They turned the foraging process into a mathematical puzzle, which was described in a technical report by Beeler and in a Scientific American article by Martin Gardner. Their version of the worm's world is highly abstract. The worm eats its way along the links of a regular lattice, at each node choosing a new link from among those that have not already been eaten. (If there are no uneaten links, the worm dies.) The choice of direction is determined entirely by the pattern of eaten and uneaten links. For example, suppose a worm on a square grid enters a node and finds that the link to its right is already eaten but the links to the left and straight ahead are still available. The worm must choose one of the uneaten links, and will always make the same choice in the same circumstances. The set of rules for making decisions defines the species of worm.

On a square grid (Beeler calls this a "quadrille worm") there are only a few possible species, and none of them lives long; the largest quadrille fossil consists of just 16 links. But on a triangular grid, where six links meet at each node, Beeler counted 1,296 species. Most of these worms too have only a limited lifespan, but some sail off toward infinity and will never die. The fate of a few species remains uncertain even today: They do not have the kind of repetitive, propagating pattern seen in the infinite species, but they have been followed for hundreds of millions of steps without showing any sign of expiring.

What's lost in this model, of course, is most of the biology; the scheme is too abstract to predict the behavior of real worms. Even so, it offers evidence that very simple rules might be enough to generate the trace-fossil patterns.





» Post Comment

 

EMAIL TO A FRIEND :

Of Possible Interest

Feature Article: Simulating Star Formation on a Galactic Scale

Feature Article: Digital Forensics

Letters to the Editors: Attractive Models

Subscribe to American Scientist