Paterson's worms

Paterson's worms are a family of cellular automata devised in 1971 by Mike Paterson and John Horton Conway to model the behaviour and feeding patterns of certain prehistoric worms. In the model, a worm moves between points on a triangular grid along line segments, representing food. Its turnings are determined by the configuration of eaten and uneaten line segments adjacent to the point at which the worm currently is. Despite being governed by simple rules the behaviour of the worms can be extremely complex, and the ultimate fate of one variant is still unknown.

The worms were studied in the early 1970s by Paterson, Conway and Michael Beeler, described by Beeler in June 1973, and presented in November 1973 in Martin Gardner's "Mathematical Games" column in Scientific American.

Electronic Arts' 1983 game Worms? is an interactive implementation of Paterson's worms, where each time a worm has to turn in a way that it lacks a rule for, it stops and lets the user choose a direction, which sets that rule for that worm.

Paterson's worms are an attempt to simulate the behaviour of prehistoric worms. These creatures fed upon sediment at the bottom of ponds and avoided retracing paths they had already travelled because food would be scarce there but, because food occurred in patches, it was in the worm's interest to stay near previous trails. Different species of worm had different innate rules regarding how close to travelled paths to stay, when to turn, and how sharp a turn to make. In 1969 Raup and Seilacher created computer simulations of the fossilized worm trails, and these simulations inspired Paterson and Conway to develop a simple set of rules to study idealized worms on regular grids.

Conway's original model was a worm on an orthogonal grid but this produced only three different species of worm, all with rather uninteresting behaviour. Paterson considered worms on a triangular grid. Paterson's worms were described by Beeler in a Massachusetts Institute of Technology AI Memo (#290) and were presented in November 1973 in Martin Gardner's "Mathematical Games" column in Scientific American, and later reprinted in Gardner 1986. These simulations differed in approach from other cellular automata developed around the same time, which focused on cells and the relationships between them. Simple computer models such as these are too abstract to accurately describe the behaviour of the real creatures, but they do demonstrate that even very simple rules can give rise to patterns resembling their tracks.

...
Wikipedia