OCA:Paterson's worms

Paterson's worms are a family of cellular automata devised in 1971 by Mike Paterson and John Horton Conway. The worms were described by Michael Beeler in June 1973, and presented in November of that year in Martin Gardner's "Mathematical Games" column in Scientific American.

Rules

The worm starts at some point of an infinite triangular grid. It starts moving along one of the six gridlines that meet at each point and, once it has travelled one unit of distance, it arrives at a new point.

The worm then decides, based on the distribution of traversed and untraversed gridlines, what direction it will take. The directions are relative to the worm's point of view. If the worm has not encountered this exact distribution before it may leave along any untraversed gridline. From then on, if it encounters that distribution again, it must move in the same way.

If there are no untraversed gridlines available, the worm dies and the simulation ends.

The six directions are numbered as follows:

Direction 0 indicates the worm continues to travel straight ahead, direction 1 indicates the worm will make a right turn of 60° and similarly for the other directions. The worm cannot travel in direction 3 because that is the gridline it has just traversed. Thus a worm with rule {1,0,5,1} decides to travel in direction 1 the first time it has to make a choice, in direction 0 the next time it has to make a choice and so on. If there is only one available gridline, the worm has no choice but to take it and this is usually not explicitly listed.

There are 1,296 possible combinations of worm rules. This can be seen by the following argument:

1. If the worm encounters a node with no eaten segments, other than the one it has just eaten, it can either make a sharp turn or a gentle one. This is the situation shown in the figure above. Since the initial choice of left or right produces combinations that are simply mirrors of each other, they are not effectively different.
2. If it encounters a node with one eaten segment, it can leave along any of the remaining four. Only the worm's first return to the origin has this character.
3. For two eaten segments, the location of the eaten segments is important. The only type of two-segment intersections that can exist is that produced by the first rule, for which there are four distinct approach directions, each of which offers a choice of three departure directions. This allows for 81 different alternatives in choosing rules.
4. If the worm returns to the origin, it will encounter three eaten segments and must choose between the two remaining uneaten ones regardless of their distribution.
5. For four eaten segments, there is only one uneaten segment left and the worm must take it.

There are therefore 2×4×81×2x1=1,296 different combinations of rules. 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). 336 of these species eventually die. 73 patterns exhibit infinite behaviour, that is, they settle into a repeating pattern that does not return to the origin.

A further two are strongly believed to be infinite and one remains unsolved. Eleven of the rules exhibit complicated behaviour. They do not die even after many billions of iterations, nor do they adopt an obviously infinite pattern. Their ultimate fate was unknown until 2003 when Benjamin Chaffin developed new methods of solving them.

After many hours of computer time, nine of the eleven rules were solved, leaving the worms with rules {1,0,4,2,0,2,0} and {1,0,4,2,0,1,5}. 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. According to Rokicki, the worm is still active after 5.2×1019 timesteps. He used an algorithm based on Bill Gosper's Hashlife to simulate the worms at extraordinary speeds. This behaviour is considerably more complex than the related rectangular grid worm, which has a longest path of only 16 segments.

See also

• Langton's ant
• Busy beaver

External links

• Paterson's worms at Wikipedia