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