Paterson's 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.

[4] These simulations differed in approach from other cellular automata developed around the same time, which focused on cells and the relationships between them.

The different varieties of worm can be classified systematically by assigning every direction a number and listing the choice made every time a new type of intersection is encountered.

This is a trivial case, so it is usually stipulated that the worm must turn when it encounters a point with only uneaten gridlines.

Many of these are mirror-image duplicates of others, and others die before having to make all the choices in their ruleset, leaving 411 distinct species (412 if the infinite straight-line worm is included).

[7] The first of these was solved by Tomas Rokicki, who determined that it halts after 57 trillion (5.7×1013) timesteps, leaving only {1,0,4,2,0,1,5} unsolved.

He used an algorithm based on Bill Gosper's Hashlife to simulate the worms at extraordinary speeds.

[8] This behaviour is considerably more complex than the related rectangular grid worm, which has a longest path of only 16 segments.