Paterson’s Worms

 

Paterson's worms are a type of finite automaton which exhibit some complex and beautiful behavior from a very simple set of rules. Wikipedia has an overview (slightly out of date); the French version has more current results. I heard about it when Ed Pegg Jr. mentioned it in the 9/15/03 update to MathPuzzle; later he wrote an article on it for the MAA, which got discussed on Slashdot. I'm indebted to Sven Kahrkling for a nice write-up of the results which has since disappeared from the web.

 

The basic idea is that a worm travels around a triangular (isometric) grid, never retracing its path. At each step, the worm looks around at the 5 adjacent points (the one it just came from is not considered) and sees a particular configuration of taken and open paths. It makes a decision as to which of the open paths to take, and this becomes a rule: every time from then on that the worm sees that same configuration of open and taken paths, it must go the same way as before. All of this is from the worm’s point of view – directions are not absolute but relative to the worm’s direction of travel, i.e. your choices are hard left (120 degrees), soft left (60 degrees), straight ahead, soft right, and hard right. A worm finishes if it reaches a point where there are no open paths; if you think about it you’ll realize that this can only happen at the starting point, and that a worm must return there three times to fill all the paths (it dies on its third return).

 

As it turns out there are exactly 412 distinct sets of rules, discarding the obvious symmetry of whether the first turn is left or right. That’s many fewer than you’d guess from all the combinations of rules, but many rule sets are equivalent because their worms die before using all the rules. Pictures of all 412 and details of their fates are in this table. 336 are known to finish, 73 are known to be infinite, 2 are almost certain (but not proven) to be infinite, and one remains undecided.

 

Thanks to a clever algorithm from Tomas Rokicki, based on Hashlife, (his results are here) the computation of a worm's path has been sped up by many orders of magnitude over a simple approach. Below are some results discovered in 2003-2004, and a few other of my favorites. The meaning of the "rule" column and details on the pictures are with the full list of worms.

 

Pattern number Rule Length / Lower Bound Pictures (click for larger version) Comments   Pattern number Rule Length / Lower Bound Pictures (click for larger version) Comments
061 1042015 Unknown - lower bound 5.2 * 10^19
Paterson's worm 061

This is the one worm which remains truly undecided. Random swirls like those shown to the left give way to irregular triangles after several billion steps.

After more than 10^19 steps, it still shows no sign of falling into any repetitive behavior.

Movie

  060 1042010 918,339

This was the longest known worm prior to 2003. Very similar turbulent structure to #061... but then it ends.

062 1042020 57,493,855,205,939
Paterson's worm 062
This is the longest worm known to finish. For the first 57,493,855,199,226 steps it is identical to worm 063.

Movie

  063 1042022 57,493,855,205,905 Only a close-up picture of the center for this one. All other pictures are all the same as for 062 -- the difference between them is all in the last pixel.
156 1252121 Almost certainly infinite - lower bound 2.2 * 10^16
Paterson's worm 156
This worm is almost certainly infinite, but a proof would be quite difficult. It builds beautiful fractal-like hexagons of ever-increasing size. Very similar to worm 323.   323 1525115 Almost certainly infinite - lower bound 4.5 * 10^15
Paterson's worm 323

Very similar to worm # 156, this also builds recursive hexagons.

185 1420224 16,811,365,528
Paterson's worm 185

The third-longest worm. Same as #232, rotated 180 degrees.

  232 1450224 16,811,365,528
Paterson's worm 232

Same as worm #185, rotated 180 degrees.

Movie

379 2014142 3,563,608,205
Paterson's worm 379

Same as worm #402, rotated 120 degrees.

  402 2454142 3,563,608,205
Paterson's worm 402

Same as worm #379, rotated 120 degrees.

Movie

392 2145142 87,996,218
Paterson's worm 392

The close-up picture of this one is neat -- although it's mostly a completely filled grid, due to rounding errors in the drawing of the lines there's still a ghost of a Sierpiński triangle pattern visible.

Movie

  055 1040512 569,804

This one has a delicate spider web structure.

184 1420221 Infinite

Some early irregular behavior led to this one initially being classified as 'undecided', but Tom Rokicki proved that it does settle into a repeating pattern and is infinite. He also showed that it is the same as worm #231 after the 13th step.

  231 1450221 Infinite

Same as worm #184 after the 13th step.

334 1525511 83,618

A complex structure of overlapping hexagons.

  289 1505111 52,549

A nice spider-webby design with near symmetry.

  

Pictures for the worms #061 and #062 were created with the new algorithm, and so some of the jagged edges are artifacts of its storage scheme – precise image data cannot be kept at all points. Thanks to Fractint for a nice selection of color palettes. Movies are encoded with Xvid. Higher resolution versions are available via email.

 

Worm Cubes

For the sixth Gathering for Gardner (G4G6) I created about 200 clear acrylic cubes with pictures of the worms layered inside them to give as an exchange gift to all the other participants.

 

  

 

If you’re interested you can see more pictures and a description of the process.

 

You can find me at chaffin@gmail.com.

Back home